Title: Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions
Speaker: Juan Garay, Bell Labs
Date: Wednesday, December 13, 2006 11:00am - 12:00pm
Location: DIMACS Center, CoRE Bldg, CoRE A*, Rutgers University, Busch Campus, Piscataway, NJ
*Note Room Change
Abstract:
Searchable symmetric encryption (SSE) allows a party to outsource the storage of his data to another party (a server) in a private manner, while maintaining the ability to selectively search over it. This problem has been the focus of active research for over a decade. In recent years, efficient solutions requiring only a constant number of rounds of interaction have been proposed at the expense of providing weaker security guarantees -- specifically, these solutions allow the "access pattern" (i.e., the order in which the encrypted items are "touched" by the server) to be revealed. In this talk we consider this weaker security model as well, and show two constant-round solutions to SSE that simultaneously enjoy the following properties:
1) Both solutions are more efficient than previous constant-round schemes. In particular, the work performed by the server per returned document is constant as opposed to linear in the size of the data.
2) Both solutions enjoy stronger security guarantees than previous constant-round schemes. We point out shortcomings of previous notions of security for SSE, and show how to design constructions which avoid these pitfalls. Further, our second solution also achieves what we call *adaptive* SSE security, where queries into the database can be chosen adaptively (by the adversary) during the execution of the search.
We also consider *multi-user* SSE, where an arbitrary group of parties other than the owner can submit search queries. We formally define SSE in the multi-user setting, and present an efficient construction that achieves better performance than simply using access control mechanisms.
This is joint work with Reza Curtmola, Seny Kamara, and Rafail Ostrovsky.