An Efficient Attack on A Fuzzy Keyword Search Scheme over Encrypted Data

Ciphertext searchability is a promising method to securely store and retrieve outsourced data, like in secure cloud storage. But it is still hard to do fuzzy keyword search over outsourced ciphertexts. In INFOCOM 2010, Li et al. [1] proposed a fuzzy keyword search scheme over encrypted data based on edit distance [2]. However, we find that their scheme is insecure. In this paper, we construct a special adversary to break the provable security reduction of their scheme. In theory, the main reason of the insecurity is caused by the independency of the indexes generated for different keywords. So an adversary can break the provable security according to some possessed messages learned from history interaction in the provable security.