Constant-Round Arguments from One-Way Functions

by Noga Amit and Guy Rothblum

Oded's comments

I got private presentations of this work more than a year ago, but the authors kept postponing posting the work, and having missed its posting (in June 2023) I forgot to review it. Anyhow, here is my take.

Using any one way function, the aforementioned work presents a constant-round argument system (a.k.s computationally-sound proof system) of low communication complexity for any set that can be decided by a small-depth Boolean circuit. Specifically, the communication complexity as well as the verifier time is almost linear in the depth of the deciding circuit. Furthermore, the honest prover strategy is polynomial in the size of the aforementioned circuit.

The construction is based on transforming a known multi-round interactive proof system into a constant-round one by using extremely short commitments to the sequence of all possible messages that the prover may send in each of the rounds of the original protocol. The problem with this strategy is that the common wisdom is that in order to implement it (via an authentication tree) one has to use collision-resilient hashing (CRH), whereas the latter are not known to exist when only assuming the existence of one-way functions (OWF).

In contrast, the construction and analysis capitalize on the observation that the foregoing sequence of possible messages is determined by the input to the protocol such that each element in the sequence is determined by the previous one. This allows to use a primitive that can be constructed based any OWF rather than based on CRH. The actual analysis is extremely sophisticated and subtle.

The original 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 P, such as depth-bounded computations.

Kilian's celebrated work [STOC 1992] provides such 4-message arguments for P (actually, for 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 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 NC (indeed, even for AC1).

See ECCC TR23-081.


Back to list of Oded's choices.