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

Cipher text search ability 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 cipher texts. 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.