__
TR23-081 | 1st June 2023 00:47
__

#### Constant-Round Arguments from One-Way Functions

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