Public key authenticated searchable encryption against frequency analysis attacks

To retrieve data in form of encryption, Boneh et al. proposed a primitive called the public key encryption with keyword search (PEKS). Unfortunately, PEKS is inherently vulnerable to the keyword guessing attack (KGA). To resist such an attack, Huang et al. introduced an authenticated version of PEKS (i.e., PAEKS), in which the sender not only encrypts the keyword, but also uses his/her secret key to authenticate it. Since then, many PAEKS schemes have emerged to improve the security model of the PAEKS system. However, none of these PAEKS schemes consider frequency analysis attacks (FAA). This attack works by tabulating the frequency distribution of trapdoors generated by user when searching, i.e., placing trapdoors embedded with the same keyword in the same category and recording the number of trapdoors in each category. These frequencies are then compared with the priori knowledge of the frequency of keyword searched by user to extract the keyword embedded in the trapdoor, thereby corrupting the user's search privacy.This work formally analyzes how frequency analysis attacks lead to the leakage of keyword information of the trapdoor in the PAEKS system. Then, to resist against this attack, we propose the first PAEKS scheme with frequency analysis attack resistance to protect the user's search privacy. In order to simplify the management of the sender/receiver's public keys, we further propose our second PAEKS scheme based on the first scheme. Finally, we show that both of these two schemes are proven secure under static assumptions.