Paper 2006/228

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

Mihir Bellare and Amit Sahai

Abstract

We prove the equivalence of two definitions of non-malleable encryption, one based on the simulation approach of Dolev, Dwork and Naor and the other based on the comparison approach of Bellare, Desai, Pointcheval and Rogaway. Our definitions are slightly stronger than the original ones. 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.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. A preliminary version appeared in CRYPTO 99. This full version corrects some mistakes from the preliminary version.
Contact author(s)
mihir @ cs ucsd edu
History
2006-07-15: last of 5 revisions
2006-07-06: received
See all versions
Short URL
https://ia.cr/2006/228
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/228,
      author = {Mihir Bellare and Amit Sahai},
      title = {Non-Malleable Encryption: Equivalence between Two Notions, and an Indistinguishability-based Characterization},
      howpublished = {Cryptology ePrint Archive, Paper 2006/228},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/228}},
      url = {https://eprint.iacr.org/2006/228}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.