An error‐tolerant keyword search scheme based on public‐key encryption in secure cloud computing

Summary 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. An error‐tolerant keyword search scheme can be generated based on a public‐key encryption scheme, in which anyone with access to a user's public key can generate the trapdoors and indexes to keywords, and only the user holding the decryption key can obtain the records it retrieves. In this paper, we first present a general framework for searching on error‐tolerant keywords based on a public‐key encryption scheme. Then, we propose a concrete scheme based on the Cramer–Shoup cryptosystem. The scheme is adaptive chosen‐ciphertext attack secure and suitable for all similarity metrics including Hamming distance metric, edit distance metric, and set difference metric. It does not require the user to construct and store anything in advance, other than the cryptosystem used to calculate the trapdoor of keywords and 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 searching for exact keywords on plaintexts. The server can use any existing approaches of exact keywords search to search plaintexts on an index table. Copyright © 2015 John Wiley & Sons, Ltd.