# Data fingerprint using multiple multilinear polynomials

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

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.
• 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$. Feb 18, 2023 at 23:22