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

Question

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

Answer 1

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.