Abstract
The zero-knowledge proof of knowledge, first defined by Fiat, Fiege and Shamir, was used by Galil, Haber and Yung as a means of constructing (out of a trapdoor function) an interactive public-key cryptosystem provably secure against chosen ciphertext attack. We introduce a revised setting which permits the definition of a non-interactive analogue, the non-interactive zero-knowledge proof of knowledge, and show how it may be constructed in that setting from a non-interactive zero-knowledge proof system for N P (of the type introduced by Blum, Feldman and Micali). We give a formalization of chosen ciphertext attack in our model which is stronger than the “lunchtime attack” considered by Naor and Yung, and prove a non-interactive public-key cryptosystem based on non-interactive zero-knowledge proof of knowledge to be secure against it.
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. Blum, P. Feldman, and S. Micali, Non-Interactive Zero Knowledge and its Applications, Proc. 20th ACM Symposium on Theory of Computing (1988), pp. 103–112.
M. Bellare and S. Goldwasser, New Paradigms for Digital signatures and Message Authentication based on Non-Interactive Zero-Knowledge Proofs, Proc. CRYPTO’ 89.
D. Dolev, C. Dwork and M. Naor, Non-Malleable Cryptography, Proc. 23rd ACM Symposium on Theory of Computing (1991), pp. 542–552.
W. Diffie and M. Hellman, New directions in Cryptography, IEEE Trans. on Information Theory 22(6), 1976, pp. 644–654.
A. De Santis and M. Yung, Cryptographic Applications of the Non-Interactive Metaproof and Many-Prover Systems, Proc. CRYPTO’ 90.
U. Feige, A. Fiat, and A. Shamir, Zero Knowledge Proofs of Identity, Proc. 19th ACM Symp. on Theory of Computing (1987), pp. 210–217.
U. Feige, D. Lapidot and A. Shamir, Multiple Non-Interactive Zero-Knowledge Proofs Based on a Single Random String, Proc. 31st IEEE Symp. on Foundations of Computer Science (1990), pp. 308–317.
Z. Galil, S. Haber and M. Yung, Symmetric Public-Key Cryptosystems, submitted to J. of Cryptology.
S. Goldwasser and S. Micali, Probabilistic Encryption, JCSS Vol. 28, No. 2 (April 1984), pp. 270–299.
S. Goldwasser, S. Micali and C. Rackoff, The Knowledge Complexity of Interactive Proof Systems, Proc. 17th ACM Symp. on Theory of Computing (1985), pp. 291–304.
S. Goldwasser, S. Micali and R. Rivest, A Secure Digital Signature Scheme, SIAM J. on Computing, Vol. 17,2 (1988), pp. 281–308.
M. Naor and M. Yung, Public-Key Cryptosystems Provably Secure Against Chosen Ciphertext Attacks, Proc. 22nd ACM Symp on Theory of Computing (1990), pp. 427–437.
J. Rompel, One-Way Functions Are Necessary and Sufficient for Secure Signatures, Proc. 31st IEEE Symp. on Foundations of Computer Science (1990), pp. 387–394.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rackoff, C., Simon, D.R. (1992). Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack. In: Feigenbaum, J. (eds) Advances in Cryptology — CRYPTO ’91. CRYPTO 1991. Lecture Notes in Computer Science, vol 576. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46766-1_35
Download citation
DOI: https://doi.org/10.1007/3-540-46766-1_35
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-55188-1
Online ISBN: 978-3-540-46766-3
eBook Packages: Springer Book Archive