Join Log in
Score:1
vimwitch avatar Crypto

Data fingerprint using polynomial and Schwartz-Zippel Lemma

vc flag
vimwitch

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.

246
1 + 1
fgrieu avatar
ng flag
fgrieu
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.
2
Reply
Score:3
kodlu avatar Crypto
sa flag
kodlu

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.

+ 1
Daniel S avatar
ru flag
Daniel S
$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).
1
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.