[Resource Topic] 2022/1470: Casting out Primes: Bignum Arithmetic for Zero-Knowledge Proofs

Welcome to the resource topic for 2022/1470

Casting out Primes: Bignum Arithmetic for Zero-Knowledge Proofs

Authors: Daniel Lubarov, Jordi Baylina Melé


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 .