All reports by Author Noga Amit:

__
TR23-081
| 1st June 2023
__

Noga Amit, Guy Rothblum#### Constant-Round Arguments from One-Way Functions

Noga Amit, Guy Rothblum

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