# Data fingerprint using polynomial and Schwartz-Zippel Lemma

I'm working on a protocol and am looking for a way to fingerprint a set of elements. All elements are evenly distributed across a finite field that is integers modulus $$2^{256}$$.

Assume I have a set of elements $$[v_0, v_1, v_2, v_3]$$, and a strong random value $$R$$ (also in the field).

I construct a hash like this $$H = v_0 + v_1R + v_2R^2 + v_3R^3$$

Can Schwartz–Zippel lemma be applied to this? Like the odds of another set $$[v_0, \ldots v_3]$$ having hash $$H$$ are equal to the odds of another set $$[v_0, \ldots v_3]$$ being the zero polynomial? e.g. $$n/|F| = 4/2^{256}$$

As a followup, could I represent the algorithm like this: $$(v_0 + R)*(v_1 + R)*(v_2 + R)*(v_3 + R)$$? Would this be functionally the same (even though it reduces to different coefficients)?

Thanks for any help.

• Integers modulo $2^{256}$ form a ring, not a field. Argument: $2$ and $4$ haves no multiplicative inverses. $\mathbb F_{2^{256}}$ is a field, but is not integers modulo $2^{256}$; rather, it's elements can be described as polynomials with binary coefficients and degree less than 256, and it's multiplication is polynomial multiplication followed by reduction modulo some degree-256 irreducible polynomial with binary coefficients. $\mathbb F_{2^{256}-189}$ and $\mathbb F_{2^{256}+297}$ are fields that are integers modulo a prime.
– fgrieu
Commented Dec 20, 2022 at 7:49

## 1 Answer

The integers modulo $$2^{256}$$ are not a field but a ring with identity where every number divisible by $$2$$ is a zero divisor. See this question and its answer for conditions on applying Schwartz-Zippel (SZ) to rings. There are technical issues to be addressed, however you may just be happy with using the finite field $$\mathbb{F}_{2^{256}}$$ where the SZ lemma holds.

Your $$H(v_0,v_1,v_2,v_3)=v_0+v_1 R+ v_2 R^2+ v_3 R^3$$ being a multivariate linear polynomial in the $$v_i$$ (thanks to @DanielS for catching my error) has degree 1 and thus has at most 1 root1 in $$\mathbb{F}_{2^{256}}$$ so if you define the fingerprint of $$V=\{v_0,v_1,v_2,v_3\}$$ as $$H(v_0,v_1,v_2,v_3)$$ the probability that another 4 element set $$V='\{v_0',v_1',v_2',v_3'\}$$ will have the same fingerprint where $$V'\neq V$$ is $$\leq 1/2^{256}.$$

If you formulate your fingerprinting by using the second polynomial $$\Pi_{i=0}^3 (v_i+R)$$ this gives collision probability $$4/2^{256}$$ since it is actually of total degree 4 due to the $$v_0 v_1 v_2 v_4$$ term, while the first polynomial was degree 1. In practice, for such small sets, the difference in probability is negligible but for more sizeable sets it would be a problem.

• $H(v_0,v_1,v_2,v_3)$ is degree 1 in the $v_i$ and hence the probability of collision is $1/2^{256}$. We can check this by fixing $v_1’$, $v_2’$, $v_3’$ and letting $v_0’$ run over all possible values. (I’m assuming that $R$ is the same for all $H$, but even if it isn’t we can beat SZ in this case). Commented Dec 20, 2022 at 9:25