Paper 2014/609

Structure-Preserving Encryption Indistinguishable Under Plaintext-Checkable Attacks

Michel Abdalla and Fabrice Benhamouda and David Pointcheval

Abstract

Even though indistinguishability under adaptive chosen-ciphertext attack (INDCCA) is now considered the \emph{de facto} security notion for public-key encryption, the security guarantees 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. Moreover, the new scheme is also structure-preserving and hence can also be used with Groth-Sahai non-interactive zero-knowledge proofs and 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 2014-08-15: added missing references