Paper 2024/1548

Fully Succinct Arguments over the Integers from First Principles

Mathias Hall-Andersen, ZKSecurity

Abstract

We construct succinct arguments of knowledge for computations over the ring of integers $\mathbb{Z}$ ($\mathbb{Z}$NARKs). Our motivation stems both from the theoretical challenge of developing general techniques for arguments over the integers and their practical applications. For example, many natural applications can be viewed as special cases of proving over $\mathbb{Z}$—e.g. cryptographic primitives based on RSA groups or Ring-LWE; field emulation and field "switching"; arbitrary-precision arithmetic. Moreover, $\mathbb{Z}$NARKs can support arbitrary mixing and matching of these settings within the same computation, which is not easily possible with solutions tailored to a specific arithmetic. Unlike prior works targeting $\mathbb{Z}$ or $\mathbb{Z}_{2^k}$, we avoid most of the complexities involved in extracting over these rings directly. Instead, we introduce a general, 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—fingerprinting, a form of arithmetic hashing—for "bootstrapping" 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 integer polynomial modulo an arbitrary prime $q$. We show how to instantiate our framework and obtain a concrete scheme, $\mathbb{Z}$aratan. This is the first construction in literature being _fully_ succinct over integer computations, i.e., with short proofs and fast verification even when the witness consists of large integers.