Alex Lombardi: Fiat-Shamir via List-Recoverable Codes

Speaker: Alex Lombardi, MIT

Date: Friday, March 05, 2021

Time: 1:00 PM to 2:30 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: email or join the CIS Seminar email group for Zoom link

Event Type: Seminar

Room Description:

Host: Vinod Vaikuntanathan and Yael Kalai

Contact: Deborah Goodwin,

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to:,,

Reminder Subject: TALK: 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.

Based on joint work with Justin Holmgren and Ron Rothblum.

Research Areas:

Impact Areas:

See other events that are part of the Cryptography and Information Security (CIS) Seminar Series 2021.

Created by Deborah Goodwin Email at Friday, February 26, 2021 at 8:47 AM.