# Is $F(x) =Ax+b$ a pseudorandom function or not?

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.

• Hint; Gaussian? – kelalaka Oct 24 '18 at 11:25
• Hint: what does $F_{A,b}(x)+F_{A,b}(y)$ equal? – Yehuda Lindell Oct 24 '18 at 15:45
• This is exercise 3.13 in Katz and Lindell book, 2nd edition. – Rodrigo 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.

• 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 – Rodrigo Nov 19 '18 at 16:26

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

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