Efficient Public Key Encryption With Equality Test Supporting Flexible Authorization

We reformalize and recast the notion of public key encryption with equality test (PKEET), which was proposed in CT-RSA 2010 and supports to check whether two ciphertexts encrypted under different public keys contain the same message. PKEET has many interesting applications, for example, in constructing searchable encryption and partitioning encrypted data. However, the original PKEET scheme lacks an authorization mechanism for a user to control the comparison of its ciphertexts with others’. In this paper, we study the authorization mechanism for PKEET, and propose four types of authorization policies to enhance the privacy of users’ data. We give the definitions of the policies, propose a PKEET scheme supporting these four types of authorization at the same time, and prove its security based on the computational Diffie–Hellman assumption in the random oracle model. To the best of our knowledge, it is the only PKEET scheme supporting flexible authorization.

I. Introduction

Public key encryption with equality test (PKEET), introduced by Yang et al. in CT-RSA 2010 [23], is a special kind of public key encryption (PKE) which allows to check whether two ciphertexts encrypted under (possibly) different public keys contain the same message. PKEET has many interesting applications. For example, consider the following scenario. All users send encrypted emails to Alice using Alice’s public key, which include both the encrypted email contents and the encrypted keywords. There is an email security monitor responsible for generating sensitive keywords in order to test whether they are contained in the emails. In the cloud era, these sensitive keywords are also encrypted and stored in the remote cloud email server for security and privacy concerns. It should be guaranteed that the cloud email server can search for whether the sensitive keywords are contained in the emails, but learn neither the sensitive keywords nor the email contents. To do so, the emails are encrypted using a standard public key encryption system and then are appended with a PKEET ciphertext of each keyword. To send a message with keywords to Alice, the following ciphertext is generated:

$$\begin{equation*} Enc(pk_{A}, M) \| \text {PKEET}(pk_{A},W_{1}) \| \cdots \| \text {PKEET}(pk_{A},W_{n}), \end{equation*}$$ where is Alice’s public key. PKEET enables the cloud email server to test whether any of the keywords associated with is equal to a specific keyword , which is encrypted using the email security monitor’s public key and stored in the cloud email server. Note that Alice and the email security monitor do not communicate in the entire process.