Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR24-096 | 30th May 2024 12:51

Constant-Round Arguments for Batch-Verification and Bounded-Space Computations from One-Way Functions

RSS-Feed




Revision #1
Authors: Noga Amit, Guy Rothblum
Accepted on: 30th May 2024 12:51
Downloads: 48
Keywords: 


Abstract:

What are the minimal cryptographic assumptions that suffice for constructing efficient argument systems, and for which tasks? Recently, Amit and Rothblum [STOC 2023] showed that one-way functions suffice for constructing constant-round arguments for bounded-depth computations. In this work we ask: what other tasks have efficient argument systems based only on one-way functions? We show two positive results:

First, we construct a new argument system for batch-verification of $k$ $UP$ statements ($NP$ statements with a unique witness) for witness relations that are verifiable in depth $D$.
Taking $M$ to be the length of a single witness, the communication complexity is $O(\log k) \cdot (M + k \cdot D \cdot n^{\sigma})$, where $\sigma > 0$ is an arbitrarily small constant. In particular, the communication is quasi-linear in the length of a single witness, so long as $k < M / (D \cdot n^{\sigma})$.
The number of rounds is constant and the honest prover runs in polynomial time given witnesses for all $k$ inputs' membership in the language.

Our second result is a constant-round doubly-efficient argument system for languages in $P$ that are computable by bounded-space Turing machines. For this class of computations, we obtain an exponential improvement in the trade-off between the number of rounds and the (exponent of the) communication complexity, compared to known unconditionally sound protocols [Reingold, Rothblum and Rothblum, STOC 2016].



Changes to previous version:

Changed abstract to explicitly state the communication complexity that the UP batching protocol achieves.


Paper:

TR24-096 | 27th May 2024 21:50

Constant-Round Arguments for Batch-Verification and Bounded-Space Computations from One-Way Functions





TR24-096
Authors: Noga Amit, Guy Rothblum
Publication: 27th May 2024 22:43
Downloads: 108
Keywords: 


Abstract:

What are the minimal cryptographic assumptions that suffice for constructing efficient argument systems, and for which tasks? Recently, Amit and Rothblum [STOC 2023] showed that one-way functions suffice for constructing constant-round arguments for bounded-depth computations. In this work we ask: what other tasks have efficient argument systems based only on one-way functions? We show two positive results:

First, we construct a new argument system for batch-verification of $k$ $UP$ statements ($NP$ statements with a unique witness) for witness relations that are verifiable in bounded depth. The communication is quasi-linear in the length of a single witness, and the number of rounds is constant. The honest prover runs in polynomial time given witnesses for all $k$ inputs' membership in the language.

Our second result is a constant-round doubly-efficient argument system for languages in $P$ that are computable by bounded-space Turing machines. For this class of computations, we obtain an exponential improvement in the trade-off between the number of rounds and the (exponent of the) communication complexity, compared to known unconditionally sound protocols [Reingold, Rothblum and Rothblum, STOC 2016].



ISSN 1433-8092 | Imprint