Abstract
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 system searches documents containing keywords while insider (such as administrators of the storage system) and outsider attackers do not learn anything else about the documents.
In this paper, we firstly raise a serious vulnerability of recent keyword search schemes, which lies in the fact that keywords are chosen from much smaller space than passwords and users usually use well-known keywords for search of document. Hence this fact sufficiently gives rise to an off-line keyword guessing attack. Unfortunately, we observe that the recent public key-based keyword search schemes are susceptible to an off-line keyword guessing attack. We demonstrated that anyone (insider/outsider) can retrieve information of certain keyword from any captured query messages.
This research was supported by the MIC(Ministry of Information and Communication), Korea, under the ITRC(Information Technology Research Center) support program supervised by the IITA(Institute of Information Technology Assessment).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abdalla, M., Bellare, M., Catalano, D., Kiltz, E., Kohno, T., Lange, T., Malone-Lee, J., Neven, G., Paillier, P., Shi, H.: Encryption with keyword search, revisited: consistency conditions, relations to anonymous IBE, and extensions. This paper will be appear in: Crypto 2005 (2005)
Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of the First ACM Conference on Computer and Communications Security. ACM, New York (1995)
Boneh, D., Crescenzo, G.D., 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)
Boneh, D., Franklin, M.: Identity-Based Encryption from the Weil Pairing. SIAM J. of Computing 32(3), 586–615 (2003)
Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private Information Retrieval. In: Proceedings of 29th STOC (1997)
Di Crescenzo, G., Ishai, Y., Ostrovsky, R.: Universal Servie-providers for Dtabase Private Information Retrieval. In: Proceedings of 17th PODC (1998)
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); An early version of this paper is appeared on Cryptology ePrint Archieve, Available at: http://eprint.iacr.org/2004/051
Golle, P., Staddon, J., Waters, B.: Secure Conjunctive keyword search over encrytped data. In: Jakobsson, M., Yung, M., Zhou, J. (eds.) ACNS 2004. LNCS, vol. 3089, pp. 31–45. Springer, Heidelberg (2004)
Goh, E.: Secure Indexes. Cryptology ePrint Archieve on (March 16, 2004), This paper is availabe at: http://eprint.iacr.org/2003/216
Mish, F.: Merriam-Webster’s Collegiate Dictionary, 11th edn. Merriam-Webser, Inc. (2003), http://www.m-w.com/help/
Ostrovsky, R., Skeith, W.: Private keyword search on streaming data. In: Crypto 2005 (2005) (This paper will be appear)
Ogata, W., Kurosawa, K.: Oblivious keyword search. Journal of Complexity 20(2-3), 356–371 (2004)
Park, D.J., Kim, K., Lee, P.J.: 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)
Song, D., Wagner, D., Perrig, A.: Practical Techniques for Searches on Encrypted Data. In: Proceedings of IEEE sysmposium on Security and Privacy (2000)
Zimmermann, P.R.: The official PGP User’s Guide. MIT Press, Cambridge (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Byun, J.W., Rhee, H.S., Park, HA., Lee, D.H. (2006). Off-Line Keyword Guessing Attacks on Recent Keyword Search Schemes over Encrypted Data. In: Jonker, W., Petković, M. (eds) Secure Data Management. SDM 2006. Lecture Notes in Computer Science, vol 4165. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11844662_6
Download citation
DOI: https://doi.org/10.1007/11844662_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-38984-2
Online ISBN: 978-3-540-38987-3
eBook Packages: Computer ScienceComputer Science (R0)