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

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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi mathvariant="sans-serif">B</mml:mi> <mml:mi mathvariant="sans-serif">P</mml:mi> <mml:mi mathvariant="sans-serif">P</mml:mi> </mml:mrow> </mml:mrow> </mml:math> cannot be black-box zero knowledge. Their result says nothing, however, about proofs (or arguments) of knowledge for languages in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi mathvariant="sans-serif">B</mml:mi> <mml:mi mathvariant="sans-serif">P</mml:mi> <mml:mi mathvariant="sans-serif">P</mml:mi> </mml:mrow> </mml:mrow> </mml:math>. 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ℛ</mml:mi> </mml:mrow> </mml:math> 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ℛ</mml:mi> </mml:mrow> </mml:math> 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi mathvariant="sans-serif">B</mml:mi> <mml:mi mathvariant="sans-serif">P</mml:mi> <mml:mi mathvariant="sans-serif">P</mml:mi> </mml:mrow> </mml:mrow> </mml:math> 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.