Welcome to the resource topic for 2023/802
Title:
Constant-Round Arguments from One-Way Functions
Authors: Noga Amit, Guy Rothblum
Abstract:We study the following question: what cryptographic assumptions are needed for obtaining constant-round computationally-sound argument systems? We focus on argument systems with almost-linear verification time for subclasses of \mathbf{P}, such as depth-bounded computations.
Kilian’s celebrated work [STOC 1992] provides such 4-message arguments for \mathbf{P} (actually, for \mathbf{NP}) using collision-resistant hash functions.
We show that one-way\ functions suffice for obtaining constant-round arguments of almost-linear verification time for languages in \mathbf{P} that have log-space uniform circuits of linear depth and polynomial size. More generally, the complexity of the verifier scales with the circuit depth. Furthermore, our argument systems (like Kilian’s) are doubly-efficient; that is, the honest prover strategy can be implemented in polynomial-time.
Unconditionally sound interactive proofs for this class of computations do not rely on any cryptographic assumptions, but they require a linear number of rounds [Goldwasser, Kalai and Rothblum, STOC 2008]. Constant-round interactive proof systems of linear verification complexity are not known even for \mathbf{NC} (indeed, even for \mathbf{AC}^1).
ePrint: https://eprint.iacr.org/2023/802
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .