$p$ is a large prime number. Consider the following function $F:\mathbb Z^*_p \times \mathbb D\rightarrow\mathbb Z^*_p$ where $\mathbb D=2,....,p-1$.

$F_k(x)=x^k \bmod p$

Proof that it's not a secure pseudorandom function.

What I‘ve tried:

I give a value to $x_1$ and obtain $y_1$, then I set $x_2 =y_1+p$. At the end $y_1$ is equal to $y_2$. Could this be right or is it totally wrong?


Hint: multiplicative property.

What you have tried does not work because $y_1=y_2$ does not hold in general when $x_2=y_1+p$ (further, adding $p$ is identity in $Z_p$ ).

You want to build a distinguisher for $F_k$. Arguably, $F_k(1)=1$ is enough for that, but you can build a more general distinguisher from $F_k(x_1\cdot x_2\bmod p)=F_k(x_1)\cdot F_k(x_2)\bmod p$.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.