2
$\begingroup$

Let $F\colon K×K \rightarrow \{0,1\}^{128}$ be a $\mathit{PRF}$ function. Is $F'$ a $\mathit{PRF}$ ?

\begin{equation*} F'(x) = \begin{cases} 0^{128} & \quad \text{if $x = 0$} \\ F_k(x) & \quad \text{otherwise} \end{cases} \end{equation*}

EDIT:
I know that a $\mathit{PRF}$ over $(K,X,Y)$ is a bijective function $F\colon K×K \rightarrow Y$ that satisfies the following properties:

  1. Efficiency: $∀k ∈ K, x ∈ X, ∃ $ an algorithm to compute $F_k(x)$
  2. Pseudorandomness: $∀$ $\mathit{PPT}$ $D$ algorithm, $∃$ a negligible function so that:
    $|\Pr[D(r) = 1] - \Pr[D(F(.)) = 1]| < \mathit{negl}(n)$ where $r \leftarrow^R \mathrm{Func}(X,Y), k \leftarrow^RK$
$\endgroup$
1
$\begingroup$

You have listed two properties for something to be a PRF, efficiency and pseudorandomness.

The function $F'$ is clearly efficient as $F$ is efficient and $F'$ calls $F$ in just about every case. The one case where it doesn't is a very easily computable case too.

So, that leaves pseudorandomness. What that property is basically saying is imagine you are given a black box. You can feed it inputs (the x and k values) and see the outputs. If there exists a probabilistic polynomial time (PPT) algorithm that can, given the outputs, decide whether or not the black box implements $F'$ vs a random function, you do not have a PRF. On the other hand, if such a PPT algorithm does not exist, then you do have a PRF.

So, ultimately, the question is asking whether or not you can construct a PPT algorithm that can distinguish the outputs of $F'$ from outputs of a random function. If you can construct such an algorithm (fairly easy in this case), then you have proved that it is not a PRF.

Let's suppose, however, that the problem were setup differently and in fact $F'$ were a PRF. How would you prove that? You can't go through every possible PPT algorithm and show that it cannot distinguish outputs of $F'$ from outputs of a random function. Instead, you would assume that $F'$ is not a PRF and show how this would lead to a conclusion that $F$ is also not a PRF. In other words, a proof by contradiction.

$\endgroup$
  • $\begingroup$ > You can feed it inputs (the x and k values) and see the outputs. @mikeazo my understanding of the secure PRF game is that you (i.e. the adversary) can pick x values, but not k. k is randomly chosen from the Key-space by the blackbox at the start of the game. Is that accurate? $\endgroup$ – Savil Apr 11 '18 at 17:12
  • $\begingroup$ @Savil, In this case I don't think it matters, but in general you may be right. $\endgroup$ – mikeazo Apr 11 '18 at 17:20

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.