Paper 2023/802

Constant-Round Arguments from One-Way Functions

Noga Amit, Weizmann Institute of Science
Guy Rothblum, Weizmann Institute of Science, Apple (United States)

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

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. STOC
Interactive ArgumentsDelegationOne-Way FunctionsConstant-Round
Contact author(s)
nogamit @ gmail com
rothblum @ alum mit edu
2023-06-06: approved
2023-05-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Noga Amit and Guy Rothblum},
      title = {Constant-Round Arguments from One-Way Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2023/802},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.