On the security of the CLSV PAEKS scheme

Abstract Calderini, Longo, Sala and Villa (Journal of Mathematical Cryptology 2024) proposed a public key encryption with keyword search (PKES) scheme which we call the CLSV scheme. They claim that the scheme provides Ciphertext-Indistinguishability (CI) security where no keyword information is leaked from ciphertexts. In this paper, we demonstrate a concrete attack that obtains keyword information from ciphertexts. We point out that a ciphertext of the CLSV scheme is an ElGamal ciphertext, which is malleable. By employing the malleability, we propose a ciphertext-trapdoor conversion algorithm that allows an CI adversary to generate a trapdoor for the challenge keyword without using the receiver’s secret key. We note that our attack follows a security model called full CI security, i.e., the attack needs an active adversary, and lies outside CI security considered in the CLSV paper. Thus, we do not claim to break the CLSV scheme. Due to this situation, we evaluate the validity of our attack model in light of the design objectives of the CLSV scheme. We also analyze the attack complexity, and show that our attack completes about 100 ms.