[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 light-weight 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), 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 range [a, b]. The authorization policy only allows queries of size at most t, for some threshold t. Our scheme relies on the solution to a combinatorial problem at the core of one popular approach, which concerns efficiently computing universal covers in binary trees. A set of subtrees "covers" a 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, not the particular endpoints a and 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 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 for any constant c > 1 and achieves optimal overhead. We conjecture that the overhead of the scheme decays exponentially in c.

Advisors: Aloni Cohen

Committee Members: David Cash, Aloni Cohen, and William Hoza