ECCC-Report TR23-081https://eccc.weizmann.ac.il/report/2023/081Comments and Revisions published for TR23-081en-usSat, 06 Jan 2024 04:01:44 +0200
Revision 1
| Constant-Round Arguments from One-Way Functions |
Noga Amit,
Guy Rothblum
https://eccc.weizmann.ac.il/report/2023/081#revision1We 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$).Sat, 06 Jan 2024 04:01:44 +0200https://eccc.weizmann.ac.il/report/2023/081#revision1
Paper TR23-081
| Constant-Round Arguments from One-Way Functions |
Noga Amit,
Guy Rothblum
https://eccc.weizmann.ac.il/report/2023/081We 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$).Thu, 01 Jun 2023 08:42:37 +0300https://eccc.weizmann.ac.il/report/2023/081