Privacy leakage of certificateless public key authenticated searchable encryption via frequency analysis: Attacks and revises

Certificateless public key authenticated searchable encryption (CLPASE) is a versatile asymmetric searchable encryption that enables ciphertext retrieval, resists inside keyword guessing attacks, and avoids both certificate management problem and key escrow problem. However, most existing CLPASE schemes are vulnerable to frequency analysis which can extract keywords from user-generated trapdoors (i.e., search queries) and thus compromise user's search privacy. In this paper, we give a detailed analysis showing that most CLPASE schemes reveal the underlying frequency distribution of the target keywords in the trapdoors searched by users, regardless of whether the trapdoor generation algorithm is deterministic or not. The analysis shows that frequency analysis has become a significant threat to users' search privacy in the CLPASE system. To address this issue, we provide a concrete CLPASE scheme against frequency analysis. We then compare our scheme with previous CLPASE schemes in terms of features and performance evaluation. As a result, our scheme provides higher guarantee for user's search privacy with comparable efficiency.