K-Gram Based Fuzzy Keyword Search over Encrypted Cloud Computing

Wei Zhou, Lixi Liu, He Jing, Chi Zhang, Shaowen Yao, Shipu Wang

National Software School of Yunnan University, Kunming, China.
National Software School of Yunnan University, Kunming, China&Key Laboratory in Software Engineering of Yunnan Province, Kunming, China..

DOI: 10.4236/jsea.2013.61004                

Abstract

With recent significant development in the portable device market, cloud computing is getting more and more utilized. Many sensitive data are stored in cloud central servers. To ensure privacy, these data are usually encrypted before being uploaded—making file searching complicated. Although previous cloud computing searchable encryption schemes allow users to search encrypted data by keywords securely, these techniques only support exact keyword search and will fail if there are some spelling errors or if some morphological variants of words are used. In this paper, we provide the solution for fuzzy keyword search over encrypted cloud data. K-grams is used to produce fuzzy results. For security reasons, we use two separate servers that cannot communicate with each other. Our experiment result shows that our system is effective and scalable to handle large number of encrypted files.

Keywords

K-Gram; Fuzzy Keyword; Encrypted Cloud Computing

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	D. Boneh, G. D. Crescenzo, R. Ostrovsky and G. Persiano, “Public Key Encryption with Keyword Search,” Proceedings of EUROCRYPT, Interlaken, 2-6 May 2004.
[2]	E.-J. Goh, “Secure Indexes,” Cryptology ePrint Archive, 2003. http://eprint.iacr.org/2003/216
[3]	Y.-C. Chang and M. Mitzenmacher, “Privacy Preserving Keyword Searches on Remote Encrypted Data,” Lecture Notes in Computer Science, Applied Cryptography and Network Security, Vol. 3531, 2005, pp. 391-421.
[4]	R. Curtmola, J. A. Garay, S. Kamara and R. Ostrovsky, “Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions,” Proceedings of ACM CCS, Alexandria, 30 October-3 November 2006.
[5]	M. Bellare, A. Boldyreva and A. ONeill, “Deterministic and Efficiently Searchable Encryption,” Lecture Notes in Computer Science, Advances in Cryptology, Vol. 4622, 2007, pp. 535-552.
[6]	P. Golle, J. Staddon and B. Waters, “Secure Conjunctive Keyword Search over Encrypted Data,” Lecture Notes in Computer Science, Applied Cryptography and Network Security, Vol. 3089, 2004, pp. 31-45.
[7]	J. Byun, D. Lee and J. Lim, “Efficient Conjunctive Keyword Search on Encrypted Data Storage System,” Lecture Notes in Computer Science, Public Key Infrastructure, Vol. 4043, 2006, pp. 184-196.
[8]	J. Li, Q. Wang, C. Wang, N. Cao, K. Ren and W. Lou, “Fuzzy Keyword Search over Encrypted Data in Cloud Computing,” Proceedings of IEEE INFOCOM’10 Mini-Conference, San Diego, March 2010.
[9]	N. Cao, C. Wang, M. Li, K. Ren and W. Lou, “Privacy-Preserving Multi-keyword Ranked Search over Encrypted Cloud Data,” 2011 Proceedings IEEE INFOCOM, Shanghai, 10-15 April 2011, pp. 829-837.
[10]	Q. Liu, G.-J. Wang and J. Wu, “An Efficient Privacy Preserving Keyword Search Scheme in Cloud Computing,” International Conference on Computational Science and Engineering, Vancouver, 29-31 August 2009, pp. 715-720.