$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?


1 Answer 1


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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