›› 2014, Vol. 29 ›› Issue (1): 81-89.doi: 10.1007/s11390-013-1413-6

Special Issue: Data Management and Data Mining

• Computer Networks and Distributed Computing • Previous Articles     Next Articles

Effective Error-Tolerant Keyword Search for Secure Cloud Computing

Bo Yang1 (杨波), Xiao-Qiong Pang2 (庞晓琼), Jun-Qiang Du1 (杜军强), and Dan Xie1 (解丹)   

  1. 1 School of Computer Science, Shaanxi Normal University, Xi'an 710062, China;
    2 College of Computer and Control Engineering, North University of China, Taiyuan 030051, China
  • Received:2013-01-15 Revised:2013-04-28 Online:2014-01-05 Published:2014-01-05
  • Supported by:

    This work is supported by the National Natural Science Foundation of China under Grant Nos. 61272436, 61003232 and 61272404, and the Natural Science Foundation of Guangdong Province of China under Grant No. 10351806001000000.

The existing solutions to keyword search in the cloud can be divided into two categories: searching on exact keywords and searching on error-tolerant keywords. An error-tolerant keyword search scheme permits to make searches on encrypted data with only an approximation of some keyword. The scheme is suitable to the case where users' searching input might not exactly match those pre-set keywords. In this paper, we first present a general framework for searching on error-tolerant keywords. Then we propose a concrete scheme, based on a fuzzy extractor, which is proved secure against an adaptive adversary under well-defined security definition. The scheme is suitable for all similarity metrics including Hamming distance, edit distance, and set difference. It does not require the user to construct or store anything in advance, other than the key used to calculate the trapdoor of keywords and the key to encrypt data documents. Thus, our scheme tremendously eases the users' burden. What is more, our scheme is able to transform the servers' searching for error-tolerant keywords on ciphertexts to the searching for exact keywords on plaintexts. The server can use any existing approaches of exact keywords search to search plaintexts on an index table.

[1] Mell P, Grance T. The NIST definition of cloud computing. National Institute of Standards and Technology Special Publication, SP 800-145, September 2011. http://csrc. nist.gov/publications/nistpubs/800-145/SP800-145.pdf

[2] Harauz J, Kaufman L M, Potter B. Data security in the world of cloud computing. IEEE Security & Privacy, 2009, 7(4): 61-64.

[3] Gentry C. Computing arbitrary functions of encrypted data. Communications of the ACM, 2010, 53(3): 97-105.

[4] Boneh D, Crescenzo G D, Ostrovsky R, Persiano G. Public key encryption with keyword search. In Proc. EUROCRYPT 2004, May 2004, pp.506-522.

[5] Boneh D, Kushilevitz E, Ostrovsky R, Skeith W. Publickey encryption that allows PIR queries. In Proc. the 27th CRYPTO, Aug. 2007, pp.50-67.

[6] Boneh D, Waters B. Conjunctive, subset, and range queries on encrypted data. In Proc. the 4th Theory of Cryptography Conference, Feb. 2007, pp.535-554.

[7] Bringer J, Chabanne H, Kindarji B. Error-tolerant searchable encryption. In Proc. the IEEE International Conference on Communications, June 2009.

[8] Chang Y, Mitzenmacher M. Privacy preserving keyword searches on remote encrypted data. In Proc. the 3rd Int. Conf. Applied Cryptography and Network Security, June 2005, pp.442-455.

[9] Curtmola R, Garay J, Kamara S, Ostrovsky R. Searchable symmetric encryption: Improved definitions and efficient constructions. J. Computer Security, 2011, 19(5): 895-934.

[10] Goh E. Secure indexes. IACR ePrint Cryptography Archive, 2003. http://eprint.iacr.org/2003/216, Dec. 2013.

[11] Li J,Wang Q,Wang C, Cao N, Ren K, Lou W. Fuzzy keyword search over encrypted data in cloud computing. In Proc. the 29th IEEE INFOCOM, March 2010, pp.441-445.

[12] Ma S, Yang B, Li K, Xia F. A privacy-preserving join on outsourced database. In Proc. the 14th Information Security Conference, Oct. 2011, pp.278-292.

[13] Park D, Kim K, Lee P. Public key encryption with conjunctive field keyword search. In Proc. the 5th Int. Workshop on Information Security Applications, Aug. 2004, pp.73-86.

[14] Pinkas B, Reinman T. Oblivious RAM revisited. In Proc. the 30th CRYPT, Aug. 2010, pp.502-519.

[15] Shi E, Bethencourt J, Chan T et al. Multi-dimensional range query over encrypted data. In Proc. the 2007 IEEE Symp. Security and Privacy, May 2007, pp.350-364.

[16] Song D,Wagner D, Perrig A. Practical techniques for searches on encrypted data. In Proc. the 2000 IEEE Symposium on Security and Privacy, May 2000, pp.44-55.

[17] van Liesdonk P, Sedghi S, Doumen J et al. Computationally efficient searchable symmetric encryption. In Proc. the 7th VLDB Workshop. Secure Data Management, Sept. 2010, pp. 87-100.

[18] Pang X, Yang B, Huang Q. Privacy-preserving noisy keyword search in cloud computing. In Proc. the 14th Int. Conf. Information and Communications Security, October 2012, pp.154-166.

[19] Goldreich O, Ostrovsky R. Software protection and simulation on oblivious RAMS. Journal of the ACM, 1996, 43(3): 431-473.

[20] Dodis Y, Ostrovsky R, Reyzin L, Smith A. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM Journal of Computing, 2008, 38(1): 97-139.
No related articles found!
Full text



[1] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[2] Shen Li;. Testability Analysis at Switch Level for CMOS Circuits[J]. , 1990, 5(2): 197 -202 .
[3] Sibabrata RAY; JIANG Hong;. Reconfigurable Optical Bus and Performance Optimization[J]. , 1996, 11(3): 296 -312 .
[4] Xue Jinyun;. Unified Approach for Developing EfficientAlgorithmic Programs[J]. , 1997, 12(4): 314 -329 .
[5] WANG Xiaodong; XU Ming; ZHOU Xingming;. Fast Multicast on Multistage Interconnection Networks Using Multi-Head Worms[J]. , 1999, 14(3): 250 -258 .
[6] WU Xunwei; Massoud Pedram;. Bounded Algebra and Current-Mode Digital Circuits[J]. , 1999, 14(6): 551 -557 .
[7] SUN Yongqiang; LIN Kai; LU Chaojun;. Partial Completion of Equational Theories[J]. , 2000, 15(6): 552 -559 .
[8] Sheng Li and Tie-Jun Zhao. Chinese Information Processing and Its Prospects[J]. , 2006, 21(5): 838 -846 .
[9] Dong-Xi Liu. CSchema: A Downgrading Policy Language for XML Access Control[J]. , 2007, 22(1): 44 -53 .
[10] Huanyu Zhao, Student Member, IEEE, and Xiaolin Li, Member, ACM, IEEE. H-Trust: A Group Trust Management System for Peer-to-Peer Desktop Grid[J]. , 2009, 24(5): 833 -843 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved