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.

  • $\begingroup$ 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? $\endgroup$ – Gabi G Nov 16 '20 at 11:33
  • $\begingroup$ If you can prove that it works, then it works. You don't need me for that. $\endgroup$ – Yuval Filmus Nov 16 '20 at 11:34
  • $\begingroup$ Okay, thank you! $\endgroup$ – Gabi G Nov 16 '20 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.