Article

Searchable symmetric encryption: improved definitions and efficient constructions

Authors:

Rafail OstrovskyAuthors Info & Claims

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

Pages 79 - 88

https://doi.org/10.1145/1180405.1180417

Published: 30 October 2006 Publication History

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

[1]

Google Desktop. http://desktop.google.com.

[2]

Privacy with Security. DARPA Information Science and Technology (ISAT) Study Group, December 2002. http://www.cs.berkeley.edu/ tygar/papers/ISAT-final-briefing.pdf.

[3]

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.

Digital Library

[4]

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.

Digital Library

[5]

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.

Digital Library

[6]

B. Barak and O. Goldreich. Universal arguments and their applications. In IEEE Conference on Computational Complexity, pages 194--203, 2002.

Digital Library

[7]

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.

[8]

S. Bellovin and W. Cheswick. Privacy-enhanced searches using encrypted Bloom filters. Technical Report 2004/022, IACR ePrint Cryptography Archive, 2004.

[9]

B. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422--426, 1970.

Digital Library

[10]

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.

Digital Library

[11]

D. Boneh, G. di Crescenzo, R. Ostrovsky, and G. Persiano. Public key encryption with keyword search. In Proc. EUROCRYPT 04, pages 506--522, 2004.

[12]

D. Boneh, E. Kushilevitz, R. Ostrovsky, and W. Skeith. Public-key encryption that allows PIR queries. Unpublished Manuscript, August 2006.

[13]

Y. C. Chang and M. Mitzenmacher. Privacy preserving keyword searches on remote encrypted data. In Applied Cryptography and Network Security Conference, 2005.

Digital Library

[14]

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.

[15]

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.

Digital Library

[16]

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.

Digital Library

[17]

E.-J. Goh. Secure indexes. Technical Report 2003/216, IACR ePrint Cryptography Archive, 2003. See http://eprint.iacr.org/2003/216.

[18]

O. Goldreich. Foundations of Cryptography. Cambridge University Press, 2001.

Digital Library

[19]

O. Goldreich and R. Ostrovsky. Software protection and simulation on oblivious RAMs. Journal of the ACM, 43(3):431--473, 1996.

Digital Library

[20]

S. Goldwasser and S. Micali. Probabilistic encryption. JCSS, 28(2):270--299, Apr. 1984.

[21]

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.

[22]

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.

Digital Library

[23]

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.

Digital Library

[24]

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.

Digital Library

[25]

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.

Digital Library

[26]

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.

Digital Library

[27]

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.

Digital Library

[28]

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.

Digital Library

[29]

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.

Digital Library

[30]

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.

Digital Library

Cited By

Wang XMa J(2025)Cloud-Network-End Collaborative Security for Wireless Networks: Architecture, Mechanisms, and ApplicationsTsinghua Science and Technology10.26599/TST.2023.901015830:1(18-33)Online publication date: Feb-2025
https://doi.org/10.26599/TST.2023.9010158
Bulbul SAbduljabbar Z(2024)Performing Encrypted Cloud Data Keyword Searches Using Blockchain Technology on Smart DevicesBasrah Researches Sciences10.56714/bjrs.50.1.2450:1(17)Online publication date: 30-Jun-2024
https://doi.org/10.56714/bjrs.50.1.24
Manikanta K. M A. G Akshay Aftab Ahmed Gavi Siddhana Gowda Prof. Shivakeshi Choupiri (2024)Authorized Keyword Search over Outsourced Encrypted Data in Cloud EnvironmentInternational Journal of Advanced Research in Science, Communication and Technology10.48175/IJARSCT-18468(418-420)Online publication date: 24-May-2024
https://doi.org/10.48175/IJARSCT-18468
Show More Cited By

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 ...
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 ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 October 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CCS06

Sponsor:

CCS06: 13th ACM Conference on Computer and Communications Security 2006

October 30 - November 3, 2006

Virginia, Alexandria, USA

Acceptance Rates

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1,178
Total Citations
View Citations
4,475
Total Downloads

Downloads (Last 12 months)292
Downloads (Last 6 weeks)38

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang XMa J(2025)Cloud-Network-End Collaborative Security for Wireless Networks: Architecture, Mechanisms, and ApplicationsTsinghua Science and Technology10.26599/TST.2023.901015830:1(18-33)Online publication date: Feb-2025
https://doi.org/10.26599/TST.2023.9010158
Bulbul SAbduljabbar Z(2024)Performing Encrypted Cloud Data Keyword Searches Using Blockchain Technology on Smart DevicesBasrah Researches Sciences10.56714/bjrs.50.1.2450:1(17)Online publication date: 30-Jun-2024
https://doi.org/10.56714/bjrs.50.1.24
Manikanta K. M A. G Akshay Aftab Ahmed Gavi Siddhana Gowda Prof. Shivakeshi Choupiri (2024)Authorized Keyword Search over Outsourced Encrypted Data in Cloud EnvironmentInternational Journal of Advanced Research in Science, Communication and Technology10.48175/IJARSCT-18468(418-420)Online publication date: 24-May-2024
https://doi.org/10.48175/IJARSCT-18468
Yan ZLin XZhang XXu JQu H(2024)Identity-Based Matchmaking Encryption with Equality TestEntropy10.3390/e2601007426:1(74)Online publication date: 15-Jan-2024
https://doi.org/10.3390/e26010074
Zheng YZhang WSong WWang XFu C(2024)Encrypted Video Search with Single/Multiple WritersACM Transactions on Multimedia Computing, Communications, and Applications10.1145/3643887Online publication date: 5-Feb-2024
https://doi.org/10.1145/3643887
Song XZheng YBai JDong CLiu ZChang EQuek TGao DZhou JCardenas A(2024)DISCO: Dynamic Searchable Encryption with Constant StateProceedings of the 19th ACM Asia Conference on Computer and Communications Security10.1145/3634737.3637674(1724-1738)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1145/3634737.3637674
K PK S GGhosh Ray IAdhikari ADatta SBiswas A(2024)On the Design of a Searchable Encryption Protocol for Keyword Search using Proactive Secret Sharing2024 IEEE 20th International Conference on e-Science (e-Science)10.1109/e-Science62913.2024.10678696(1-8)Online publication date: 16-Sep-2024
https://doi.org/10.1109/e-Science62913.2024.10678696
Song YGe XYu JHao RYang M(2024)Enabling Privacy-Preserving K-Hop Reachability Query Over Encrypted GraphsIEEE Transactions on Services Computing10.1109/TSC.2024.338295417:3(893-904)Online publication date: May-2024
https://doi.org/10.1109/TSC.2024.3382954
Li DWu JLe JLü QLiao XXiang T(2024)An Efficient Privacy-Preserving Ranked Multi-Keyword Retrieval for Multiple Data Owners in Outsourced CloudIEEE Transactions on Services Computing10.1109/TSC.2023.334179917:2(406-419)Online publication date: Mar-2024
https://doi.org/10.1109/TSC.2023.3341799
Li MGao JZhu LZhang ZLal CConti M(2024)Time-Restricted, Verifiable, and Efficient Query Processing Over Encrypted Data on CloudIEEE Transactions on Services Computing10.1109/TSC.2023.331158617:3(1239-1251)Online publication date: May-2024
https://doi.org/10.1109/TSC.2023.3311586
Show More Cited By

View Options

Get Access

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents