5
$\begingroup$

This is a well-known exercise that has already even been posted here.

I understand both arguments to prove and disprove that $F'$ and $\bar{F}$ are PRFs, as I explain below, however, it seems that the proof also applies to the case where $\bar{F}$ is not a PRF!

Assume $F$ is a PRF, then we have to prove that each of the following functions is a PRF or show a counter example

  1. $F'_k(x) = F_k(0\mathbin\|x) \mathbin\| F_k(1\mathbin\|x)$
  2. $\bar{F}_k(x) = F_k(0\mathbin\|x) \mathbin\| F_k(x\mathbin\|1)$

(Here $\mathbin\|$ represents concatenation)

The $\bar{F}$ from (2.) is not a PRF because a distinguisher can compute $\bar{F}_k(00...0) = F_k(000...0) \mathbin\| F_k(00...01)$ and $\bar{F}_k(00...1) = F_k(00...01) \mathbin\| F_k(00...011)$ and check if the first half of the bits of $\bar{F}_k(00...1)$ is equal to the second half of the bits of $\bar{F}_k(00...0)$. For a uniform $f$, this happens only with negligible probability.

Now, for $F'$ from (1.), since it is a PRF, we can construct a distinguisher $D$ for $F$ given a distinguisher $D'$ for $F'$

  1. $D'$ sends $x$ to $D$
  2. $D$ queries two times the oracle of $F$ to get $f(0\mathbin\|x)$ and $f(1\mathbin\|x)$ (where $f$ is uniform or $F_k$)
  3. $D$ sends $f'(x) = f(0\mathbin\|x) \mathbin\| f(1\mathbin\|x)$ to $D'$
  4. $D'$ outputs a bit $b'$
  5. $D$ outputs the same bit

The advantage of $D$ against $F$ is the same as the advantage of $D'$ in distinguishing $F'$ (unless I am missing something), but $\operatorname{Adv}(D')$ is non negligible by hypothesis, so $\operatorname{Adv}(D)$ is non-negligible, which contradicts the fact that $F$ is a PRF.

Therefore, $F'$ is also a PRF (end of proof)

Now it is the point where I am confused... It seems that if we replace steps (2.) and (3.) in the proof above so that $D$ obtains $f(0\mathbin\|x)\mathbin\|f(x\mathbin\|1)$, then we obtain a proof that $\bar{F}$ (from item (2.)) is a PRF, although we know it is not a PRF!

So what am I missing?

Or what is wrong with the proof?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

The advantages of $D$ and $D’$ are not the same. Recall that a distinguisher’s advantage is the difference between the probabilities that it accepts in the “real” and “ideal” experiments, where its oracle is either the function in question (with a random key) or a uniformly random function, respectively. So, to analyze $D$’s advantage and relate it to that of $D’$, you must consider both kinds of experiments.

In this case, when $f$ is a uniformly random function ($D$’s ideal experiment), $f’$ is not a uniformly random function. Indeed, $f’$ has the same property that the attack looks for (equality of two halves of two specific function outputs). As you noticed, this is very unlikely to hold for a random function. So, in this case $D’$ is under no obligation to behave as it would in its own ideal experiment. In particular, it might accept with the same probability as in its real experiment, making $D$’s advantage zero. (Indeed, this is the case if $D’$ is the stated attack.)

To put it another way: while the proposed reduction $D$ does properly “simulate” the real experiment to $D’$, it does not correctly simulate the ideal experiment. So, we cannot conclude that $D$ has the same advantage as $D’$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I am very thankful for your answer. Then in the first proof we also have to show that $f'(x) = f(0 || x) || f(1 || x)$ is uniform in the view of $D'$? But how can we do this please? $\endgroup$
    – Marcellus
    Jul 22, 2022 at 16:13
  • $\begingroup$ Correct. To do this, show that $f’$ maps each distinct input $x$ to a uniformly random and independent output. Use the fact that this holds for $f$ by assumption (because we are analyzing the “ideal” world), and some reasoning about the $f$-inputs $0x, $1x$ induced by $x$. $\endgroup$
    – Chris Peikert
    Jul 22, 2022 at 17:27
  • $\begingroup$ gotcha! If the image of $f$ is $\{0, 1\}^\ell$ and of $f'$ is $\{0, 1\}^{2\cdot \ell}$, then because $0||x$ is always different from $1||x$, we have for any $y = y_0||y_1$, $P [ f'(x) = y ] = P[ f(0||x) = y_0 \land f(1||x) = y_1 ] = P[ f(0||x) = y_0 ]\cdot P[ f(1||x) = y_1 ] = 2^{-2\cdot \ell}$, so $f'$ is uniform. Thank you very much! $\endgroup$
    – Marcellus
    Jul 23, 2022 at 12:27
  • $\begingroup$ This is almost an airtight argument. However, the reasoning should consider all $x$, not just one in isolation. This is because you need to show that all the $f’(x)$ are mutually independent for distinct $x$. (This is not the case, and is the fatal vulnerability, for the insecure construction.) To address this, observe that any two distinct $x,x’$ yield four distinct $0x, 1x, 0x’, 1x’$. $\endgroup$
    – Chris Peikert
    Jul 23, 2022 at 12:50
2
$\begingroup$

The problem is, that you are using a high level description of the reduction proof technique. I mean, that you just describe the idea, the steps of the reduction, but you are missing the deeper look into the math.

You have to evaluate the stochastic relationships in more detail. The reductive part only refers to the assumed function $F_k$. But it must also be shown that the breaking probability of the extension is negligible, too. In your words: You must show, that the advantages are (nearly) the same. For $F_k'$ this is simple and in the reference you already made.

But for $\overline{F}_k$ this is not possible. You can apply the same reduction to $\overline{F}_k$, but for the stochastical analysis, you will use the counterexample you already made. This would lead to a non negligible breaking probability. This would imply, that the advantages of breaking the PRF are not the same (or only have a negligible difference). This leads to the result, that $\overline{F}_k$ is not a PRF and hence making your claim from the first proof "The advantage of $D$ against $F$ is the same as the advantage of $D′$ in distinguishing $F′$" wrong for the given context of $\overline{F}_k$.

In conclusion: Your high level idea of reduction seems correct, but is missing the stochastical relations.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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