1
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – vimwitch
    Feb 18, 2023 at 23:22

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.