Searchable symmetric encryption: Improved definitions and efficient constructions

Reza Curtmola, Juan Garay, Seny Kamara, Rafail Ostrovsky

Research output: Contribution to journalConference articlepeer-review

1403 Scopus citations


Searchable symmetric encryption (SSE) allows a party to outsource the storage of its 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 in recent years. In this paper we show two solutions to SSE that simultaneously enjoy the following properties: Both solutions are more efficient than all 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. Both solutions enjoy stronger security guarantees than previous constant-round schemes. In fact, we point out subtle but serious problems with 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 to the server can be chosen adaptively (by the adversary) during the execution of the search; this notion is both important in practice and has not been previously considered.Surprisingly, despite being more secure and more efficient, our SSE schemes are remarkably simple. We consider the simplicity of both solutions as an important step towards the deployment of SSE technologies.As an additional contribution, we also consider multi-user SSE. All prior work on SSE studied the setting where only the owner of the data is capable of submitting search queries. We consider the natural extension 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.

Original languageEnglish (US)
Article number1180417
Pages (from-to)79-88
Number of pages10
JournalProceedings of the ACM Conference on Computer and Communications Security
StatePublished - 2006
Externally publishedYes
EventCCS 2006: 13th ACM Conference on Computer and Communications Security - Alexandria, VA, United States
Duration: Oct 30 2006Nov 3 2006

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Networks and Communications


  • Multi-user
  • Searchable encryption
  • Searchable symmetric encryption
  • Security definitions


Dive into the research topics of 'Searchable symmetric encryption: Improved definitions and efficient constructions'. Together they form a unique fingerprint.

Cite this