Data fingerprint using multiple multilinear polynomials

Question

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

Answer 1

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.