Paper 2023/1394

Incrementally Verifiable Computation via Rate-1 Batch Arguments

Omer Paneth, Tel Aviv University
Rafael Pass, Tel Aviv University, Cornell Tech
Abstract

Non-interactive delegation schemes enable producing succinct proofs (that can be efficiently verified) that a machine $M$ transitions from $c_1$ to $c_2$ in a certain number of deterministic steps. We here consider the problem of efficiently \emph{merging} such proofs: given a proof $\Pi_1$ that $M$ transitions from $c_1$ to $c_2$, and a proof $\Pi_2$ that $M$ transitions from $c_2$ to $c_3$, can these proofs be efficiently merged into a single short proof (of roughly the same size as the original proofs) that $M$ transitions from $c_1$ to $c_3$? To date, the only known constructions of such a mergeable delegation scheme rely on strong non-falsifiable ``knowledge extraction" assumptions. In this work, we present a provably secure construction based on the standard LWE assumption. As an application of mergeable delegation, we obtain a construction of incrementally verifiable computation (IVC) (with polylogarithmic length proofs) for any (unbounded) polynomial number of steps based on LWE; as far as we know, this is the first such construction based on any falsifiable (as opposed to knowledge-extraction) assumption. The central building block that we rely on, and construct based on LWE, is a rate-1 batch argument (BARG): this is a non-interactive argument for NP that enables proving $k$ NP statements $x_1,..., x_k$ with communication/verifier complexity $m+o(m)$, where $m$ is the length of one witness. Rate-1 BARGs are particularly useful as they can be recursively composed a super-constant number of times.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. FOCS
Contact author(s)
omerpa @ gmail com
rafael pass @ gmail com
History
2023-09-18: approved
2023-09-18: received
See all versions
Short URL
https://ia.cr/2023/1394
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1394,
      author = {Omer Paneth and Rafael Pass},
      title = {Incrementally Verifiable Computation via Rate-1 Batch Arguments},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1394},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1394}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.