7
$\begingroup$

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.

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

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

$\endgroup$
5
$\begingroup$

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

enter image description here

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.

$\endgroup$

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