# algorithms – 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. 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 will querry $$Z$$ on $$x$$, then it will somehow check if $$x$$ is in the image. But I am not sure how to do this.

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

Posted on Categories Articles