Boneh et al. proposed the cryptographic primitive public key encryption with keyword search (PEKS) to search on encrypted data without exposing the privacy of the keyword. Most standard PEKS schemes are vulnerable to inside keyword guessing attacks (KGA), i.e., a malicious server may generate a ciphertext by its own and then to guess the keyword of the trapdoor by testing.
Huang et al. solved this problem by proposing the public-key authenticated encryption with keyword search (PAEKS) achieving single trapdoor indistinguishability (TI).

Certificateless public-key authenticated encryption with keyword search (CLPAEKS) is first formally proposed by He et al. as a combination of the Huang’s PAEKS and the certificateless public key cryptography (CLPKC). Lin et al. revised He’s work and re-formalize the security requirements for CLPAEKS in terms of both trapdoor indistinguishability and ciphertext indistinguishability.
However, trapdoor generation algorithms of all above works are deterministic. In this case, given two trapdoors, it’s obviously to check whether the target keywords are identical embedded in them. This feature conflicts with trapdoor indistinguishability security.

In this paper, we initially propose a CLPAEKS scheme with probabilistic trapdoor generation. Formal proof shows that our scheme is provable secure in the random oracle model.

By admin