Paper 2014/609

Public-Key Encryption Indistinguishable Under Plaintext-Checkable Attacks

Michel Abdalla and Fabrice Benhamouda and David Pointcheval

Abstract

Indistinguishability under adaptive chosen-ciphertext attack (INDCCA) is now considered the de facto security notion for public-key encryption. However, the security guarantee that it offers is sometimes stronger than what is needed by certain applications. In this paper, we consider a weaker notion of security for public-key encryption, termed indistinguishability under plaintext-checking attacks (INDPCA), in which the adversary is only given access to an oracle which says whether or not a given ciphertext encrypts a given message. After formalizing the INDPCA notion, we then design a new public-key encryption scheme satisfying it. The new scheme is a more efficient variant of the Cramer-Shoup encryption scheme with shorter ciphertexts and its security is also based on the plain Decisional Diffie-Hellman (DDH) assumption. Additionally, the algebraic properties of the new scheme also allow for proving plaintext knowledge using Groth-Sahai non-interactive zero-knowledge proofs or smooth projective hash functions. Finally, in order to illustrate the usefulness of the new scheme, we further show that, for many password-based authenticated key exchange (PAKE) schemes in the Bellare-Pointcheval-Rogaway security model, one can safely replace the underlying INDCCA encryption schemes with our new INDPCA one. By doing so, we were able to reduce the overall communication complexity of these protocols and obtain the most efficient PAKE schemes to date based on the plain DDH assumption.

Note: version 2015-01-16: new title, published in PKC 2015; version 2014-08-15: added missing references