Alex Lombardi: Fiat-Shamir via List-Recoverable Codes

Abstract: We construct hash functions that, assuming the hardness of LWE, securely realize the Fiat-Shamir transform (in the standard model) for the following rich classes of protocols:
 

- The parallel repetition of any ``commit-and-open'' protocol (such as the seminal Goldreich-Micali-Wigderson protocol for 3-coloring), using a natural choice of commitment scheme. 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.

 

This results in non-interactive variants of all such protocols, and -- for the HVZK proof systems -- proves that assuming LWE, the original interactive protocols cannot be zero knowledge. This leverages a connection due to Dwork-Naor-Reingold-Stockmeyer (FOCS '99) and resolves long-standing open questions about protocols such as GMW.

 

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.