# How can I prove that a function F isn't a pseudo random function?

Let $$F$$ be a length-preserving pseudorandom function. For the following constructions of a keyed function $$F' : \{0, 1\}^n \times \{0, 1\}^{n−1} \to \{0, 1\}^{2n}$$, state whether $$F'$$ is a pseudorandom function. If yes, prove it; if not, show an attack.

$$F'_k(x) = F_k(0 ∥ x) ∥ F_k(1 ∥ x) \tag{a}$$

and

$$F'_k(x) = F_k(0 ∥ x) ∥ F_k(x ∥ 1) \tag{b}$$

I don't want the solution: I want to understand how I can solve this type of exercise.

• Comments are not for extended discussion; this conversation has been moved to chat. – e-sushi Aug 5 '17 at 4:56

your title asks "How to prove that a function F isn't a pseudo random function", in your question case (b) is not PRF which is easy to prove. function $F'$ is PRF if for all PPT distingushers $D$, success probability of $D$ distinguishing $F'$ from random function be negligible. So for proving that function $F'$ is not PRF it suffices to construct one distinguisher (which queries to its oracle and look for non-random patterns) with non-negligible success probability.

In contrast case (a) here is PRF, which is harder to proof. for proving function $F'$ is PRF as @fkraiem mentioned suppose $F'$ is not PRF and $D'$ is distinguisher for $F'$ then construct an algorithm $A$ which breaks some assumption (Distingush $F$ from random function here breaks assumption of $F$ being PRF).

The general approach for proving that something is not a PRF is to come up with a distinguisher for it. A general approach for proving that a construction $F'$ from a PRF $F$ is also pseudo-random is to prove the contrapositive. That is we prove the contrapositive of

$F$ is pseudo-random implies $F'$ is pseudo-random

which is

$F'$ is not pseudo-random implies $F$ is not pseudo-random.

This is easier to prove as we assume that there is some distinguisher $D'$ which distinguishes $F'$ from a random oracle, and then prove that this implies there is some distinguisher $D$, distinguishing $F$ from a random oracle. To do this, we can show that if $D$ is playing the PRF game against a challenger who has chosen $F$ or a random oracle, then $D$ may simulate (in a polynomial number of queries to the challenger) the PRF game between $D'$ and a challenger who has chosen $F'$ or a random oracle. You could think of this interaction as though $D$ has $D'$ in it's belly, and uses it to win the PRF game as shown in the picture

To get an intuitive sens of how this "reduction" would work for this example, imagine that for each query $x_i$ that $D'$ makes, $D$ takes that query and queries the challenger twice (once for $0||x_i$, and once for $1||x$) returning, the concatenation of both of these queries to $D'$. This has effectively made it so that $D$ has returned $F'_k(x_i)$ to $D'$, and in this way simulates that $D'$ is interacting with a challenger for the PRF $F'_k$. Since this simulation was done with a polynomial number of queries (2x as many), if $D$ responds with the same answer that $D'$ produces, it will have the same advantage as $D'$. Thus, if $D'$ has non-negligible advantage, so does, $D$, which is the contrapositive we sought to prove.

A hint for part (a): If $$R(x)$$ is a truly random function, then so is $$R'(x) = R(0|x) | R(1|x)$$

Now to prove [$$F$$ pseudorandom $$\implies F'$$ pseudorandom],

we will prove the contrapositive [$$F'$$ not pseudorandom $$\implies F$$ not pseudorandom].

Suppose $$F'$$ is not pseudorandom. That means there is a distinguisher $$D'$$ which can guess with a probability higher than $$\frac{1}{2} + \frac{1}{p(n)}$$ whether it interacts with $$F'$$ or $$R'$$. How can you use $$D'$$ to construct a distinguisher $$D$$ which would guess with a probability higher than $$\frac{1}{2} + \frac{1}{p(n)}$$ whether it interacts with $$F$$ or $$R$$?

A lot of answers here for part (a) about how to use distinguisher for F' into distinguisher for F. A hint for part b). Suppose we have some $$x' \in \{0,1\}^{n-2}$$, what do you expect to get for $$F'_k(x'||1)$$ and $$F'_k(0||x')$$.