Fiat-Shamir via List-Recoverable Codes
(or: Parallel Repetition of GMW is not Zero-Knowledge)
by Justin Holmgren, Alex Lombardi, and Ron Rothblum
Oded's comments
Here the GMW protocol is a 3-message (zero-knowledge)
protocol for 3-Colorability in which the prover sends individual
commitments to colors, the verifier responds with a random edge,
and the prover de-commits to the corresponding colors.
The main result of this paper is proving that, under the LWE assumption,
the following conjecture is false.
The parallel GMW conjecture (vaguely stated)
The GMW protocol preserves zero-knowledge under parallel repetitions.
I have labelled this conjecture by the words `vaguely stated'
since it does not really specify the protocol; what is misssing
is the specification of the commitment scheme.
Two possible extreme specifications follow.
The parallel GMW conjecture (maximal interpretation)
The protocol that arises from instantiating the GMW protocol
with any (constant-round) commitment scheme
(including in the common reference string model)
preserves zero-knowledge under parallel repetitions.
I believe that the maximal interpretation is the one that
is most consistent with the original vaguely stated conjecture.
(Proper disclosure: I never believed the conjecture...)
The main result of this paper refers to this maximal interpretation.
However, a minimal interpretation also makes sense,
and is suggested as a challenge for future research.
The parallel GMW conjecture (minimal interpretation)
The protocol that arises from instantiating the GMW protocol
with some (constant-round public coin) commitment scheme
(including in the common reference string model)
preserves zero-knowledge under parallel repetitions.
It should be mentioned that the fact that evidence
to the falseness of the above conjectures have appeared in the past.
For starters, assuming NP is not in BPP,
none of these conjectures can be proved using black-box simulation,
since they all yield constant-round public-coin protocols
[GK96].
But, this is not a strong evidence, since, as shown by Boaz Barak,
non-black-box simulations can succeed where black-box ones fails [Bar01].
Nevertheless, other evidence for failure were suggested;
specifically, the following text is reproduced from the paper.
A sequence of recent works [KRR17, CCRR18, HL18, CCH+18] showed
that zero-knowledge is not preserved by repetition in very high generality
(in fact, general 3-message zero-knowledge proofs can be ruled out [FGJ18]),
but these works relied on extremely strong, non-falsifiable,
and/or poorly understood cryptographic assumptions. The first progress on
this question based on standard assumptions was due to Canetti et al. [CCH+19]
and Peikert and Shiehian [PS19], who showed that some classical ZK protocols
[GMR85, Blu86] fail to remain ZK under parallel repetition.
However, their results conspicuously fail to capture the GMW protocol
(and indeed fail to capture ``most'' protocols).
Hence, the evidence against the maximal interpretation
of the (parallel GMW) conjecture provided by this paper
is by far stronger than all prior evidence.
The original abstract
Shortly after the introduction of zero-knowledge proofs, Goldreich, Micali and Wigderson (CRYPTO '86) demonstrated their wide applicability by constructing zero-knowledge proofs for the NP-complete problem of graph 3-coloring. A long-standing open question has been whether parallel repetition of their protocol preserves zero knowledge. In this work, we answer this question in the negative, assuming a a standard cryptographic assumption (i.e., the hardness of learning with errors (LWE)).
Leveraging a connection observed by Dwork, Naor, Reingold, and Stockmeyer (FOCS '99), our negative result is obtained by making positive progress on a related fundamental problem in cryptography: securely instantiating the Fiat-Shamir heuristic for eliminating interaction in public-coin interactive protocols. A recent line of works has shown how to instantiate the heuristic securely, albeit only for a limited class of protocols.
Our main result shows how to instantiate Fiat-Shamir for parallel repetitions of much more general interactive proofs. In particular, we construct hash functions that, assuming LWE, securely realize the Fiat-Shamir transform for the following rich classes of protocols:
- The parallel repetition of any ``commit-and-open'' protocol (such as the GMW protocol mentioned above), when a specific (natural) commitment scheme is used. Commit-and-open protocols are a ubiquitous paradigm for constructing general purpose public-coin zero knowledge proofs.
- The parallel repetition of any base protocol that (1) satisfies a stronger notion of soundness called round-by-round soundness, and (2) has an efficient procedure, using a suitable trapdoor, for recognizing ``bad verifier randomness'' that would allow the prover to cheat.
Our results are obtained by establishing a new connection between the Fiat-Shamir transform and list-recoverable codes. In contrast to the usual focus in coding theory, we focus on a parameter regime in which the input lists are extremely large, but the rate can be small. We give a (probabilistic) construction based on Parvaresh-Vardy codes (FOCS '05) that suffices for our applications.
Keywords: zero knowledge, Fiat-Shamir paradigm
See ECCC TR21-032
Back to
list of Oded's choices.