Abstract
We study the setting in which a user stores encrypted documents (e.g. e-mails) on an untrusted server. In order to retrieve documents satisfying a certain search criterion, the user gives the server a capability that allows the server to identify exactly those documents. Work in this area has largely focused on search criteria consisting of a single keyword. If the user is actually interested in documents containing each of several keywords (conjunctive keyword search) the user must either give the server capabilities for each of the keywords individually and rely on an intersection calculation (by either the server or the user) to determine the correct set of documents, or alternatively, the user may store additional information on the server to facilitate such searches. Neither solution is desirable; the former enables the server to learn which documents match each individual keyword of the conjunctive search and the latter results in exponential storage if the user allows for searches on every set of keywords.
We define a security model for conjunctive keyword search over encrypted data and present the first schemes for conducting such searches securely. We propose first a scheme for which the communication cost is linear in the number of documents, but that cost can be incurred “offline” before the conjunctive query is asked. The security of this scheme relies on the Decisional Diffie-Hellman (DDH) assumption. We propose a second scheme whose communication cost is on the order of the number of keyword fields and whose security relies on a new hardness assumption.
Chapter PDF
Similar content being viewed by others
Keywords
References
Boneh, D.: The decision Diffie-Hellman problem. In: ANTS 1998. LNCS, vol. 1423, pp. 48–63. Springer, Heidelberg (1998)
Boneh, D., Franklin, M.: Identity based encryption from the Weil pairing. SIAM J. of Computing 32(3), 586–615 (2003)
Boneh, D., Di Crescenzo, G., Ostrovsky, R., Persiano, G.: Searchable public key encryption. In: To appear in Adances in Cryptology – Eurocrypt ‘04. Cryptology ePrint Archive, Report 2003/195 (September 2003), http://eprint.iacr.org/2003/195/
Bennett, K., Grothoff, C., Horozov, T., Patrascu, I.: Efficient sharing of encrypted data. In: Batten, L.M., Seberry, J. (eds.) ACISP 2002. LNCS, vol. 2384, p. 107. Springer, Heidelberg (2002)
Cachin, C., Micali, S., Stadler, M.: Computationally private information retrieval with polylogarithmic communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, p. 402. Springer, Heidelberg (1999)
Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. In: proceedings of FOCS 1995 (1995)
Chor, B., Gilboa, N., Naor, M.: Private Information Retrieval by Keywords. Technical report, TR CS0917, Department of Computer Science, Technion (1997)
Dodis, Y.: Efficient construction of (distributed) random functions. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 1–17. Springer, Heidelberg (2002)
Goh, E.: Secure Indexes. In: the Cryptology ePrint Archive, Report 2003/216, March 16 (2004), http://eprint.iacr.org/2003/216/
Google, Inc. The basics of Google search, http://www.google.com/help/basics.html
Goldreich, O., Ostrovsky, R.: Software protection and simulation on oblivious RAMs. J. ACM, 431-473 (1996)
Jarecki, S., Lincoln, P., Shmatikov, V.: Negotiated privacy. In: The International Symposium on Software Security (2002)
Joux, A.: The Weil and Tate pairings as building blocks for public key cryptosystems. In: Proceedings Fifth Algorithmic Number Theory Symposium (2002)
Joux, A., Nguyen, K.: Separating decision Diffie-Hellman from Diffie-Hellman in cryptographic groups. In: IACR ePrint Archive: http://eprint.iacr.org/2001/003/
Song, D., Wagner, D., Perrig, A.: Practical Techniques for Searches on Encrypted Data. In: Proc. of the 2000 IEEE Security and Privacy Symposium (May 2000)
Tô, V., Safavi-Naini, R., Zhang, F.: New Traitor Tracing Schemes Using Bilinear Map. In: 2003 ACM Workshop on Digital Rights Management (DRM 2003), The Wyndham City Center Washington DC, USA, October 27 (2003)
Waters, B., Balfanz, D., Durfee, G., Smetters, D.: Building an Encrypted and Searchable Audit Log. In: Proceedings of NDSS 2004 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Golle, P., Staddon, J., Waters, B. (2004). Secure Conjunctive Keyword Search over Encrypted Data. In: Jakobsson, M., Yung, M., Zhou, J. (eds) Applied Cryptography and Network Security. ACNS 2004. Lecture Notes in Computer Science, vol 3089. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24852-1_3
Download citation
DOI: https://doi.org/10.1007/978-3-540-24852-1_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22217-0
Online ISBN: 978-3-540-24852-1
eBook Packages: Springer Book Archive