Abstract
We compare the relative strengths of popular notions of security for public key encryption schemes. We consider the goals of privacy and non-malleability, each under chosen plaintext attack and two kinds of chosen ciphertext attack. For each of the resulting pairs of definitions we prove either an implication (every scheme meeting one notion must meet the other) or a separation (there is a scheme meeting one notion but not the other, assuming the first notion can be met at all). We similarly treat plaintext awareness, a notion of security in the random oracle model. An additional contribution of this paper is a new definition of non-malleability which we believe is simpler than the previous one.
Chapter PDF
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. Pull version of this paper, available via http://www-cse.ucsd.edu/users/mihir/
M. Bellare and P. Rogaway, Random oracles are practical: a paradigm for designing efficient protocols. First ACM Conference on Computer and Communications Security, ACM, 1993.
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.
M. Bellare and A. Sahai, private communication, May 1998.
D. Bleichenbacher, A chosen ciphertext attack against protocols based on the RSA encryption standard PKCS #1, Advances in Cryptology — CRYPTO '98 Proceedings, Lecture Notes in Computer Science, H. Krawczyk, ed., Springer-Verlag 1998.
M. Blum, P. Feldman and S. Micali, Non-interactive zero-knowledge and its applications. Proceedings of the 20th Annual Symposium on Theory of Computing, ACM, 1988.
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, H. Krawczyk, ed., Springer-Verlag 1998.
I. Damgård, Towards practical public key cryptosystems secure against chosen ciphertext attacks. Advances in Cryptology — Crypto 91 Proceedings, Lecture Notes in Computer Science Vol. 576, J. Feigenbaum ed., Springer-Verlag, 1991.
A. De Santis and G. Persiano, Zero-knowledge proofs of knowledge without interaction. Proceedings of the 33rd Symposium on Foundations of Computer Science, IEEE, 1992.
D. Dolev, C. Dwork, and M. Naor, Non-malleable cryptography. Proceedings of the 23rd Annual Symposium on Theory of Computing, ACM, 1991.
D. Dolev, C. Dwork, and M. Naor, Non-malleable cryptography. 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.
Z. Galil, S. Haber and M. Yung, Symmetric public key encryption. Advances in Cryptology — Crypto 85 Proceedings, Lecture Notes in Computer Science Vol. 218, H. Williams ed., Springer-Verlag, 1985.
Z. Galil, S. Haber and M. Yung, Security against replay chosen ciphertext attack. Distributed Computing and Cryptography, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 2, ACM, 1991.
S. Goldwasser and S. Micali, Probabilistic encryption. Journal of Computer and System Sciences, 28:270–299, 1984.
O. Goldreich, S. Goldwasser and S. Micali, How to construct random functions. Journal of the ACM, Vol. 33, No. 4, 1986, pp. 210–217.
J. Håstad, R. Impagliazzo, L. Levin and M. Luby, Construction of a pseudo-random generator from any one-way function. Manuscript. Earlier versions in STOC 89 and STOC 90.
R. Impagliazzo and M. Luby, One-way functions are essential for complexity based cryptography. Proceedings of the 30th Symposium on Foundations of Computer Science, IEEE, 1989.
S. Micali, C. Rackoff and R. Sloan, The notion of security for probabilistic cryptosystems. SIAM J. of Computing, April 1988.
M. Naor, private communication, March 1998.
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/
Y. Zheng and J. Seberry, Immunizing public key cryptosystems against chosen ciphertext attack. IEEE Journal on Selected Areas in Communications, vol. 11, no. 5, 715–724 (1993).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bellare, M., Desai, A., Pointcheval, D., Rogaway, P. (1998). Relations among notions of security for public-key encryption schemes. In: Krawczyk, H. (eds) Advances in Cryptology — CRYPTO '98. CRYPTO 1998. Lecture Notes in Computer Science, vol 1462. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0055718
Download citation
DOI: https://doi.org/10.1007/BFb0055718
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64892-5
Online ISBN: 978-3-540-68462-6
eBook Packages: Springer Book Archive
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.