Welcome to the resource topic for 2022/1470
Title:
Casting out Primes: Bignum Arithmetic for Zero-Knowledge Proofs
Authors: Daniel Lubarov, Jordi Baylina Melé
Abstract:We describe a nondeterministic method for bignum arithmetic. It is inspired by the “casting out nines” technique, where some identity is checked modulo 9, providing a probabilistic result.
More generally, we might check that some identity holds under a set of moduli, i.e. f(\vec{x}) = 0 \mod m_i for each m_i \in M. Then \DeclareMathOperator{\lcm}{lcm} f(\vec{x}) = 0 \mod \lcm(M), and if we know |f(\vec{x})| < \lcm(M), it follows that f(\vec{x}) = 0.
We show how to perform such small-modulus checks efficiently, for certain f(\vec{x}) such as bignum multiplication. We focus on the cost model of zero-knowledge proof systems, which support field arithmetic and range checks as native operations.
ePrint: https://eprint.iacr.org/2022/1470
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .