Min-round Resettable Zero-Knowledge in the Public-Key Model

  • Silvio Micali
  • Leonid Reyzin
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2045)


In STOC 2000, Canetti, Goldreich, Goldwasser, and Micali put forward the strongest notion of zero-knowledge to date, resettable zero-knowledge (RZK) and implemented it in constant rounds in a new model, where the verifier simply has a public key registered before any interaction with the prover.

To achieve ultimate round efficiency, we advocate a slightly stronger model. Informally, we show that, as long as the honest verifier does not use a given public key more than a fixed-polynomial number of times, there exist 3-round (which we prove optimal) RZK protocols for all of NP.


Security Parameter Random String Commitment Scheme Pseudorandom Function Oracle Access 
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.


  1. BCC88.
    G. Brassard, D. Chaum, and C. Crépeau. Minimum disclosure proofs of knowledge. Journal of Computer and System Sciences, 37(2):156–189, 1988.zbMATHCrossRefMathSciNetGoogle Scholar
  2. BDMP91.
    M. Blum, A. De Santis, S. Micali, and G. Persiano. Noninteractive zero-knowledge. SIAM Journal on Computing, 20(6):1084–1118, December 1991.zbMATHCrossRefMathSciNetGoogle Scholar
  3. BFM88.
    M. Blum, P. Feldman, and S. 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, 1988.Google Scholar
  4. Bra89.
    G. Brassard, editor. Advances in Cryptology-CRYPTO '89, volume 435 of Lecture Notes in Computer Science. Springer-Verlag, 1990.zbMATHGoogle Scholar
  5. CGGM00.
    R. Canetti, O. Goldreich, S. Goldwasser, and S. Micali. Resettable zero-knowledge. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000. Updated version available at the Cryptology ePrint Archive, record 1999/022,
  6. CKPR01.
    R. Canetti, J. Kilian, E. Petrank, and A. Rosen. Black-box concurrent zero-knowledge requires Ω̃(log n) rounds. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 6–8 July 2001.Google Scholar
  7. Dam00.
    I. Damgård. Efficient concurrent zero-knowledge in the auxiliary string model. In Bart Preneel, ed., Advances in Cryptology-EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, Springer-Verlag, 2000.CrossRefGoogle Scholar
  8. DDP00.
    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. In U. Montanari, J. D. P. Rolim, and E. Welzl, editors, Automata Languages and Programming: 27th International Colloquim (ICALP 2000), volume 1853 of Lecture Notes in Computer Science, pages 451–462. Springer-Verlag, July 9–15 2000.Google Scholar
  9. DNS98.
    C. Dwork, M. Naor, and A. Sahai. Concurrent zero knowledge. In 30th Annual ACM Symposium on Theory of Computing, 1998.Google Scholar
  10. DP92.
    A. De Santis and G. Persiano. Zero-knowledge proofs of knowledge without interaction. In 33rd Annual Symposium on Foundations of Computer Science, 1992.Google Scholar
  11. DPP97.
    I. B. Damgård, T. P. Pedersen, and B. Pfitzmann. On the existence of statistically hiding bit commitment schemes and fail-stop signatures. Journal of Cryptology, 10(3):163–194, Summer 1997.zbMATHCrossRefMathSciNetGoogle Scholar
  12. DS98.
    C. Dwork and A. Sahai. Concurrent zero-knowledge: Reducing the need for timing constraints. In H. Krawczyk, ed., Advances in Cryptology — CRYPTO '98, volume 1462 of Lecture Notes in Computer Science, 1998.CrossRefGoogle Scholar
  13. FLS99.
    U. Feige, D. Lapidot, and A. Shamir. Multiple non-interactive zero knowledge proofs under general assumptions. SIAM Journal on Computing, 29(1):1–28, 1999.zbMATHCrossRefMathSciNetGoogle Scholar
  14. FS89.
    U. Feige and A. Shamir. Zero knowledge proofs of knowledge in two rounds. In Brassard [Bra89], pages 526–545.Google Scholar
  15. GGM86.
    O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions. Journal of the ACM, 33(4):792–807, October 1986.CrossRefMathSciNetGoogle Scholar
  16. GK96.
    O. Goldreich and H. Krawczyk. On the composition of zero-knowledge proof systems. SIAM Journal on Computing, 25(1):169–192, February 1996.zbMATHCrossRefMathSciNetGoogle Scholar
  17. GMR88.
    S. Goldwasser, S. Micali, and R. L. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on Computing, 17(2):281–308, April 1988.zbMATHCrossRefMathSciNetGoogle Scholar
  18. GMR89.
    S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18:186–208, 1989.zbMATHCrossRefMathSciNetGoogle Scholar
  19. GMW91.
    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 the ACM, 38(1):691–729, 1991.zbMATHMathSciNetGoogle Scholar
  20. HILL99.
    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.zbMATHCrossRefMathSciNetGoogle Scholar
  21. HM96.
    S. Halevi and S. Micali. Practical and provably-secure commitment schemes from collision-free hashing. In Neal Koblitz, editor, Advances in Cryptology-CRYPTO '96, volume 1109 of Lecture Notes in Computer Science, pages 201–215. Springer-Verlag, 18–22 August 1996.Google Scholar
  22. KP00.
    J. Kilian and E. Petrank. Concurrent zero-knowledge in polylogarithmic rounds. Technical Report 2000/013, Cryptology ePrint Archive,, 2000.
  23. KPR98.
    J. Kilian, E. Petrank, and C. Rackoff. Lower bounds for zero-knowledge on the Internet. In 39th Annual Symposium on Foundations of Computer Science, pages 484–492, Los Alamitos, California, November 1998. IEEE.Google Scholar
  24. Mer89.
    R. C. Merkle. A certified digital signature. In Brassard [Bra89], pages 218–238.Google Scholar
  25. Mic.
    Silvio Micali. CS proofs. SIAM Journal on Computing, to appear.Google Scholar
  26. MR01.
    S. Micali and L. Reyzin. Soundness in the public-key model. Unpublished manuscript, 2001.Google Scholar
  27. NR97.
    Moni Naor and Omer Reingold. Number-theoretic constructions of efficient pseudo-random functions. In 38th Annual Symposium on Foundations of Computer Science, pages 458–467, Miami Beach, Florida, 20–22 October 1997. IEEE.CrossRefGoogle Scholar
  28. RK99.
    R. Richardson and J. Kilian. On the concurrent composition of zero-knowledge proofs. In Jacques Stern, editor, Advances in Cryptology—EUROCRYPT '99, volume 1592 of Lecture Notes in Computer Science, pages 415–431. Springer-Verlag, 2–6 May 1999.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2001

Authors and Affiliations

  • Silvio Micali
    • 1
  • Leonid Reyzin
    • 1
  1. 1.Laboratory for Computer ScienceMassachusetts Institute of TechnologyCambridge

Personalised recommendations