Abstract
The public-key model for interactive proofs has proved to be quite effective in improving protocol efficiency [CGGM00]. We argue, however, that its soundness notion is more subtle and complex than in the classical model, and that it should be better understood to avoid designing erroneous protocols. Specifically, for the public-key model, we
-
identify four meaningful notions of soundness;
-
prove that, under minimal complexity assumptions, these four notions are distinct;
-
identify the exact soundness notions satisfied by prior interactive protocols; and
-
identify the round complexity of some of the new notions.
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
Gilles Brassard, David Chaum, and Claude Crépeau. Minimum disclosure proofs of knowledge. Journal of Computer and System Sciences, 37(2):156–189, October 1988.
Manuel Blum, Alfredo De Santis, Silvio Micali, and Giuseppe Persiano. Noninteractive zero-knowledge. SIAM Journal on Computing, 20(6):1084–1118, December 1991.
Manuel Blum, Paul Feldman, and Silvio Micali. Non-interactive zero-knowledge and its applications (extended abstract). In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 103–112, Chicago, Illinois, 2–4 May 1988.
Manuel Blum. How to prove a theorem so no one else can claim it. In Proc. of the International Congress of Mathematicians, Berkeley, CA, pages 1444–1451, 1986.
Ran Canetti, Oded Goldreich, Shafi Goldwasser, and Silvio Micali. Resettable zero-knowledge. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, Portland, Oregon, 21–23 May 2000. Updated version available at the Cryptology ePrint Archive, record 1999/022, http://eprint.iacr.org/.
Ran Canetti, Joe Kilian, Erez Petrank, and Alon Rosen. Black-box concurrent zero-knowledge requires \( \tilde \Omega (\log n) \) rounds. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, Crete, Greece, 6–8 July 2001.
Cynthia Dwork, Moni Naor, and Amit Sahai. Concurrent zero knowledge. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pages 409–418, Dallas, Texas, 23–26 May 1998.
Uriel Feige, Dror Lapidot, and Adi Shamir. Multiple non-interactive zero knowledge proofs under general assumptions. SIAM Journal on Computing, 29(1):1–28, 1999.
Uriel Feige and Adi Shamir. Zero knowledge proofs of knowledge in two rounds. In G. Brassard, editor, Advances in Cryptology—CRYPTO’ 89, volume 435 of Lecture Notes in Computer Science, pages 526–545. Springer-Verlag, 1990, 20–24 August 1989.
Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. Journal of the ACM, 33(4):792–807, October 1986.
Oded Goldreich and Hugo Krawczyk. On the composition of zero-knowledge proof systems. SIAM Journal on Computing, 25(1):169–192, February 1996.
O. Goldreich and L. Levin. A hard-core predicate for all one-way functions. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 25–32, Seattle, Washington, 15–17 May 1989.
S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270–299, April 1984.
Shafi Goldwasser, Silvio Micali, and Ronald L. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on Computing, 17(2):281–308, April 1988.
Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18:186–208, 1989.
Oded Goldreich and Yair Oren. Definitions and properties of zero-knowledge proof systems. Journal of Cryptology, 7(1):1–32, 1994.
J. Håstad, R. Impagliazzo, L.A. Levin, and M. Luby. Construction of pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4):1364–1396, 1999.
Silvio Micali and Leonid Reyzin. Min-round resettable zero knowledge in the public-key model. In Birgit Pfitzmann, editor, Advances in Cryptology—EUROCRYPT 2001, volume 2045 of Lecture Notes in Computer Science, pages 373–393. Springer-Verlag, 6–10 May 2001.
Silvio Micali, Michael Rabin, and Salil Vadhan. Verifiable random functions. In 40th Annual Symposium on Foundations of Computer Science, pages 120–130, New York, October 1999. IEEE.
John Rompel. One-way functions are necessary and sufficient for secure signatures. In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 387–394, Baltimore, Maryland, 14–16 May 1990.
A. C. Yao. Theory and application of trapdoor functions. In 23rd Annual Symposium on Foundations of Computer Science, pages 80–91, Chicago, Illinois, 3–5 November 1982. IEEE.
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
Micali, S., Reyzin, L. (2001). Soundness in the Public-Key Model. 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_32
Download citation
DOI: https://doi.org/10.1007/3-540-44647-8_32
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