Efficient All-or-Nothing Public Key Encryption with Authenticated Equality Test

Public key encryption with equality test (PKEET for short) is a new cryptographic primitive which allows a proxy to check whether two ciphertexts encrypted under different public keys are of the same plaintext. PKEET has become a prospective candidate for various application scenarios, such as data management on encrypted databases, personal health record systems, spam filtering in encrypted email systems. In this paper, we propose an efficient all-or-nothing public key encryption scheme with authenticated equality test (AoN-PKEAET for short). In comparison with the existing PKEET schemes, the proposed scheme provides a new feature of ciphertext authentication before the plaintext equality test. It ensures that no misjudgement occurs when testing the equality between ciphertexts. Specially, the mathsf Test algorithm in the proposed scheme first authenticates the compared ciphertexts and the equality test is fulfilled only if the ciphertexts are authenticated as valid. With this new feature, the mathsf Test algorithm cannot output 0 (which means that the encrypted messages are different) when the two input ciphertexts are of an identical message, or it cannot output 1 (which means that the encrypted messages are identical) when the two input ciphertexts are of different messages. Under a redefined security model for AoN-PKEAET, we give the detailed security proof of the proposed scheme.