Consider the following keyed function $F$: For security parameter $n,$ the key is an $n\times n$ boolean matrix $A$ and an $n-$bit boolean vector $b$. Define $F_{A,b} : \{0, 1\}^n->\{0, 1\}^n$ by $F_{A,b}(x) = Ax + b$, where all operations are done modulo $2.$ Show that $F$ is not a pseudorandom function.

I have thought for a whole day but could not conquer it, so hope to get the solution here. Thanks.

  • $\begingroup$ Hint; Gaussian? $\endgroup$ – kelalaka Oct 24 '18 at 11:25
  • $\begingroup$ Hint: what does $F_{A,b}(x)+F_{A,b}(y)$ equal? $\endgroup$ – Yehuda Lindell Oct 24 '18 at 15:45
  • $\begingroup$ This is exercise 3.13 in Katz and Lindell book, 2nd edition. $\endgroup$ – Javier Nov 19 '18 at 15:57

I have searched the similar question in network and drawn a solution as follows:

Let's consider the distinguisher $D$ that queries its oracle $\mathcal{O}$ on arbitrary. At first, let $x=0^n$, we can get $b=\mathcal{O}(0^n)$. Then, we access the $\mathcal{O}$ with $x_1$, $x_2$, $x_1+x_2$, output $1$ if and only if $\mathcal{O}(x_1 )+\mathcal{O}(x_2 )-b=\mathcal{O}(x_1+x_2)$.

  • If $\mathcal{O}=F$, $Pr⁡\left[D^F{^{(\cdot)}} (1^n)=1\right]=1$.
  • If $\mathcal{O}=F$ for f chosen uniformly from $Func_n$, $Pr⁡[D^{f(\cdot)} (1^n )=1]=2^{-n}$.

The difference is $|1-2^{-n}|$, which is not negligible. Therefore, F is not a pseudorandom function.

  • $\begingroup$ following the recommendation of Yehuda Lindell you could take out the computation of $b$, I think it is not necessary to obtain the same conclusion $\endgroup$ – Javier Nov 19 '18 at 16:26

F verifies tons of equalities like $F(2x) = (F(x) + F(3x)) / 2$. It is highly non random.

  • $\begingroup$ Yes. Because I don't know how the distinguishable experiment goes at first, I fail to solve it. $\endgroup$ – zack h Oct 28 '18 at 2:21

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.