Public-Coin, Complexity-Preserving, Succinct Arguments of Knowledge for NP from Collision-Resistance
Date: Friday, December 01, 2023
Time: 10:30 AM to 12:00 PM Note: all times are in the Eastern Time Zone
Location: G-882 Hewlett Room
Event Type: Seminar
Speaker URL: None
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.
Created by Felicia Raton at Tuesday, November 28, 2023 at 3:09 PM.