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.

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.

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.

See ECCC TR21-032

Back to list of Oded's choices.