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 Gold-wasser and Micali. We show that non-malleability is equivalent to in-distinguishability 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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
M. Bellare, R. Canetti and H. Krawczyk, A modular approach to the design and analysis of authentication and key exchange protocols. Proceedings of the 30th Annual Symposium on Theory of Computing, ACM, 1998.
M. Bellare, A. Desai, D. Pointcheval and P. Rogaway, Relations among notions of security for public-key encryption schemes. Advances in Cryptology-Crypto 98 Proceedings, Lecture Notes in Computer Science Vol. 1462, H. Krawczyk ed., Springer-Verlag, 1998.
M. Bellare and P. Rogaway, Optimal asymmetric encryption-How to encrypt with RSA. Advances in Cryptology-Eurocrypt 94 Proceedings, Lecture Notes in Computer Science Vol. 950, A. De Santis ed., Springer-Verlag, 1994.
R. Cramer and V. Shoup, A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. Advances in Cryptology-Crypto 98 Proceedings, Lecture Notes in Computer Science Vol. 1462, H. Krawczyk ed., Springer-Verlag, 1998.
D. Dolev, C. Dwork, and M. Naor, Non-malleable cryptography. Proceedings of the 23rd Annual Symposium on Theory of Computing, ACM, 1991. Also Technical Report CS95-27, Weizmann Institute of Science, 1995.
D. Dolev, C. Dwork, and M. Naor, Non-malleable cryptography. Manuscript, 1998.
O. Goldreich, A uniform complexity treatment of encryption and zero-knowledge. Journal of Cryptology, Vol. 6, 1993, pp. 21–53.
S. Goldwasser and S. Micali, Probabilistic encryption. Journal of Computer and System Sciences, 28:270–299, 1984.
S. Halevi and H. Krawczyk, Public-key cryptography and password protocols. Proceedings of the Fifth Annual Conference on Computer and Communications Security, ACM, 1998.
S. Micali, C. Rackoff and R. Sloan, The notion of security for probabilistic cryptosystems. SIAM J. of Computing, April 1988.
M. Naor and M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks. Proceedings of the 22nd Annual Symposium on Theory of Computing, ACM, 1990.
C. Rackoff and D. Simon, Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack. Advances in Cryptology-Crypto 91 Proceedings, Lecture Notes in Computer Science Vol. 576, J. Feigenbaum ed., Springer-Verlag, 1991.
SETCo (Secure Electronic Transaction LLC), The SET standard — book 3 — formal protocol definitions (version 1.0). May 31, 1997. Available from http://www.setco.org/
A. Yao, Theory and applications of trapdoor functions. Proceedings of the 23rd Symposium on Foundations of Computer Science, IEEE, 1982.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bellare, M., Sahai, A. (1999). Non-malleable Encryption: Equivalence between Two Notions, and an Indistinguishability-Based Characterization. In: Wiener, M. (eds) Advances in Cryptology — CRYPTO’ 99. CRYPTO 1999. Lecture Notes in Computer Science, vol 1666. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48405-1_33
Download citation
DOI: https://doi.org/10.1007/3-540-48405-1_33
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66347-8
Online ISBN: 978-3-540-48405-9
eBook Packages: Springer Book Archive