Paper 1999/018
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 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.
Metadata
- Available format(s)
- PS
- Publication info
- Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
- Keywords
- Asymmetric encryptionNon-malleabilityIndistinguishabilityequivalence between notionssemantic security.
- Contact author(s)
- mihir @ cs ucsd edu
- History
- 1999-07-28: received
- Short URL
- https://ia.cr/1999/018
- License
-
CC BY
BibTeX
@misc{cryptoeprint:1999/018,
author = {Mihir Bellare and Amit Sahai},
title = {Non-Malleable Encryption: Equivalence between Two Notions, and an Indistinguishability-Based Characterization},
howpublished = {Cryptology ePrint Archive, Paper 1999/018},
year = {1999},
note = {\url{https://eprint.iacr.org/1999/018}},
url = {https://eprint.iacr.org/1999/018}
}
