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.

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. 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. 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:

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.