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. Since the matrix $A \in G^{m \times n}$, we can take $m \times n$ base elements of $G^{m \times n}$, and check that for elements in $G^m$ if they are in $Ax$.
I tried to describe the following adversary B:
on input $x \in G^m$ and access to oracle $Z()$, A$B$ will querrytake $Z$ on$n$ base elements of $x$$G^m$ and run $Z()$ on them. Then, then it$B$ will somehow check if $x$$ x \in span\{Z(e_1), \cdots , Z(e_n) \}$ and return 1 if it is in the image. But
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 doget 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$.