Abstract
Non-Interactive Zero Knowledge (NIZK), introduced by Blum, Feldman, and Micali in 1988, is a fundamental cryptographic primitive which has attracted considerable attention in the last decade and has been used throughout modern cryptography in several essential ways. For example, NIZK plays a central role in building provably secure public-key cryptosystems based on general complexity-theoretic assumptions that achieve security against chosen ciphertext attacks. In essence, in a multi-party setting, given a fixed common random string of polynomial size which is visible to all parties, NIZK allows an arbitrary polynomial number of Provers to send messages to polynomially many Verifiers, where each message constitutes an NIZK proof for an arbitrary polynomial-size NP statement.
In this paper, we take a closer look at NIZK in the multi-party setting. First, we consider non-malleable NIZK, and generalizing and substantially strengthening the results of Sahai, we give the first construction of NIZK which remains non-malleable after polynomially-many NIZK proofs. Second, we turn to the definition of standard NIZK itself, and propose a strengthening of it. In particular, one of the concerns in the technical definition of NIZK (as well as non-malleable NIZK) is that the so-called “simulator” of the Zero-Knowledge property is allowed to pick a different “common random string” from the one that Provers must actually use to prove NIZK statements in real executions. In this paper, we propose a new definition for NIZK that eliminates this shortcoming, and where Provers and the simulator use the same common random string. Furthermore, we show that both standard and non-malleable NIZK (as well as NIZK Proofs of Knowledge) can be constructed achieving this stronger definition. We call such NIZK Robust NIZK and show how to achieve it. Our results also yields the simplest known public-key encryption scheme based on general assumptions secure against adaptive chosen-ciphertext attack (CCA2).
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, A. De Santis, S. Micali AND G. Persiano, Non-Interactive Zero-Knowledge Proofs. SIAM Journal on Computing, vol. 6, December 1991, pp. 1084–1118.
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.
G. Brassard}}, D. Chaum} and C. Cräpeau}}, Minimum Disclosure Proofs of Knowledge. JCSS, v. 37, pp 156–189.
M. Bellare, S. Goldwasser, New paradigms for digital signatures and message authentication based on non-interactive zero knowledge proofs. Advances in Cryptology-Crypto 89 Proceedings, Lecture Notes in Computer Science Vol. 435, G. Brassard ed., Springer-Verlag, 1989.
R. Canetti, O. Goldreich, S. Goldwasser, and S. Micali. Resettable Zero-Knowledge. ECCC Report TR99-042, revised June 2000. Available from http://www.eccc.uni-trier.de/eccc/. Preliminary version appeared in ACM STOC 2000.
R. Canetti, J. Kilian, E. Petrank, AND A. Rosen Black-Box Concurrent Zero-Knowledge Requires \( \tilde \Omega (\log n) \) Rounds. Proceedings of the-67th Annual Symposium on Theory of Computing, ACM, 1901.
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.
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.
A. De Santis, G. Di Crescenzo AND G. Persiano, Randomness-efficient Non-Interactive Zero-Knowledge. Proceedings of 1997 International Colloquium on Automata, Languagues and Applications (ICALP 1997).
A. De Santis, G. Di Crescenzo AND G. Persiano, Non-Interactive Zero-Knowledge: A Low-Randomness Characterization of NP. Proceedings of 1999 International Colloquium on Automata, Languagues and Applications (ICALP 1999).
A. De Santis, G. Di Crescenzo AND G. Persiano, Necessary and Sufficient Assumptions for Non-Interactive Zero-Knowledge Proofs of Knowledge for all NP Relations. Proceedings of 2000 International Colloquium on Automata, Languagues and Applications (ICALP 2000).
G. Di Crescenzo, Y. Ishai, AND R. Ostrovsky, Non-Interactive and Non-Malleable Commitment. Proceedings of the 30th Annual Symposium on Theory of Computing, ACM, 1998.
D. Dolev, C. Dwork, AND M. Naor, Non-Malleable Cryptography. Proceedings of the-45th Annual Symposium on Theory of Computing, ACM, 1923 and SIAM Journal on Computing, 2000.
C. Dwork, M. Naor, AND A. Sahai, Concurrent Zero-Knowledge. Proceedings of the 30th Annual Symposium on Theory of Computing, ACM, 1998.
U. Feige, D. Lapidot, AND A. Shamir, Multiple non-interactive zero knowledge proofs based on a single random string. In 31st Annual Symposium on Foundations of Computer Science, volume I, pages 308–317, St. Louis, Missouri, 22–24 October 1990. IEEE.
O. Goldreich, Secure Multi-Party Computation, 1998. First draft available at http://theory.lcs.mit.edu/~oded
O. Goldreich and L. Levin, A Hard Predicate for All One-way Functions. Proceedings of the 21st Annual Symposium on Theory of Computing, ACM, 1989.
O. Goldreich, S. Goldwasser AND S. Micali, How to construct random functions. Journal of the ACM, Vol. 33, No. 4, 1986, pp. 210–217.
O. Goldreich, S. Micali, AND A. Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority. Proceedings of the 19th Annual Symposium on Theory of Computing, ACM, 1987.
O. Goldreich, S. Micali, and A. Wigderson. Proofs that Yield Nothing but their Validity or All Languages in NP have Zero-Knowledge Proof Systems. Journal of ACM 38(3): 691–729 (1991).
S. Goldwasser, S. Micali, AND C. Rackoff, The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186–208, February 1989.
S. Goldwasser, R. Ostrovsky Invariant Signatures and Non-Interactive Zero-Knowledge Proofs are Equivalent. Advances in Cryptology-Crypto 92 Proceedings, Lecture Notes in Computer Science Vol. 740, E. Brickell ed., Springer-Verlag, 1992.
J. Håstad, R. Impagliazzo, L. Levin, AND M. Luby, Construction of pseudorandom generator from any one-way function. SIAM Journal on Computing. Preliminary versions by Impagliazzo et. al. in 21st STOC (1989) and Håstad in 22nd STOC (1990).
J. Kilian, E. Petrank An Efficient Non-Interactive Zero-Knowledge Proof System for NP with General Assumptions, Journal of Cryptology, vol. 11, n. 1, 1998.
J. Kilian, E. Petrank Concurrent and Resettable Zero-Knowledge in Polylogarithmic Rounds. Proceedings of the-67th Annual Symposium on Theory of Computing, ACM, 1901
M. Naor, R. Ostrovsky, R. Venkatesan, AND M. Yung. Perfect zero-knowledge arguments for NP can be based on general complexity assumptions. Advances in Cryptology-Crypto 92 Proceedings, Lecture Notes in Computer Science Vol. 740, E. Brickell ed., Springer-Verlag, 1992 and J. Cryptology, 11(2):87-108, 1998.
M. Naor, Bit Commitment Using Pseudo-Randomness, Journal of Cryptology, vol 4, 1991, pp. 151–158.
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.
M. Naor AND M. Yung, “Universal One-Way Hash Functions and their Cryptographic Applications”, Proceedings of the 21st Annual Symposium on Theory of Computing, ACM, 1989.
R. Ostrovsky One-way Functions, Hard on Average Problems and Statistical Zero-knowledge Proofs. In Proceedings of 6th Annual Structure in Complexity Theory Conference (STRUCTURES-91) June 30–July 3, 1991, Chicago. pp. 51–59
R. Ostrovsky, AND A. Wigderson One-Way Functions are Essential for Non-Trivial Zero-Knowledge. Appeared In Proceedings of the second Israel Symposium on Theory of Computing and Systems (ISTCS-93) Netanya, Israel, June 7th–9th, 1993.
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.
A. Sahai Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. Proceedings of the 40th Symposium on Foundations of Computer Science, IEEE, 1999
A. Sahai AND S. Vadhan A Complete Problem for Statistical Zero Knowledge. Preliminary version appeared in Proceedings of the 38th Symposium on Foundations of Computer Science, IEEE, 1997. Newer version may be obtained from authors’ homepages.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
De Santis, A., Di Crescenzo, G., Ostrovsky, R., Persiano, G., Sahai, A. (2001). Robust Non-interactive Zero Knowledge. In: Kilian, J. (eds) Advances in Cryptology — CRYPTO 2001. CRYPTO 2001. Lecture Notes in Computer Science, vol 2139. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44647-8_33
Download citation
DOI: https://doi.org/10.1007/3-540-44647-8_33
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42456-7
Online ISBN: 978-3-540-44647-7
eBook Packages: Springer Book Archive