Public key encryption with keyword search and keyword guessing attack: a survey

Searchable encryption is a cryptographic notion which enables users to perform secure searches over encrypted data stored on an untrusted server. Searchable encryption techniques can be divided into two main categories: searchable symmetric encryption (SSE) and public key encryption with keyword search (PEKS). Unlike SSE techniques, PEKS methods are vulnerable to keyword guessing attack wherein an attacker first generates encrypted tags corresponding to all possible keywords. Then, by accessing a trapdoor, a match can be found and therefore the searched keyword and the files containing it can be determined. The feasibility of the attack stems from the fact that the space from which keywords are chosen is small in practice. In this paper, after reviewing the concept of searchable encryption, the description of keyword guessing attack and the vulnerability of PEKS schemes to such attacks are discussed. The paper then proceeds to provide an overall picture of the attempts made to overcome this drawback. Finally, open problems and future work directions in this area are addressed.