Paper 2024/1548

Fully Succinct Arguments over the Integers from First Principles

Abstract

In this work we construct fully succinct arguments of knowledge for computations over the infinite ring $\mathbb{Z}$. We are motivated both by their practical applications—e.g. verifying cryptographic primitives based on RSA groups or Ring-LWE; field emulation and field "switching"; arbitrary precision-arithmetic—and by theoretical questions of techniques for constructing arguments over the integers in general. Unlike prior works constructing arguments for $\mathbb{Z}$ or $\mathbb{Z}_{2^k}$, we circumvent most of the complexities of arithmetizing or extracting over these rings directly. Instead, we introduce a general and arguably simpler theoretical framework for building succinct arguments over $\mathbb{Z}$, one which allows protocol designers to reuse existing SNARK techniques. This is possible thanks to our key technique—$\textit{fingerprinting}$, a form of arithmetic hashing—for "boostrapping" protocols over the integers from existing systems over prime fields (e.g., multilinear-flavored ones, such as Spartan). The resulting protocol can then be compiled into a cryptographic argument via a novel kind of polynomial commitment allowing queries to a multivariate $\textit{integer}$ polynomial modulo an arbitrary prime $q$. We show how to instantiate our framework and obtain a concrete scheme, $\mathbb{Z}$artan. This is the first construction in literature being $\textit{fully}$ succinct over integer computation, i.e., with short proofs and fast verification even when the witness consists of very large integers.

Note: A previous version of this work did not account for one superlinear step in a subprotocol (while incorrectly stating that the resulting prover stayed linear). This appeared more specifically in a part of our constructions whose goal was to obtain norm-succinctness. We currently use a different, more general and more efficient technique for the same problem that does not have this issue.