[CS] Gabe Schoenbach MS Presentation/Mar 4, 2025

[via cs]

This is an announcement of Gabe Schoenbach's MS Presentation
===============================================
Candidate: Gabe Schoenbach

Date: Tuesday, March 04, 2025

Time: 10 AM CST

Location: JCL 298

Title: Range-searchable symmetric encryption with minimal communication complexity

Abstract: Searchable symmetric encryption (SSE) schemes are relatively lightweight cryptographic protocols that enable a data owner D to outsource a database to an untrusted server E and submit queries. When used for Outsourced Symmetric Private Information Retrieval (OSPIR) [Jarecki, Jutla, Krawczyk et al., '13], additional third-party clients can submit queries to the database, subject to an authorization policy managed by D. Correctness of the scheme requires that for any query, the response from E includes all database items that would be returned had D hosted and queried the database locally. Standard SSE security limits the information E can learn about the data and the queries, while OSPIR security additionally limits what D can learn about the queries, while still being able to enforce a particular authorization policy. In this work, we build a range-searchable symmetric encryption (RSSE) scheme, where the client asks for documents indexed by a value in a queried range [a, b]. The authorization policy only allows queries of size b - a + 1 < T for some threshold T.   
A popular approach [Demertzis, Papadopoulos, Papapetrou, et al., '16, Faber, Jarecki, Krawczyk et. al., '15] to building RSSE schemes relies on tree-based indexes whose leaves are labeled 0, 1, 2, ... from left to right and correspond to items in the database. Core to this approach is the combinatorial problem of efficiently computing universal covers in binary trees. A set of subtrees "covers" the range [a, b] if it contains all the leaves in the range. To minimize leakage, we want "universal" covers, where the sizes of individual subtrees only depend on the size of the range [a,b], not the particular endpoints a, b. Minimizing the number and the total size of the subtrees reduces the communication complexity between the clients, the data owner D, and the server E.

Faber, Jarecki, Krawczyk et al., use universal covers to build an RSSE scheme that satisfies the OSPIR security guarantee. Their construction uses 3 subtrees and admits a 66% overhead in the worst case, where the overhead is the size of the subtrees normalized by the range size. In this work, we generalize their construction to build an OSPIR-secure RSSE scheme which uses a constant number of subtrees and (conjecturally) admits arbitrarily small worst-case overhead. We rely on a novel O(log r)-time algorithm that finds constant-sized universal covers of ranges of size r.

Advisor: Aloni Cohen

Committee: Aloni Cohen, David Cash, William Hoza