## Non-Malleable Encryption: Equivalence between Two
Notions, and an Indistinguishability-Based Characterization

** Authors: M. Bellare and A. Sahai **
** Abstract: ** We prove the equivalence of two definitions of non-malleable
encryption appearing in the literature--- the original one of Dolev, Dwork
and Naor and the later one of Bellare, Desai, Pointcheval and Rogaway. The
equivalence relies on a new characterization of non-malleable encryption in
terms of the standard notion of indistinguishability of Goldwasser and
Micali. We show that non-malleability is equivalent to indistinguishability
under a ``parallel chosen ciphertext attack,'' this being a new kind of
chosen ciphertext attack we introduce, in which the adversary's decryption
queries are not allowed to depend on answers to previous queries, but must be
made all at once. This characterization simplifies both the notion of
non-malleable encryption and its usage, and enables one to see more easily
how it compares with other notions of encryption. The results here apply to
non-malleable encryption under any form of attack, whether chosen-plaintext,
chosen-ciphertext, or adaptive chosen-ciphertext.

** Ref:** Extended abstract in Advances in Cryptology - Crypto 99
Proceedings, Lecture Notes in Computer Science Vol. 1666, M. Wiener ed,
Springer-Verlag, 1999. Full paper available below. Last revised July
2006 to correct some mistakes from the preliminary version.

** Full paper: ** Available as compressed
postscript, postscript, or
pdf. ( Help if this doesn't work).