Article

Efficient conjunctive keyword search on encrypted data storage system

Authors:

Jin Wook Byun,

Dong Hoon Lee,

Jongin LimAuthors Info & Claims

EuroPKI 2006: Proceedings of the Third European conference on Public Key Infrastructure: theory and Practice

Pages 184 - 196

https://doi.org/10.1007/11774716_15

Published: 19 June 2006 Publication History

Publisher Site

Abstract

We study conjunctive keyword search scheme allowing for remote search of data containing each of several keywords on encrypted data storage system. A data supplier first uploads encrypted data on a storage system, and then a user of the storage system searches data containing keywords over encrypted data hence insider (such as an administrator of the storage system) and outsider attackers do not learn anything else about the data. Recently, Golle et al. first suggested conjunctive keyword search scheme, but the communication and storage costs linearly depend on the number of stored data in the database, hence it is not really suitable for a large scale database.

In this paper, we propose an efficient conjunctive keyword search scheme over encrypted data in aspects of communication and storage costs. Concretely, we reduce the storage cost of a user and the communication cost between a user and a data supplier to the constant amounts. We formally define security model for a conjunctive keyword search scheme and prove that the proposed scheme is secure under the decisional bilinear Diffie-Hellman (DBDH) assumption in the random oracle model.

References

[1]

M. Abdalla, M. Bellare, D. Catalano, E. Kiltz, T. Kohno, T. Lange, J. Malone-Lee, G. Neven, P. Paillier, and H. Shi, "Encryption with keyword search, revisited: consistency conditions, relations to anonymous IBE, and extensions", In Proceedings of Crypto '05, LNCS Vol. 3621, pp. 205-222, Springer-Verlag, 2005.

Digital Library

Google Scholar

[2]

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

Digital Library

Google Scholar

[3]

D. Boneh, G. D. Crescenzo, R. Ostrovsky, and G. Persiano, "Public Key Encryption with Keyword Search", In Proceedings of Eurocrypt '04, LNCS Vol. 3089, pp. 31-45, Springer-Verlag, 2004.

Crossref

Google Scholar

[4]

B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan, "Private Information Retrieval", In Proceedings of 29th STOC, 1997.

Digital Library

Google Scholar

[5]

G. Di. Crescenzo, Y. Ishai, and R. Ostrovsky, "Universal Servie-providers for Dtabase Private Information Retrieval", In Proceedings of 17th PODC, 1998.

Digital Library

Google Scholar

[6]

Y. Chang and M. Mitzenmacher, "Privacy preserving keyword searches on remote encrypted data", In Proceedings of ACNS '05 LNCS Vol. 3531, pp. 442-455, Springer-Verlag, 2005, An early version of this paper is appeared on Cryptology ePrint Archieve. Availabe at http://eprint.iacr.org/2004/051

Digital Library

Google Scholar

[7]

P. Golle, J. Staddon, and B. Waters, "Secure Conjunctive keyword search over encrytped data", In Proceedings of ACNS '04, LNCS Vol. 3089, pp. 31-45, Springer-Verlag, 2004.

Google Scholar

[8]

E. Goh, "Secure Indexes", In Cryptology ePrint Archieve on March 16, 2004, This paper is availabe at http://eprint.iacr.org/2003/216

Google Scholar

[9]

Microsoft Developer Network (MSDN), in the part of Maximum Capacity Specifications for SQL Server 2005. Refer to http://msdn2.microsoft.com/en-us/library/ms143432(SQL.90).aspx

Google Scholar

[10]

R. Ostrovsky and W. Skeith, "Private keyword search on streaming data", This paper will be appear in Crypto05.

Digital Library

Google Scholar

[11]

W. Ogata and K. Kurosawa, "Oblivious keyword search" Journal of Complexity Vol. 20, Issues 2-3, pp. 356-371, 2004.

Digital Library

Google Scholar

[12]

D. J. Park, K. Kim, and P. J. Lee, "Public Key Encryption with Conjunctive Field Keyword Search", In Proceedings of WISA '04, LNCS Vol. 3325, pp. 73-86, Springer-Verlag, 2004.

Digital Library

Google Scholar

[13]

D. Song, D. Wagner, and A. Perrig, "Practical Techniques for Searches on Encrypted Data", In Proceedings of IEEE sysmposium on Security and Privacy, 2000.

Digital Library

Google Scholar

Cited By

View all

Li FMa JMiao YLiu XNing JDeng R(2023)A Survey on Searchable Symmetric EncryptionACM Computing Surveys10.1145/361799156:5(1-42)Online publication date: 27-Nov-2023
https://dl.acm.org/doi/10.1145/3617991
Zhang YLi YWang Y(2020)Efficient Searchable Symmetric Encryption Supporting Dynamic Multikeyword Ranked SearchSecurity and Communication Networks10.1155/2020/72985182020Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1155/2020/7298518
Yang YLiu XDeng R(2020)Multi-User Multi-Keyword Rank Search Over Encrypted Data in Arbitrary LanguageIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2017.278758817:2(320-334)Online publication date: 11-Mar-2020
https://dl.acm.org/doi/10.1109/TDSC.2017.2787588
Show More Cited By

Efficient conjunctive keyword search on encrypted data storage system

Recommendations

Off-line keyword guessing attacks on recent keyword search schemes over encrypted data
SDM'06: Proceedings of the Third VLDB international conference on Secure Data Management

A keyword search scheme over encrypted documents allows for remote keyword search of documents by a user in possession of a trapdoor (secret key). A data supplier first uploads encrypted documents on a storage system, and then a user of the storage ...
Dynamic Verifiable Encrypted Keyword Search

Outsourcing data storage to the cloud securely and retrieving the remote data in an efficient way is a very significant research topic, with high relevance to secure cloud deployment. With the ever growing security and privacy concerns, encrypting the ...
Efficient Keyword Search over Encrypted Cloud Data

With the advent of cloud computing, most of the data owners are outsourcing their complex data management systems from local sites to the commercial public cloud for great flexibility and economic savings. But sensitive data has to be encrypted before ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

EuroPKI 2006: Proceedings of the Third European conference on Public Key Infrastructure: theory and Practice

June 2006

260 pages

ISBN:3540351515

Editors:
Andrea S. Atzeni
Dip. di Automatica ed Informatica, Politecnico di Torino, Corso Duca degli Abruzzi, 24, Turin, Italy
,
Antonio Lioy
Dip. Di Automatica e Informatica, Politecnico di Torino, Corso Duca degli Abruzzi 24, Torino, Italy

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 19 June 2006

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Li FMa JMiao YLiu XNing JDeng R(2023)A Survey on Searchable Symmetric EncryptionACM Computing Surveys10.1145/361799156:5(1-42)Online publication date: 27-Nov-2023
https://dl.acm.org/doi/10.1145/3617991
Zhang YLi YWang Y(2020)Efficient Searchable Symmetric Encryption Supporting Dynamic Multikeyword Ranked SearchSecurity and Communication Networks10.1155/2020/72985182020Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1155/2020/7298518
Yang YLiu XDeng R(2020)Multi-User Multi-Keyword Rank Search Over Encrypted Data in Arbitrary LanguageIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2017.278758817:2(320-334)Online publication date: 11-Mar-2020
https://dl.acm.org/doi/10.1109/TDSC.2017.2787588
Feng THe W(2018)Research on Privacy Preserving of Searchable EncryptionProceedings of the 2018 2nd High Performance Computing and Cluster Technologies Conference10.1145/3234664.3234665(58-68)Online publication date: 22-Jun-2018
https://dl.acm.org/doi/10.1145/3234664.3234665
Li YZhou FQin YLin MXu Z(2018)Integrity-verifiable conjunctive keyword searchable encryption in cloud storageInternational Journal of Information Security10.1007/s10207-017-0394-917:5(549-568)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1007/s10207-017-0394-9
Wang JChen XSun SLiu JAu MZhan Z(2018)Towards Efficient Verifiable Conjunctive Keyword Search for Large Encrypted DatabaseComputer Security10.1007/978-3-319-98989-1_5(83-100)Online publication date: 3-Sep-2018
https://dl.acm.org/doi/10.1007/978-3-319-98989-1_5
Sharma DJinwala D(2017)Multiuser Searchable Encryption with Token Freshness VerificationSecurity and Communication Networks10.1155/2017/64351382017Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1155/2017/6435138
Ogata WKurosawa K(2017)Efficient No-dictionary Verifiable Searchable Symmetric EncryptionFinancial Cryptography and Data Security10.1007/978-3-319-70972-7_28(498-516)Online publication date: 3-Apr-2017
https://dl.acm.org/doi/10.1007/978-3-319-70972-7_28
Abdelraheem MGehrmann CLindström MNordahl CPayer MMangard SWeippl EKatzenbeisser SAndroulaki EReiter M(2016)Executing Boolean Queries on an Encrypted Bitmap IndexProceedings of the 2016 ACM on Cloud Computing Security Workshop10.1145/2996429.2996436(11-22)Online publication date: 28-Oct-2016
https://dl.acm.org/doi/10.1145/2996429.2996436
Jiang HLi XXu Q(2016)An Improvement to a Multi-Client Searchable Encryption Scheme for Boolean QueriesJournal of Medical Systems10.1007/s10916-016-0610-640:12(1-11)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1007/s10916-016-0610-6
Show More Cited By

Abstract

References

Cited By

Recommendations

Off-line keyword guessing attacks on recent keyword search schemes over encrypted data

Dynamic Verifiable Encrypted Keyword Search

Efficient Keyword Search over Encrypted Cloud Data

Comments

Information

Published In

Sponsors

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations