An Efficient and Generic Construction of Public Key Encryption With Equality Test Under the Random Oracle Model

Abstract

Public key encryption with equality test (PKE-ET) facilitates authorized entities in distinguishing if two ciphertexts involve the identical underlying message. This functionality has driven its adoption across various applications, such as secure data management in cloud environments, encrypted spam filtering, and keyword searches in encrypted databases. However, existing generic PKE-ET constructions often rely on cryptographic primitives that require strong security assumptions or additional complex functionalities, leading to inefficiencies. This paper proposes an improved generic construction for PKE-ET under the random oracle model. The proposed method leverages only fundamental cryptographic building blocks, relying exclusively on a standard public key encryption (PKE) scheme along with cryptographic hash functions, without requiring additional complex primitives. More concretely, the proposed construction leverages a PKE scheme that ensures one-wayness against chosen plaintext attacks (OW-CPA), differing from earlier generic frameworks that necessitate stronger security guarantees. We demonstrate that the proposed construction satisfies one-wayness against adaptively chosen ciphertext attacks (OW-CCA2) for a Type-1 adversary-who possesses equality test trapdoors-and indistinguishability against adaptively chosen ciphertext attacks (IND-CCA2) for a Type-2 adversary-who lacks such trapdoors-assuming that the exploited PKE scheme achieves OW-CPA security. Furthermore, we present three concrete instantiations of our generic framework using well-established PKE schemes: The hashed ElGamal encryption, the RSA encryption, and the BIKE cryptosystem. These instantiations offer notable advantages over existing PKE-ET designs. The first two constructions enhance efficiency in comparison to prior schemes, while the third stands out as the first code-based PKE-ET instantiation, relying solely on code-based security assumptions.

Keywords

• Equality test
• public key encryption
• generic construction
• random oracle model
• discrete logarithm-based instantiation
• RSA-based instantiation