Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR23-081 | 6th January 2024 04:01

Constant-Round Arguments from One-Way Functions

RSS-Feed




Revision #1
Authors: Noga Amit, Guy Rothblum
Accepted on: 6th January 2024 04:01
Downloads: 267
Keywords: 


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).



Changes to previous version:

Revised Section 2.1: the observation that we attributed to Bellare and Rogaway was actually made earlier by Naor and Yung.


Paper:

TR23-081 | 1st June 2023 00:47

Constant-Round Arguments from One-Way Functions





TR23-081
Authors: Noga Amit, Guy Rothblum
Publication: 1st June 2023 08:42
Downloads: 501
Keywords: 


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).



ISSN 1433-8092 | Imprint