Article

Searchable symmetric encryption: improved definitions and efficient constructions

Authors:
Reza Curtmola

Johns Hopkins University

Johns Hopkins University
View Profile

,
Juan Garay

Bell Labs -- Lucent Technologies

Bell Labs -- Lucent Technologies
View Profile

,
Seny Kamara

Johns Hopkins University

Johns Hopkins University
View Profile

,
Rafail Ostrovsky

University of California at Los Angeles

University of California at Los Angeles
View Profile

CCS '06: Proceedings of the 13th ACM conference on Computer and communications securityOctober 2006Pages 79–88https://doi.org/10.1145/1180405.1180417

Published:30 October 2006Publication History

CCS '06: Proceedings of the 13th ACM conference on Computer and communications security

Pages 79–88

ABSTRACT

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.

References

Google Desktop. http://desktop.google.com.Google Scholar
Privacy with Security. DARPA Information Science and Technology (ISAT) Study Group, December 2002. http://www.cs.berkeley.edu/ tygar/papers/ISAT-final-briefing.pdf.Google Scholar
M. Abdalla, M. Bellare, D. Catalano, E. Kiltz, T. Kohno, T. Lange, J. M. Lee, G. Neven, P. Paillier, and H. Shi. Searchable encryption revisited: Consistency properties, relation to anonymous IBE, and extensions. In CRYPTO 2005, volume 3621 of LNCS, pages 205--222. Springer, 2005. Google ScholarDigital Library
A. Adya, W. Bolosky, M. Castro, R. Chaiken, G. Cermak, J. Douceur, J. Howell, J. Lorch, M. Theimer, and R. Wattenhofer. Farsite: Federated, available, and reliable storage for an incompletely trusted environment. In Proceedings of the 5th SOSDI, December 2002. Google ScholarDigital Library
L. Ballard, S. Kamara, and F. Monrose. Achieving efficient conjunctive keyword searches over encrypted data. In Proceedings of the Seventh International Conference on Information and Communication Security (ICICS 2005), pages 414--426, 2005. Google ScholarDigital Library
B. Barak and O. Goldreich. Universal arguments and their applications. In IEEE Conference on Computational Complexity, pages 194--203, 2002. Google ScholarDigital Library
M. Bellare, A. Boldyreva, and A. O'Neill. Efficiently-searchable and deterministic asymmetric encryption. Cryptology ePrint archive, June 2006. report 2006/186, http://eprint.iacr.org/2006/186.Google Scholar
S. Bellovin and W. Cheswick. Privacy-enhanced searches using encrypted Bloom filters. Technical Report 2004/022, IACR ePrint Cryptography Archive, 2004.Google Scholar
B. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422--426, 1970. Google ScholarDigital Library
M. Blum, W. S. Evans, P. Gemmell, S. Kannan, and M. Naor. Checking the correctness of memories. In IEEE Symposium on Foundations of Computer Science, pages 90--99, 1991. Google ScholarDigital Library
D. Boneh, G. di Crescenzo, R. Ostrovsky, and G. Persiano. Public key encryption with keyword search. In Proc. EUROCRYPT 04, pages 506--522, 2004.Google ScholarCross Ref
D. Boneh, E. Kushilevitz, R. Ostrovsky, and W. Skeith. Public-key encryption that allows PIR queries. Unpublished Manuscript, August 2006.Google Scholar
Y. C. Chang and M. Mitzenmacher. Privacy preserving keyword searches on remote encrypted data. In Applied Cryptography and Network Security Conference, 2005. Google ScholarDigital Library
R. Curtmola, J. Garay, S. Kamara, and R. Ostrovsky. Searchable symmetric encryption: Improved definitions and efficient constructions. Cryptology ePrint archive, June 2006. report 2006/210, http://eprint.iacr.org/2006/210.Google Scholar
A. Fiat and M. Naor. Broadcast encryption. In D. R. Stinson, editor, Proc. CRYPTO 93, volume 773 of Lecture Notes in Computer Science, pages 480--491. Springer-Verlag, 1994. Google ScholarDigital Library
M. Fredman, J. Komlós, and E. Szemerédi. Storing a sparse table with 0(1) worst case access time. J. ACM, 31(3):538--544, 1984. Google ScholarDigital Library
E.-J. Goh. Secure indexes. Technical Report 2003/216, IACR ePrint Cryptography Archive, 2003. See http://eprint.iacr.org/2003/216.Google Scholar
O. Goldreich. Foundations of Cryptography. Cambridge University Press, 2001. Google ScholarDigital Library
O. Goldreich and R. Ostrovsky. Software protection and simulation on oblivious RAMs. Journal of the ACM, 43(3):431--473, 1996. Google ScholarDigital Library
S. Goldwasser and S. Micali. Probabilistic encryption. JCSS, 28(2):270--299, Apr. 1984.Google ScholarCross Ref
P. Golle, J. Staddon, and B. Waters. Secure conjunctive keyword search over encrypted data. In M. Jakobsson, M. Yung, and J. Zhou, editors, Applied Cryptography and Network Security Conference (ACNS), volume 3089 of LNCS, pages 31--45. Springer-Verlag, 2004.Google Scholar
Y. Ishai, E. Kushilevitz, R. Ostrovsky, and A. Sahai. Batch codes and their applications. In 36th Annual ACM Symposium on Theory of Computing (STOC '04), pages 262--271. ACM, 2004. Google ScholarDigital Library
Y. Ishai, E. Kushilevitz, R. Ostrovsky, and A. Sahai. Cryptography from anonymity. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS '06). IEEE, 2006. Google ScholarDigital Library
J. Kubiatowicz, D. Bindel, Y. Chen, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer, C. Wells, and B. Zhao. Oceanstore: An architecture for global-scale persistent storage. In Proceedings of ACM ASPLOS '00. ACM, November 2000. Google ScholarDigital Library
E. Kushilevitz and R. Ostrovsky. Replication is NOT needed: SINGLE database, computationally-private information retrieval. In IEEE Symposium on Foundations of Computer Science, pages 364--373, 1997. Google ScholarDigital Library
A. Muthitacharoen, R. Morris, T. Gil, and B. Chen. Ivy: A read/write peer-to-peer file system. In Proceedings of the 5th SOSDI, December 2002. Google ScholarDigital Library
R. Ostrovsky. Software protection and simulations on oblivious RAMs. In Proceedings of 22nd Annual ACM Symposium on Theory of Computing, 1990. MIT Ph.D. Thesis, 1992. Google ScholarDigital Library
R. Ostrovsky and W. Skeith. Private searching on streaming data. In Advances in Cryptology - CRYPTO '05, volume 3621 of Lecture Notes in Computer Science, pages 223--240. Springer, 2005. Google ScholarDigital Library
D. Park, K. Kim, and P. Lee. Public key encryption with conjunctive field keyword search. In 5th International Workshop WISA 2004, volume 3325 of LNCS, pages 73--86. Springer, 2004. Google ScholarDigital Library
D. Song, D. Wagner, and A. Perrig. Practical techniques for searching on encrypted data. In Proceedings of 2000 IEEE Symposium on Security and Privacy, pages 44--55, May 2000. Google ScholarDigital Library

Index Terms

Searchable symmetric encryption: improved definitions and efficient constructions

Recommendations

Deniable Searchable Symmetric Encryption

In the recent years, Searchable Symmetric Encryption (SSE) has become one of the hottest topic in cloud-computing area because of its availability and flexibility, and there are a series of SSE schemes were proposed. The adversary considered in these ...
Read More
Searchable symmetric encryption: Improved definitions and efficient constructions

Searchable symmetric encryption SSE allows a party to outsource the storage of his data to another party in a private manner, while maintaining the ability to selectively search over it. This problem has been the focus of active research and several ...
Read More
Symmetric Searchable Encryption for Database Applications
NBIS '11: Proceedings of the 2011 14th International Conference on Network-Based Information Systems

This paper proposes an efficient symmetric searchable encryption to achieve indistinguishability of indexes and trapdoors. Previous symmetric searchable encryptions are either insecure because their trapdoor generation algorithms are not probabilistic ...
Read More

Comments

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Published in
CCS '06: Proceedings of the 13th ACM conference on Computer and communications security
October 2006
434 pages
ISBN:1595935185
DOI:10.1145/1180405
General Chair:
Ari Juels
RSA Laboratories
,
Program Chairs:
Rebecca Wright
Stevens Institute of Technology
,
Sabrina De Capitani di Vimercati
University of Milan, Italy
Copyright © 2006 ACM
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
- Published: 30 October 2006
Permissions
Request permissions about this article.
Request Permissions

Check for updates
Author Tags
multi-user
searchable encryption
searchable symmetric encryption
security definitions
Qualifiers
- Article
Conference

Acceptance Rates
Overall Acceptance Rate1,261of6,999submissions,18%
Upcoming Conference
CCS '24

Sponsor:

sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 14 - 18, 2024

Salt Lake City , UT , USA
Funding Sources
Other Metrics
View Article Metrics

Article Metrics
- 1,142
  Total Citations
  View Citations
- 4,370
  Total Downloads
- Downloads (Last 12 months)333
- Downloads (Last 6 weeks)25
Other Metrics
View Author Metrics
Cited By
View all

PDF Format

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Searchable symmetric encryption: improved definitions and efficient constructions

CCS '06: Proceedings of the 13th ACM conference on Computer and communications security

ABSTRACT

References

Cited By

Index Terms

Recommendations

Deniable Searchable Symmetric Encryption

Searchable symmetric encryption: Improved definitions and efficient constructions

Symmetric Searchable Encryption for Database Applications