1
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    Dec 20, 2022 at 7:49

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ $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). $\endgroup$
    – Daniel S
    Dec 20, 2022 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.