Schwartz–Zippel over rings and open conjectures
If you’ve touched probabilistic proofs or MPC, you’ve leaned on the Schwartz–Zippel lemma. Over a field, a non-zero polynomial of degree \(d\), evaluated at a random point, is zero with probability at most \(d/|S|\). That single fact is the bedrock of “test an identity by checking it at one random point.”
But a lot of modern secure computation lives over rings like \(\mathbb{Z}_{2^\ell}\) — they match machine words and make arithmetic cheap. And over a ring, Schwartz–Zippel breaks: zero divisors manufacture extra roots, so a non-zero polynomial can vanish far more often than \(d/|S|\) allows. The clean field bound simply doesn’t hold.
A ring version, with slack
In my recent work Pika, I prove a Schwartz–Zippel analogue that does hold over these rings. The price is a little slack — you have to work over a slightly larger ring than the one your polynomial actually lives on.
Let $p(x_1, \ldots, x_n)$ be an $n$-variable bilinear polynomial over $\mathbb{Z}_{2^{\ell+2s}}$ that is not identically zero over $\mathbb{Z}_{2^{\ell}}$. Then the probability that $p$ evaluates to $0$ on points sampled uniformly from $\{0, 1, \ldots, 2^{\ell}-1\}$ is at most $2^{1-s}$.
To get soundness error \(2^{1-s}\) the test runs over \(\mathbb{Z}_{2^{\ell+2s}}\) — a slack of \(2s\) extra bits compared to the Field version of SZ Lemma. For the quadratic case the shape is identical, but the polynomial must evaluate to zero over the larger ring \(\mathbb{Z}_{2^{\ell+4s}}\) — the slack doubles to \(4s\).
That slack isn’t just analysis bookkeeping. In implementation it sets the bit-width of your data: soundly testing a quadratic identity means carrying every value over \(\mathbb{Z}_{2^{\ell+4s}}\) — that’s \(\ell + 4s\) bits per value instead of \(\ell\), paid as wider words on every operation. So the constant in front of \(s\) is a very concrete cost.
How small can the slack be?
And that constant — the 4 for quadratics — is where it gets interesting. Nothing says it’s optimal. There were a few open problems/conjectures:
Quadratics need a $4s$ slack and the test runs over $\mathbb{Z}_{2^{\ell+4s}}$. I suspect 4 is the smallest constant that works. Conjecture: for a given slack $s$ there is no constant $c < 4$ such that $(\ell + c\,s)$-bit ring suffices.
While quadratic sufficed for the work, a more general statement may also be of interest.
Let $p(x_1, \ldots, x_n)$ be an $n$-variable polynomial of degree $d$ over $\mathbb{Z}_{2^{\ell+c(d)s}}$ that is not identically zero over $\mathbb{Z}_{2^{\ell}}$. What is the smallest constant $c(d)$ such that the probability that $p$ evaluates to $0$ on points sampled uniformly from $\{0, 1, \ldots, 2^{\ell}-1\}$ is at most $O(2^{-s})$.
PDF Pika · PETS 2022