Non-Native Arithmetic and CRT Codes

(Proposer: Liam Eagen)

Motivation

In many types of programmable cryptography, we often encounter the problem of “non-native arithmetic.” That is, while our SNARK is defined over a field of characteristic $p$ we would like to prove statements about arithmetic in some other field $q$. In some cases this is easy, for example if $q$ is small, but in many cases it is very expensive.

Residue Number Systems

One way to do this would be to encode a value $x$ over $\mathbb{F}_q$ first as an integer $z = x \mod q$, and then as a collection of small residues of $z$ modulo many small primes. Fix a sequence of primes $p_1, ..., p_k$ and let the residues be $r_k = z \mod p_k$. If $P = \prod_{i=1}^k p_i > z$ then we can do arithmetic with these residues. So long as the result does not exceed $P$, this will let us perform integer arithmetic. We can construct $z$ from the residues using the Chinese Remainder Theorem.

Batch Size Test for RNS values

This final point, that this works only for values smaller than $P$, is crucial, since it requires that the prover demonstrate all the inputs to an integer relation are small. This is expensive, since we cannot efficiently measure the size of an integer from its residues modulo small primes. Thus we would like to be avoid “materializing” these values outside of the RNS as much as possible.

One natural way to minimize the cost of the materialization is to materialize a linear combination of values all at once. In the simplest case, suppose we have a two $z_1, z_2$ that are given in RNS form and we want to show $-A < z_i < A$. Then suppose we choose a random challenge $-B < e < B$ and show that $-AB < z' < AB$ where $z' = z_1 + e z_2$. We can check that $z'$ is correctly constructed using only arithmetic mod $r_i$. What is the probability that $z_1$ and $z_2$ satisfy their constraints as a function of $A$ and $B$? Assume $A B < P$. hint: we want to make this arbitrarily small.

Issue: small rationals

Unfortunately, this doesn’t quite work. Suppose $z_i = z^*_i / d$ for small $d$ and $-A < z^*_i < A$. Then the probability that $z'$ is a sufficiently small integer is $1/d$, independent of $B$. This is because there is exactly residue class of $e \mod d$ such that $z^*_0 + e z^*_1 = 0 \mod d$. This cancels the denominator and causes $z'$ to be an integer even though $z_i^*$ are not.

However, in the spirit of the problem this is not really an issue. If $q$ is larger than $d$, then these rational values have perfectly valid reductions mod $q$. The modified question is then, given $-AB < z' < AB$, what is the probability that $z_i = z_i^* / d \mod P$ where $-A < z_i^* < A$ and $-C < d < C$ for some parameter $C$.

Extending to Proximity Gaps

Given this, can we extend this result to a proximity gap? That is, if $z'$ is close in a CRT code what can we say about $z_i$?