Abstract
We present two provably secure and efficient schemes for performing conjunctive keyword searches over symmetrically encrypted data. Our first scheme is based on Shamir Secret Sharing and provides the most efficient search technique in this context to date. Although the size of its trapdoors is linear in the number of documents being searched, we empirically show that this overhead remains reasonable in practice. Nonetheless, to address this limitation we provide an alternative based on bilinear pairings that yields constant size trapdoors. This latter construction is not only asymptotically more efficient than previous secure conjunctive keyword search schemes in the symmetric setting, but incurs significantly less storage overhead. Additionally, unlike most previous work, our constructions are proven secure in the standard model.
Chapter PDF
Similar content being viewed by others
References
Ateniese, G., Camenisch, J., de Medeiros, B.: Untraceable rfid tags via insubvertible encryption. In: 12th ACM Conference on Computer and Communications Security (CCS 2005) (2005)
Ballard, L., Green, M., de Medeiros, B., Monrose, F.: Correlation resistant storage. Technical Report TR-SP-BGMM-050507, Johns Hopkins University Department of Computer Science (2005)
Ballard, L., Kamara, S., Monrose, F.: Achieving efficient conjunctive keyword searches over encrypted data. Technical Report TR-SP-BKM-050920, Johns Hopkins University Department of Computer Science (2005)
Barreto, P., Kim, H., Lynn, B., Scott, M.: Efficient algorithms for pairing-based cryptosystems. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 354–369. Springer, Heidelberg (2002)
Barreto, P., Lynn, B., Scott, M.: On the selection of pairing-friendly groups. In: Matsui, M., Zuccherato, R.J. (eds.) SAC 2003. LNCS, vol. 3006, pp. 17–25. Springer, Heidelberg (2004)
Bellare, M., Canetti, R., Krawczyk, H.: Keying hash functions for message authentication. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 1–15. Springer, Heidelberg (1996)
Bloom, B.: Space/time trade-offs in hash coding with allowable errors. Communications of the ACM 13(7), 422–426 (1970)
Boneh, D.: The Decision-Diffie Hellman Problem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 48–63. Springer, Heidelberg (1998)
Boneh, D., Boyen, X., Sacham, H.: Short group signatures. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 41–55. Springer, Heidelberg (2004)
Boneh, D., di Crescenzo, G., Ostrovsky, R., Persiano, G.: Public key encryption with keyword search. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 506–522. Springer, Heidelberg (2004)
Camenisch, J., Hohenberger, S., Lysyanskaya, A.: Compact e-cash. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 302–321. Springer, Heidelberg (2005)
Chang, Y., Mitzenmacher, M.: Privacy preserving keyword searches on remote encrypted data. In: Ioannidis, J., Keromytis, A.D., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 442–455. Springer, Heidelberg (2005)
Clarke, I., Sandberg, O., Wiley, B., Hong, T.: Freenet: a distributed anonymous information storage and retrieval system. In: Federrath, H. (ed.) Designing Privacy Enhancing Technologies. LNCS, vol. 2009, pp. 46–66. Springer, Heidelberg (2001)
Microsoft Corp. Federated, available and reliable storage for an incompletely trusted environment (Farsite), See http://research.microsoft.com/sn/Farsite/
Davis, D., Monrose, F., Reiter, M.: Time-scoped searching of encrypted audit logs. In: López, J., Qing, S., Okamoto, E. (eds.) ICICS 2004. LNCS, vol. 3269, pp. 532–545. Springer, Heidelberg (2004)
Federal Information Processing Standards. Advanced Encryption Standard (AES) – FIPS 197 (November 2001)
Goh, E.-J.: Secure indexes. Technical Report 2003/216, IACR ePrint Cryptography Archive (2003), See http://eprint.iacr.org/2003/216
Golle, P., Staddon, J., Waters, B.: Secure conjunctive keyword search over encrypted data. In: Jakobsson, M., Yung, M., Zhou, J. (eds.) ACNS 2004. LNCS, vol. 3089, pp. 31–45. Springer, Heidelberg (2004)
Jansen, B., Spink, A., Bateman, J., Saracevic, T.: Real life information retrieval: a study of user queries on the web. SIGIR Forum 32(1), 5–17 (1998)
Knuth, D.: The Art of Computer Programming, 2nd edn., vol. 2. Addison-Wesley, Reading (1981)
Kubiatowicz, J., Bindel, D., Chen, Y., Czerwinski, S., Eaton, P., Geels, D., Gummadi, R., Rhea, S., Weatherspoon, H., Wells, C., Zhao, B.: Oceanstore: an architecture for global-scale persistent storage. In: Ninth international conference on Architectural support for programming languages and operating systems, pp. 190–201. ACM Press, New York (2000)
Lenstra, A., Verheul, E.: Selecting cryptographic key sizes. In: Imai, H., Zheng, Y. (eds.) PKC 2000. LNCS, vol. 1751, pp. 446–465. Springer, Heidelberg (2000)
The OpenSSL Library, See http://www.openssl.org
Shamus Software Ltd. Multiprecision integer and rational arithmetic C/C++ library (MIRACL), See http://indigo.ie/~mscott
Park, D., Kim, K., Lee, P.: Public key encryption with conjunctive field keyword search. In: Lim, C.H., Yung, M. (eds.) WISA 2004. LNCS, vol. 3325, pp. 73–86. Springer, Heidelberg (2005)
Scott, M.: Authenticated ID-based key exchange and remote log-in with simple to ken and PIN number. Technical Report 2002/164, International Association for Cryptological Research (2002), Available at http://eprint.iacr.org/2002/164
Shamir, A.: How to share a secret. Communications of the ACM 22, 612–613 (1979)
Song, D., Wagner, D., Perrig, A.: Practical techniques for searching on encrypted data. In: IEEE Symposium on Research in Security and Privacy, May 2000, pp. 44–55. IEEE Computer Society, Los Alamitos (2000)
Waters, B., Balfanz, D., Durfee, G., Smetters, D.: Building an encrypted and searchable audit log. In: Network and Distributed System Security Symposium (NDSS 2004). The Internet Society (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ballard, L., Kamara, S., Monrose, F. (2005). Achieving Efficient Conjunctive Keyword Searches over Encrypted Data. In: Qing, S., Mao, W., López, J., Wang, G. (eds) Information and Communications Security. ICICS 2005. Lecture Notes in Computer Science, vol 3783. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11602897_35
Download citation
DOI: https://doi.org/10.1007/11602897_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30934-5
Online ISBN: 978-3-540-32099-9
eBook Packages: Computer ScienceComputer Science (R0)