Public key encryption with equality test from generic assumptions in the random oracle model

Abstract

Public key encryption with equality test (PKEET) is a variant of classical public key encryption (PKE) with the special functionality of an equality test, and can be used in many applications such as in keyword search on encrypted data and for efficient management by partitioning encrypted data in the cloud. Since the original proposal of Yang et al. (CT-RSA, 2010), several subsequent proposals to improve the efficiency or functionality of PKEET have been reported. We present a PKEET construction from generic assumptions in the random oracle model. In particular, whereas previous results require number-theoretic assumptions or strictly stronger generic assumptions such as the existence of secure hierarchical identity-based encryption, our proposal requires only the existence of cryptographic hash functions and secure PKE schemes satisfying a special property, called randomness extractability. Informally, randomness extractability means that one can recover the randomness used in a ciphertext when given a secret key corresponding to a public key for the ciphertext. We investigate the fact that PKE schemes satisfying this property can be designed by the Fujisaki-Okamoto (FO) transformation, which is the widely utilized method to obtain secure PKE schemes from basic cryptographic primitives in the random oracle model. As a result, in combination with the FO transformation, we obtain a PKEET construction in the random oracle model if there exist a one-way PKE scheme, a one-time secure symmetric key encryption scheme, collision-resistant and one-way hash functions, and a pseudorandom function. In this sense, we remark that our PKEET construction is derived from fundamental generic assumptions only.