Paper 2023/1394
Incrementally Verifiable Computation via Rate1 Batch Arguments
Abstract
Noninteractive 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 nonfalsifiable ``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 knowledgeextraction) assumption. The central building block that we rely on, and construct based on LWE, is a rate1 batch argument (BARG): this is a noninteractive 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. Rate1 BARGs are particularly useful as they can be recursively composed a superconstant number of times.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Published elsewhere. Minor revision. FOCS
 Contact author(s)

omerpa @ gmail com
rafael pass @ gmail com  History
 20230918: approved
 20230918: received
 See all versions
 Short URL
 https://ia.cr/2023/1394
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/1394, author = {Omer Paneth and Rafael Pass}, title = {Incrementally Verifiable Computation via Rate1 Batch Arguments}, howpublished = {Cryptology ePrint Archive, Paper 2023/1394}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/1394}}, url = {https://eprint.iacr.org/2023/1394} }