Public Key Encryption with Delegated Equality Test in a Multi-User Setting

Probabilistic public key encryption with equality test (PKEET), introduced by Yang et al. in CT-RSA 2010, is able to check whether two ciphertexts are encryptions of the same message under different public keys without leaking anything else about the message encrypted under either public key. PKEET schemes have many applications, for example, in constructing searchable encryption and partitioning encrypted data. Previous PKEET schemes lack a delegation mechanism for users to specify who can perform the equality test between their ciphertexts. In this paper, we propose the notion of public key encryption with delegated equality test (PKE-DET), which requires only the delegated party to deal with the work in a practical multi-user setting, and present a concrete construction in Type 2 pairing, which is provably secure under the newly introduced security notions.