Welcome to the resource topic for 2024/850
Title:
Constant-Round Arguments for Batch-Verification and Bounded-Space Computations from One-Way Functions
Authors: Noga Amit, Guy N. Rothblum
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].
ePrint: https://eprint.iacr.org/2024/850
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .