Public-Coin, Complexity-Preserving, Succinct Arguments of Knowledge for NP from Collision-Resistance

Speaker: Cody Freitag

Date: Friday, December 01, 2023

Time: 10:30 AM to 12:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: G-882 Hewlett Room

Event Type: Seminar

Room Description:

Host:

Contact:

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, cis-seminars@csail.mit.edu

Reminder Subject: TALK: Public-Coin, Complexity-Preserving, Succinct Arguments of Knowledge for NP from Collision-Resistance

Succinct arguments allow a powerful (yet polynomial-time) prover to convince a weak verifier the validity of some mathematical statement using very little communication. A major barrier to the deployment of such proofs is the unwieldy overhead of the prover relative to the complexity of the statement to be proved. Despite over 30 years of progress aiming to minimize the prover's time complexity, the prover's space complexity still remains prohibitively large for existing protocols. In this work, we focus on complexity-preserving arguments where a verifier can be convinced the validity of a non-deterministic time $T$ and space $S$ RAM computation by a RAM prover running in time $\tilde O(T)$ and space $\tilde O(S)$---ignoring polynomial factors in the security parameter.

Bitansky and Chiesa (CRYPTO '12) first constructed complexity-preserving succinct arguments of knowledge for NP based on fully homomorphic encryption. However, their protocols require the verifier to maintain private state, so they are not publicly verifiable. Public verifiability is a key property needed for applications of proofs in the distributed, multi-party setting, which have been the driving force behind the modern resurgence of interest into cryptographic proofs. For this reason, Bitansky and Chiesa asked whether public-coin complexity preserving succinct arguments for NP exist from standard cryptographic assumptions. In this work, we resolve this open question positively and provide a construction based solely on the existence of collision-resistant hash functions.

This talk is based on joint work with Omer Paneth and Rafael Pass.

Research Areas:

Impact Areas:

See other events that are part of the CIS Seminar Series 2023 - 2024.

Created by Megan F Farmer at Tuesday, November 28, 2023 at 3:09 PM.