Abstract
Searchable encryption is used to support searches over encrypted data stored on cloud servers. Traditional searchable encryption only supports exact keyword search instead of more flexible fuzzy keyword search. To solve this problem, a recent emerging paradigm, named fuzzy keyword searchable encryption, has been proposed. There have been some proposals designed for fuzzy keyword search in the symmetric key setting, but none efficient schemes in the public key setting. In this paper, we propose a new primitive of interactive public key encryption with fuzzy keyword search (IPEFKS), which supports efficient fuzzy keyword search over encrypted data in the public key setting. We construct and implement a homomorphic encryption based IPEFKS scheme. To compare this scheme with the existing ones, we implement LWW-FKS, which, to the best of our knowledge, is the most efficient among the existing schemes. The experimental results show that IPEFKS is much more efficient than LWW-FKS.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Boneh, D., Di Crescenzo, G., Ostrovsky, R., Persiano, G.: Public key encryption with keyword search. In: Cachin, C., Camenisch, J. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 506–522. Springer, Heidelberg (2004)
Bellare, M., Boldyreva, A., O’Neill, A.: Deterministic and Efficiently Searchable Encryption. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 535–552. Springer, Heidelberg (2007)
Goh, E.J.: Secure indexes. IACR Cryptology ePrint Archive 2003, 216 (2003)
Song, D.X., Wagner, D., Perrig, A.: Practical techniques for searcheson encrypted data. In: IEEE Symposium on Security and Privacy, pp. 44–55 (2000)
Bringer, J., Chabanne, H.: Embedding edit distance to enable private keyword search. Human-centric Computing and Information Science 2(2) (2012)
Bringer, J., Chabanne, H., Kindarji, B.: Error-tolerant searchable encryption. In: Proceedings of the 2009 IEEE International Conference on Communications (2009)
Chor, B., Kushilevitz, E., Goldreich, O., Sudan, M.: Private information retrieval. J. ACM 45(6), 965–981 (1998)
Fan, J., Vercauteren, F.: Somewhat practical fully homomorphic encryption. IACR Cryptology ePrint Archive 2012, 144 informal publication (2012)
Li, J., Wang, Q., Wang, C., Cao, N., Ren, K., Lou, W.: Fuzzy keyword search over encrypted data in cloud computing. In: INFOCOM 2010, pp. 441–445 (2010)
Ostrovsky, R., Rabani, Y.: Low distortion embeddings for edit distance. J. ACM 54(5) (October 2007)
Ostrovsky, R., Shoup, V.: Private information storage (extended abstract). In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC 1997, pp. 294–303. ACM, New York (1997)
Pang, X., Yang, B., Huang, Q.: Privacy-preserving noisy keyword search in cloud computing. In: Chim, T.W., Yuen, T.H. (eds.) ICICS 2012. LNCS, vol. 7618, pp. 154–166. Springer, Heidelberg (2012)
Suga, T., Nishide, T., Sakurai, K.: Secure keyword search using bloom filter with specified character positions. In: Takagi, T., Wang, G., Qin, Z., Jiang, S., Yu, Y. (eds.) ProvSec 2012. LNCS, vol. 7496, pp. 235–252. Springer, Heidelberg (2012)
Tang, Q.: Search in encrypted data: Theoretical models and practical applications. IACR Cryptology ePrint Archive 2012, 648 (2012)
Wang, C., Ren, K., Yu, S., Urs, K.M.R.: Achieving usable and privacy-assured similarity search over outsourced cloud data. In: INFOCOM, pp. 451–459 (2012)
Kuzu, M., Islam, M.S., Kantarcioglu, M.: Efficient similarity search over encrypted data. In: Proceedings of the 2012 IEEE 28th International Conference on Data Engineering, ICDE 2012. IEEE Computer Society, Washington, DC (2012)
Yau, W.-C., Heng, S.-H., Goi, B.-M.: Off-line keyword guessing attacks on recent public key encryption with keyword search schemes. In: Rong, C., Jaatun, M.G., Sandnes, F.E., Yang, L.T., Ma, J. (eds.) ATC 2008. LNCS, vol. 5060, pp. 100–105. Springer, Heidelberg (2008)
Xu, P., Jin, H., Wu, Q., Wang, W.: Public-key encryption with fuzzy keyword search: A provably secure scheme under keyword guessing attack. IEEE Transactions on Computers 99(PrePrints), 1 (2012)
Information Retrieval: Implementing and Evaluating Search Engines. MIT Press, Cambridge (2010) ISBN 978-0-262-02651-2
Lynn, B.: Pairing-Based Cryptography Library, http://crypto.stanford.edu/pbc/
Hart, W.: FLINT: Fast Library for Number Theory, http://www.flintlib.org
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dong, Q., Guan, Z., Wu, L., Chen, Z. (2013). Fuzzy Keyword Search over Encrypted Data in the Public Key Setting. In: Wang, J., Xiong, H., Ishikawa, Y., Xu, J., Zhou, J. (eds) Web-Age Information Management. WAIM 2013. Lecture Notes in Computer Science, vol 7923. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38562-9_74
Download citation
DOI: https://doi.org/10.1007/978-3-642-38562-9_74
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38561-2
Online ISBN: 978-3-642-38562-9
eBook Packages: Computer ScienceComputer Science (R0)