Paper 2022/1470

Casting out Primes: Bignum Arithmetic for Zero-Knowledge Proofs

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(\overrightarrow{x})=0\mathrm{mod}{m}_i$ for each $m_i\in M$. Then $f(\overrightarrow{x})=0\mathrm{mod}\mathrm{lcm}(M)$, and if we know $|f(\overrightarrow{x})|<\mathrm{lcm}(M)$, it follows that $f(\overrightarrow{x})=0$. We show how to perform such small-modulus checks efficiently, for certain $$ 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.