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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

General Techniques for Building SNARKs over the Integers

  • Matteo Campanelli,
  • Mathias Hall-Andersen

摘要

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.