Score:1

Data fingerprint using multiple multilinear polynomials

vc flag

Related to this question. I'm trying to find a way to use this fingerprint system without a second pre-image attack.

Assume I have a set of elements $V = [v_0, v_1, v_2]$ in $\mathbb{F}_p$. Assume the elements of $V$ are randomly distributed over the field.

I have two random values in the field, $R_0$ and $R_1$, both non-zero.

I consider the fingerprint to be two points in the field defined by:

$P_0(V) = v_0*R_0 + v_1*R_0^2 + v_2*R_0^3$

$P_1(V) = v_0*R_1 + v_1*R_1^2 + v_2*R_1^3$

Thus the fingerprint is a vector equation $H(V) = [P_0(V), P_1(V)]$.

Is this approach safe from a second pre-image attack? e.g. how hard would it be to choose a $V'$ where $V \ne V'$ and $H(V) = H(V')$? Does the difficulty change with the cardinality of $V$?

Thanks

Score:1
sa flag

The point $P_i=f'(R_i),$ where $f'(x)=v_0 x+ v_0 x^2+v_0 x^3$ is a polynomial,.Normally one would also include a constant term in the polynomial. I will assume that for simplicity.

In any case, since the set of polynomials over $\mathbb{F}_p$ is closed under addition and scalar multiplication, what you are doing would directly correspond to using a linear code, in this case a Reed-Solomon code if the $x$ term was not there. So I will define $f(x)=f'(x)/x,$ and work with that.

It is very easy to mount a second-preimage attack on this method. First compute any point in the nullspace of the mapping $x\mapsto f(x),$ call it $N_f\subset \mathbb{F}_p.$ Thus find any value $R'$ such that $f(R')=0.$ This can be easily done by trial and error. Since the polynomial $f(x)/x$ has degree 2, it has lots of roots in $\mathbb{F}_p.$ Having done this, any point of the form $R_0+\alpha R'$ with $\alpha\neq 0,$ will also satisfy $P'(V)=f(R')=x,$ if $P_0(V)=f(R_0)=x.$

Technical Note: Since you have included an extra multiplicative term of $x$ in your definition, and the difference of the values need not have an $x$ term, you are looking at an affine subspace as opposed to a linear subspace which is the reason for your difficulty in attempting this problem.

vimwitch avatar
vc flag
Ah I think I wrote this in a confusing way. $R_0$ and $R_1$ are constants, thus the exponentiated $R$ values e.g. $R_0^2$ are the constant coefficients to the variables $v_x$.
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.