Goldreich-Krawczyk Revisited:   A Note on the Zero Knowledge   of Proofs of Knowledge

Lior Rotem

doi:10.62056/avr-11fgx

Goldreich-Krawczyk Revisited: A Note on the Zero Knowledge of Proofs of Knowledge

Authors

Lior Rotem

Stanford University, Stanford, USA
lrotem at cs dot stanford dot edu

Abstract

The seminal work of Goldreich and Krawczyk (SIAM Journal on Computing) shows that any constant-round public-coin interactive proof for languages not in ${\sf BPP}$ cannot be black-box zero knowledge. Their result says nothing, however, about proofs (or arguments) of knowledge for languages in ${\sf BPP}$. As a special case, their work leaves open the question of whether Schnorr's protocol for proving knowledge of discrete logarithms in cyclic groups is black-box zero knowledge.

In this work we focus on the zero knowledge of proofs of knowledge, centering on Schnorr's protocol as a prominent example. We prove two lower bounds, ruling out two different classes of simulators through which Schnorr's protocol can be proven zero knowledge:

We prove that if a relation $\mathcal{R}$ has a public-coin interactive proof of knowledge that is black-box zero knowledge and this protocol is compatible with the Fiat-Shamir transform in the random oracle model, then $\mathcal{R}$ must be efficiently searchable. As an immediate corollary, we deduce that Schnorr's protocol cannot be black-box zero knowledge in groups in which discrete log is hard.
We define a new class of simulators for Schnorr's protocol, which we call generic simulators. A generic simulator is one that works in any cyclic group, and does not use the representation of the specific group in which Schnorr's protocol is instantiated. We prove that Schnorr's protocol cannot have generic simulators.

As an additional contribution, we generalize the original lower bound of Goldreich and Krawczyk, to prove that a language not in ${\sf BPP}$ cannot have an interactive proof (not necessarily of knowledge) that is both black-box zero knowledge and compatible with the Fiat-Shamir transform in the random oracle model. In conjunction with recent works, this extends the Goldreich-Krawczyk lower bound to public-coin protocols that are not constant-round but have round-by-round soundness, including the parallel repetition of any public-coin interactive proof.

References

[AB09]

Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press 2009.

Google Scholar ePrint

[AFK22]

Thomas Attema, Serge Fehr, and Michael Klooß. Fiat-Shamir Transformation of Multi-round Interactive Proofs. In Eike Kiltz and Vinod Vaikuntanathan, editors, TCC 2022, Part I, volume 13747 of LNCS, pages 113–142. November 2022. Springer, Cham. DOI: 10.1007/978-3-031-22318-1_5

Google Scholar ePrint

[AFK23]

Thomas Attema, Serge Fehr, and Michael Klooß. Fiat-Shamir Transformation of Multi-Round Interactive Proofs (Extended Version). Journal of Cryptology, 36(4):36, October 2023. DOI: 10.1007/s00145-023-09478-y

Google Scholar ePrint

[BG93]

Mihir Bellare and Oded Goldreich. On Defining Proofs of Knowledge. In Ernest F. Brickell, editor, CRYPTO'92, volume 740 of LNCS, pages 390–420. August 1993. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-48071-4_28

Google Scholar ePrint

[BN06]

Mihir Bellare and Gregory Neven. Multi-signatures in the plain public-Key model and a general forking lemma. In Ari Juels, Rebecca N. Wright, and Sabrina De Capitani di Vimercati, editors, ACM CCS 2006, pages 390–399. 2006. ACM Press. DOI: 10.1145/1180405.1180453

Google Scholar ePrint

[BR93]

Mihir Bellare and Phillip Rogaway. Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. In Dorothy E. Denning, Raymond Pyle, Ravi Ganesan, Ravi S. Sandhu, and Victoria Ashby, editors, ACM CCS 93, pages 62–73. November 1993. ACM Press. DOI: 10.1145/168588.168596

Google Scholar ePrint

[BS23]

Dan Boneh and Victor Shoup. A graduate course in applied cryptography. Version 0.6, 2023.

Google Scholar ePrint

[CCH⁺18]

Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, and Ron D. Rothblum. Fiat-Shamir From Simpler Assumptions. https://eprint.iacr.org/2018/1004. Cryptology ePrint Archive, Paper 2018/1004. 2018.

Google Scholar ePrint

[CCH⁺19]

Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum, and Daniel Wichs. Fiat-Shamir: from practice to theory. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 1082–1090, New York, NY, USA. 2019. Association for Computing Machinery. DOI: 10.1145/3313276.3316380

Google Scholar ePrint

[CG89]

Benny Chor and Oded Goldreich. On the power of two-point based sampling. Journal of Complexity, 5(1):96–106, 1989. DOI: https://doi.org/10.1016/0885-064X(89)90015-0

Google Scholar ePrint

[CLMQ21]

Yilei Chen, Alex Lombardi, Fermi Ma, and Willy Quach. Does Fiat-Shamir Require a Cryptographic Hash Function?. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part IV, volume 12828 of LNCS, pages 334–363, Virtual Event. August 2021. Springer, Cham. DOI: 10.1007/978-3-030-84259-8_12

Google Scholar ePrint

[CLW18]

Ran Canetti, Alex Lombardi, and Daniel Wichs. Fiat-Shamir: From Practice to Theory, Part II (NIZK and Correlation Intractability from Circular-Secure FHE). https://eprint.iacr.org/2018/1248. Cryptology ePrint Archive, Paper 2018/1248. 2018.

Google Scholar ePrint

[CP93]

David Chaum and Torben P. Pedersen. Wallet Databases with Observers. In Ernest F. Brickell, editor, CRYPTO'92, volume 740 of LNCS, pages 89–105. August 1993. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-48071-4_7

Google Scholar ePrint

[Cra97]

Ronald Cramer. Modular Design of Secure yet Practical Cryptographic Protocols. PhD thesis, Universiteit van Amsterdam, 1997.

Google Scholar ePrint

[CS97]

Jan Camenisch and Markus Stadler. Proof systems for general statements about discrete logarithms. Technical Report/ETH Zurich, Department of Computer Science, 260, 1997.

Google Scholar ePrint

[Dam02]

Ivan Damgård. On $\Sigma$-protocols. Lecture Notes, University of Aarhus, Department for Computer Science, 84, 2002.

Google Scholar ePrint

[DNRS03]

Cynthia Dwork, Moni Naor, Omer Reingold, and Larry Stockmeyer. Magic functions: In memoriam: Bernard m. dwork 1923–1998. Journal of the ACM (JACM), 50(6):852–921, 2003. DOI: https://doi.org/10.1145/950620.95062

Google Scholar ePrint

[FS87]

Amos Fiat and Adi Shamir. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In Andrew M. Odlyzko, editor, CRYPTO'86, volume 263 of LNCS, pages 186–194. August 1987. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-47721-7_12

Google Scholar ePrint

[GK96]

Oded Goldreich and Hugo Krawczyk. On the composition of zero-knowledge proof systems. SIAM Journal on Computing, 25(1):169–192, 1996. DOI: https://doi.org/10.1137/S0097539791220688

Google Scholar ePrint

[GMR85]

Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract). In 17th ACM STOC, pages 291–304. May 1985. ACM Press. DOI: 10.1145/22145.22178

Google Scholar ePrint

[GMW87]

Oded Goldreich, Silvio Micali, and Avi Wigderson. How to Prove all NP-Statements in Zero-Knowledge, and a Methodology of Cryptographic Protocol Design. In Andrew M. Odlyzko, editor, CRYPTO'86, volume 263 of LNCS, pages 171–185. August 1987. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-47721-7_11

Google Scholar ePrint

[GO94]

Oded Goldreich and Yair Oren. Definitions and Properties of Zero-Knowledge Proof Systems. Journal of Cryptology, 7(1):1–32, December 1994. DOI: 10.1007/BF00195207

Google Scholar ePrint

[Gol01]

Oded Goldreich. Foundations of cryptography: volume 1, basic tools, volume 1. Cambridge university press 2001.

Google Scholar ePrint

[GQ90]

Louis C. Guillou and Jean-Jacques Quisquater. A “Paradoxical” Indentity-Based Signature Scheme Resulting from Zero-Knowledge. In Shafi Goldwasser, editor, CRYPTO'88, volume 403 of LNCS, pages 216–231. August 1990. Springer, New York. DOI: 10.1007/0-387-34799-2_16

Google Scholar ePrint

[HLR21]

Justin Holmgren, Alex Lombardi, and Ron D. Rothblum. Fiat-Shamir via list-recoverable codes (or: parallel repetition of GMW is not zero-knowledge). In Samir Khuller and Virginia Vassilevska Williams, editors, 53rd ACM STOC, pages 750–760. June 2021. ACM Press. DOI: 10.1145/3406325.3451116

Google Scholar ePrint

[Hol19]

Justin Holmgren. On Round-By-Round Soundness and State Restoration Attacks. https://eprint.iacr.org/2019/1261. Cryptology ePrint Archive, Paper 2019/1261. 2019.

Google Scholar ePrint

[Jof74]

Anatole Joffe. On a set of almost deterministic $ k $-independent random variables. the Annals of Probability, 2(1):161–162, 1974.

Google Scholar ePrint

[Mau15]

Ueli Maurer. Zero-knowledge proofs of knowledge for group homomorphisms. DCC, 77(2-3):663–676, 2015. DOI: 10.1007/s10623-015-0103-5

Google Scholar ePrint

[NN90]

Joseph Naor and Moni Naor. Small-bias Probability Spaces: Efficient Constructions and Applications. In 22nd ACM STOC, pages 213–223. May 1990. ACM Press. DOI: 10.1145/100216.100244

Google Scholar ePrint

[Oka93]

Tatsuaki Okamoto. Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes. In Ernest F. Brickell, editor, CRYPTO'92, volume 740 of LNCS, pages 31–53. August 1993. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-48071-4_3

Google Scholar ePrint

[PS96]

David Pointcheval and Jacques Stern. Security Proofs for Signature Schemes. In Ueli M. Maurer, editor, EUROCRYPT'96, volume 1070 of LNCS, pages 387–398. May 1996. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-68339-9_33

Google Scholar ePrint

[RS21]

Lior Rotem and Gil Segev. Tighter Security for Schnorr Identification and Signatures: A High-Moment Forking Lemma for $\varSigma$-Protocols. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part I, volume 12825 of LNCS, pages 222–250, Virtual Event. August 2021. Springer, Cham. DOI: 10.1007/978-3-030-84242-0_9

Google Scholar ePrint

[Sch90]

Claus-Peter Schnorr. Efficient Identification and Signatures for Smart Cards. In Gilles Brassard, editor, CRYPTO'89, volume 435 of LNCS, pages 239–252. August 1990. Springer, New York. DOI: 10.1007/0-387-34805-0_22

Google Scholar ePrint

[Sch91]

Claus-Peter Schnorr. Efficient Signature Generation by Smart Cards. Journal of Cryptology, 4(3):161–174, January 1991. DOI: 10.1007/BF00196725

Google Scholar ePrint

[Sho97]

Victor Shoup. Lower Bounds for Discrete Logarithms and Related Problems. In Walter Fumy, editor, EUROCRYPT'97, volume 1233 of LNCS, pages 256–266. May 1997. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-69053-0_18

Google Scholar ePrint

[WC81]

Mark N Wegman and J Lawrence Carter. New hash functions and their use in authentication and set equality. Journal of computer and system sciences, 22(3):265–279, 1981. DOI: https://doi.org/10.1016/0022-0000(81)90033-7

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/avr-11fgx

History

Submitted: 2025-01-13
Accepted: 2025-03-11
Published: 2025-04-08

How to cite

Lior Rotem, Goldreich-Krawczyk Revisited: A Note on the Zero Knowledge of Proofs of Knowledge. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/avr-11fgx.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{10.62056/avr-11fgx,
         author={Lior Rotem},
         title={Goldreich-Krawczyk Revisited:   A Note on the Zero Knowledge   of Proofs of Knowledge},
         volume={2},
         number={1},
         year={2025},
         date={2025-04-08},
         issn={3006-5496},
         doi={10.62056/avr-11fgx},
         journal={{IACR} Communications in Cryptology},
         publisher={International Association for Cryptologic Research}
}

TY  - JOUR
AU  - Lior Rotem
PY  - 2025
TI  - Goldreich-Krawczyk Revisited:   A Note on the Zero Knowledge   of Proofs of Knowledge
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 2
IS  - 1
DO  - 10.62056/avr-11fgx
UR  - https://doi.org/10.62056/avr-11fgx
AB  - <p>The seminal work of Goldreich and Krawczyk (SIAM Journal on Computing) shows that any constant-round public-coin interactive proof for languages not in ${\sf BPP}$ cannot be black-box zero knowledge. Their result says nothing, however, about proofs (or arguments) of knowledge for languages in ${\sf BPP}$. As a special case, their work leaves open the question of  whether Schnorr's protocol for proving knowledge of discrete logarithms in cyclic groups is black-box zero knowledge.</p><p>In this work we focus on the zero knowledge of proofs of knowledge, centering on Schnorr's protocol as a prominent example. We prove two lower bounds, ruling out two different classes of simulators through which Schnorr's protocol can be proven zero knowledge: </p><ol>     <li>We prove that if a relation $\mathcal{R}$ has a public-coin interactive proof of knowledge that is black-box zero knowledge and this protocol is compatible with the Fiat-Shamir transform in the random oracle model, then $\mathcal{R}$ must be efficiently searchable. As an immediate corollary, we deduce that Schnorr's protocol cannot be black-box zero knowledge in groups in which discrete log is hard.     </li><li>We define a new class of simulators for Schnorr's protocol, which we call generic simulators. A generic simulator is one that works in any cyclic group, and does not use the representation of the specific group in which Schnorr's protocol is instantiated. We prove that Schnorr's protocol cannot have generic simulators. </li></ol><p> As an additional contribution, we generalize the original lower bound of  Goldreich and Krawczyk, to prove that a language not in ${\sf BPP}$ cannot have an interactive proof (not necessarily of knowledge) that is both black-box zero knowledge and compatible with the Fiat-Shamir transform in the random oracle model. In conjunction with recent works, this extends the Goldreich-Krawczyk lower bound to public-coin protocols that are not constant-round but have round-by-round soundness, including the parallel repetition of any public-coin interactive proof. </p>
ER  -

Lior Rotem, Goldreich-Krawczyk Revisited: A Note on the Zero Knowledge of Proofs of Knowledge. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/avr-11fgx.