# Check if a linear function or an affine function can be a pseudo random function

Let $$G = \{0, \cdots , p-1 \}$$ be a field. Let $$K = G^{m \times n}$$ and $$F:K \times G^n \to G^m$$ be a family of functions.

For $$A \in G^{m \times n}$$ and $$x \in G^n$$ we have $$F(A,x) = Ax$$.

I need to check if $$F$$ is a secure pseudo random function.

We say that PRF $$H: K \times X \to Y$$ is $$(T, \epsilon)$$-secure if for every algorithm $$B: X \to \{0,1\}$$ of size $$T$$ it follows: $$|P(B^{H_k()} = 1) - (B^{R()} = 1)| \le \epsilon$$ where $$H_k(x) = H(k,x)$$, $$R:X \to Y$$ is a random function, and $$B^{S()}$$ means $$B$$ has oracle access to the function $$S$$.

Now, back to the question, I tried to describe the following adversary B:

on input $$x \in G^m$$ and access to oracle $$Z()$$, $$B$$ will take $$n$$ base elements of $$G^m$$ and run $$Z()$$ on them. Then, $$B$$ will check if $$x \in span\{Z(e_1), \cdots , Z(e_n) \}$$ and return 1 if it is.

This way I get that $$P(B^{H_k()} = 1) = 1$$ and if $$m > n$$ then $$P(B^{R()} = 1) \le \frac{1}{p^{m-n}}$$, which proves that $$H$$ is not secure.

The only problem is when $$n \ge m$$, since I am not sure how to get a good bound on $$P(B^{R()} = 1)$$ in this case.

Help would be very appreciated!

There is also the same question but with $$K = G^{m \times n} \times G^m$$ and $$F:K \times G^n \to G^m$$, $$F((A,b), x) = Ax+b$$.

Intuitively, pseudorandom functions are functions that look random. A linear function $$f$$ satisfies $$f(x+y) = f(x)+f(y)$$ for all $$x,y$$, which is highly unlikely for a random function. Similarly, an affine function $$f$$ satisfies $$f(x+y) - f(x+z) = f(y) - f(z)$$ for all $$x,y,z$$, which is highly unlikely for a random function.
• Then in the linear function case, on input $x$, I can ask the oracle about $x$ and $(1, \cdots , 1)$ and it will make $B$ break the PRF, right? – Gabi G Nov 16 '20 at 11:33