8
$\begingroup$

First, I want to clarify this is not homework. I encountered this question (here How can I prove that a function F isn't a pseudo random function?) while studying for a test coming soon.

  1. $F'_k(x) = F_k(0||x) || F_k(1||x)$
  2. $F'_k(x) = F_k(0||x) || F_k(x||1)$

(Here $||$ representing concatenation, $F$ is a PRF).

I know that the second function is not a PRF and I came up with an adversary for it by myself.

As for the first fuction, I read comments saying it is a PRF, but I couldn't find a way to formally prove this. I know the method of proving these kinds of questions.

I should assume by contradiction that $F'_K$ is not a PRF, namely it has an adversary $D'$ that distinguishes between $F'_K$ and a random function $f'$ with non-negligible probability. Using $D'$, I should construct an adversary $D$ that distinguishes between $F_K$ and a random function $f$ with non-negligible probability - which is a contradiction.

I thought of the following reduction for constructing $D$:

Given an input $x$, and a oracle access $O$ (for $F_K$), $D$ runs $D'$ on $O(0||x)||O(1||x)$. Then, $D$ answers what $D'$ answers.

  • If $O=F_k$ , then $D$'s probability of distinguishing is equal to $D'$'s.
  • If $O=f$ (the random function) - Well, here I'm stuck.
$\endgroup$
  • $\begingroup$ We do answer homework questions if enough has been done to solve it yourself. So although this is not homework, it would be on-topic if it was :) $\endgroup$ – Maarten - reinstate Monica Aug 3 '17 at 23:54
  • 1
    $\begingroup$ Could you explain the distinguisher for 2.? I don't quite see it. $\endgroup$ – Occams_Trimmer Aug 4 '17 at 8:11
  • 2
    $\begingroup$ Find $x \neq y$ such that $0\|x = y \| 1$. Then different outputs of $F'_k$ have halves in common, which shouldn't happen with probability 1. $\endgroup$ – Samuel Neves Aug 4 '17 at 8:27
  • $\begingroup$ @Occams_Trimmer, $D$ the distiguisher: given an oracle access $O$, query $O(0||x)$, $O(1||x)$ and obtain responses $s_1$, $s_2$ respectively. Then $D$ runs $D'$ on $s_1||s_2$ and answers what $D'$ answers. If $O=F_k$, $D$ runs $D'(F_k(0||x)||F_k(1||x))$, and since $D$ answers what $D'$ answers - they have the same probability to distinguish. If $O=f$ (the random function), $D$ runs $D'(f(0||x)||f(1||x))$, and as I said, here I'm stuck. I'm not sure how to prove that $f(0||x)||f(1||x)$ is random (maybe it's not random at all). $\endgroup$ – giselle Aug 4 '17 at 9:20
  • $\begingroup$ @SamuelNeves, could you elaborate? I don't quite understand. $\endgroup$ – giselle Aug 4 '17 at 9:21
6
$\begingroup$

This is not exactly the way you're going about it, but I find it an easier way to deal with this kind of construction in general. First we switch to an information-theoretic setting, then go back to the concrete construction. This is very similar to proving the security of counter mode encryption.

First, we replace $F_k$ by a real random function $G$. Every new input to $G$ results in a uniformly random output $G(x) \in \{0,1\}^{n}$. Now we have the corresponding $$ G'(x) = G(0\|x)\|G(1\|x)\,. $$ Since every call to $F_k'$ gives you two free calls to $F_k$, we have $$ \mathbf{Adv}^{\mathrm{prf}}_{F_k'}(D) \le \mathbf{Adv}^{\mathrm{prf}}_{F_k}(D') + |\mathbf{Pr}[D(G') = 1] - \mathbf{Pr}[D(\$) = 1]| \,, $$ for a distinguisher $D'$ that performs at most $2q$ queries, by the triangle inequality (the first term being $\Delta_D(F_k', G')$, and the second being $\Delta_D(G', \$)$. $\$$ represents the ideal random function).

Our goal now is to distinguish $G'$ from a uniformly random function from $\{0,1\}^{n-1}$ to $\{0,1\}^{2n}$, to determine the second term of the above inequality. Notice that the inputs to $G$ are properly domain-separated: there are never any collisions between $0\|x$ and $1\|x$ for any distinct $x$.

More concretely, take any set of (distinct) queries $((x_1, y_1), (x_2, y_2), \dots, (x_q, y_q))$, where $y_i = \mathcal{O}(x_i)$. The probability that $G'(x_1) = y_1$, $G'(x_2) = y_2$, $\dots$, $G'(x_q) = y_q$ is $\left(\frac{1}{2^{n}}\frac{1}{2^{n}}\right)^q = 2^{-2nq}$. The probability for a random function is also $2^{-2nq}$, as each output has independent probability $2^{-2n}$.

The definition of advantage is $$ |\mathbf{Pr}[D(F) = 1] - \mathbf{Pr}[D(\$) = 1]|\,, $$ for any distinguisher $D$. From this we conclude that the advantage of any attacker against $G'$ is $0$, since it has exactly the same probability distribution as the random function. So we conclude that $$ \mathbf{Adv}^{\mathrm{prf}}_{F_k'}(D) \le \mathbf{Adv}^{\mathrm{prf}}_{F_k}(D') + 0 \,. $$

$\endgroup$
2
$\begingroup$

Constructing a distinguisher $D$ for $F$ from a distinguisher $D'$ for $F'$. $D$ runs $D'$. When $D'$ asks to call its oracle on a string $x$, $D$ calls its oracle on the strings $0||x$ and $1||x$, concatenates the answers, and gives the resulting string to $D'$ as its answer. Finally $D$ outputs what $D'$ outputs.

It is clear that

  • $D$ runs in poly time if $D'$ does;
  • if $D$'s oracle implements $F$, its success probability is the same as that of $D'$ when its oracle implements $F'$; and
  • if $D$'s oracle implements a random function, its success probability is the same as that of $D'$ when its oracle does likewise.

P.S.: The distinguisher is not given any input string, only the security parameter. It chooses input strings according to its definition.

$\endgroup$

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.