1
$\begingroup$

Assume that $F: \{0,1 \}^n \rightarrow \{0,1 \}^n$ is PRF. Examine if the following functions are PRFs:

$$ \begin{align} 1. \, F_1(k,x) &= F(k,x) \oplus x \\ 2. \, F_2(k,x) &= F\left(F(k,0^n), x\right) \\ 3. \, F_3(k,x) &= F\left(F(k,0^n), x\right)|| F(k,x) \end{align} $$

where $||$ denotes concatenation.


Attempt:

For $1.$ a standard distinguisher would be: $x_1 \oplus x_2 == y_1 \oplus y_2$, where $x_1, x_2$ are two inputs and $y_1, y_2$ are their outputs respectively. So $F_1$ is not a PRF.

For $2.$ I believe that $F(k,0^n) = k'$ acts as a key, so $F_2(k',x) = F(k',x)$ should still be a PRF.

For $3.$ I would say that the concatenation of two PRFs would still be a PRF, since you combine two pseudorandom outputs together to yield $F_3$'s output.

Can you verify my results?

$\endgroup$
9
  • 1
    $\begingroup$ For 1: $y_1\oplus y_2 = F(k,x_1) \oplus F(k,x_2) \oplus x_1 \oplus x_2$, which will only equal $x_1 \oplus x_2$ if $F(k,x_1) = F(k,x_2)$. For 3. Consider whether there's a way to find out the key used in the left half of the output. $\endgroup$ – Maeher Nov 18 '20 at 12:12
  • $\begingroup$ @Maeher So what can we say about the pseudorandomness of $1.$? $\endgroup$ – Paris Nov 18 '20 at 12:32
  • $\begingroup$ Hint: if you xor something with a value that's uniformly and independently distributed, what's the distribution of the result? $\endgroup$ – Maeher Nov 18 '20 at 13:55
  • $\begingroup$ After processing your comment, I believe that: for $1.$ since there is a neglible chance that $F(k,x_1) = F(k,x_2)$, then there's no way to distinguish between $F_1$ and a proper random function. For $3.$, if you set $x = 0^n$, the right half of the output is the key used in the left half, so not a PRF. Am I correct? $\endgroup$ – Paris Nov 18 '20 at 14:49
  • $\begingroup$ 1. That just means that your distinguisher doesn't work.You would generally be expected to do a proof by reduction to the security of $F$. 3. sounds like you're on the right track. $\endgroup$ – Maeher Nov 18 '20 at 14:58
2
+50
$\begingroup$

Unfortunately, I don't have time to go into every detail, but maybe it's enough to get you on the right track.

1. Is a PRF.

Proof Idea:

Assume we have a distinguisher $\mathcal{D}_{F_1}$ distinguishing $F_1$ from a random function with non-negligible probability. Then we can construct a distinguisher $\mathcal{D}_F$ distinguishing $F$ from a random function with non-negligible probability.

$\mathcal{D}_F$ is given access to an oracle $f(\cdot)$ that's either $F(k, \cdot)$ or a random function $g(\cdot)$.

$\mathcal{D}_F$ runs $\mathcal{D}_{F_1}$ and can answer its queries. When $\mathcal{D}_{F_1}$ requests $x$, $\mathcal{D}_{F}$ queries $f$ on $x$ and returns $f(x) \oplus x$ to $\mathcal{D}_{F_1}$. This simulates $\mathcal{D}_{F_1}$'s queries: when $f$ is $F(k, \cdot)$ we return $F(k, x) \oplus x$, which is exactly $F_1(k, x)$.

When $\mathcal{D}_{F_1}$ is done, we replicate its output: when it says it's talking to $F_1$ (output = 1), $\mathcal{D}_F$ outputs the same. When it says it's talking to a random function (output = 0), $\mathcal{D}_F$ outputs the same.

You would now have to prove that the advantage: $|\Pr[\mathcal{D}_F^{F(k, \cdot)}(1^n)=1] - \Pr[\mathcal{D}_F^{g(\cdot)}(1^n) = 1]|$ of $\mathcal{D}_F$ is non-negligible, using the assumption that the advantage of $\mathcal{D}_{F_1}$ is non-negligible.

This last part is usually the hard part, where errors can come up silently, so be careful about skipping steps or making invalid assumptions.

2.

Is a PRF.

Intuitively, the question of whether this is a PRF seems to reduce to whether an adversary can predict $F(k, 0^n)$. However, a function where this is possible for non-negligibly many $k$ is not a PRF.

3.

Not a PRF.

We can construct a distinguisher $\mathcal{D}$ with non-negligible advantage. $\mathcal{D}$ is given access to $f(\cdot)$, which is either $F_3(k, \cdot)$ or a random function. I denote the first half of $z$ as $z_L$ and the second half of $z$ as $z_R$.

  1. $\mathcal{D}$ queries $y^0 = f(0)$
  2. $\mathcal{D}$ computes $y^1 = F(y^0_R, x)$ for some random $x$.
  3. $\mathcal{D}$ queries $y^2 = f(x)$
  4. If $y^1 = y^2_L$, $\mathcal{D}$ outputs that $f$ is $F_3$.
  5. Otherwise, $\mathcal{D}$ outputs that $f$ is a random function.

$\mathcal{D}$ has non-negligible advantage: if $f$ is $F_3$, then $y^1 = y^2_L$:

$y^1 = F(y^0_R, x) = F(f(0^n), x) = F(F(k, 0^n), x)$

$y^2_L = f(x)_L = F_3(k, x)_L = F(F(k, 0^n), x)$

The probability that this holds when $f$ is a random function is negligible.

Hope I could help!

$\endgroup$
7
  • $\begingroup$ I'm still uncertain about the claim 2, and dubious about the argument made. What about if there's a random-like subset $\mathcal S$ of $\{0,1\}$, and when $k\in\mathcal S$ then $F(k,x)=0^n$, else if $x=0^n$ then $F(k,x)$ is a pseudo-random element of $\mathcal S$, else $F(k,x)$ is a true PRF of $(k,x)$? Now $F_2(k,x)$ is always $0^n$, yet an adversary can't predict $F(k,0^n)$. $\endgroup$ – fgrieu Nov 21 '20 at 20:55
  • $\begingroup$ That's true, the adversary doesn't need to predict - after all it's a distinguishing game. I was only giving some intuition on how this proof could be approached, but I cannot even guarantee my answer is correct, since I have not proved it. (cont...) $\endgroup$ – cisnjxqu Nov 21 '20 at 21:08
  • $\begingroup$ As you say, $F$ can have some weak keys $k \in S$, where the output of $F(k, x) = 0^n$. However, $S$ cannot be noticeably large, otherwise $F$ wouldn't be a PRF, since the adversary would be able to easily determine that the output is $0^n$ for all $x$ for noticeably many $k$. Therefore, $S$ must be some negligible fraction of the key domain, and will give the adversary only negligible advantage. $\endgroup$ – cisnjxqu Nov 21 '20 at 21:09
  • $\begingroup$ Notice that my weak key set has size such that it's chosen with negligible probability $2^{-n/2}$, thus $F(k,x)$ can only be distinguished from random by one applying the algorithm implementing $F$ (feeding the result obtained from the oracle queried with $x=0^k$ into the key input of that algorithm). If the definition of the PRF challenge allows that, then indeed $F_2$ is demonstrably a PRF when $F$ is, otherwise my counterexampel $F$ seems to be a PRF, but definitely $F_2$ is not. $\endgroup$ – fgrieu Nov 21 '20 at 21:20
  • $\begingroup$ Could you elaborate on some things: Do you mean that $|S| = 2^{\frac{n}{2}}$? If the definition of the PRF game (?) allows the adversary to evaluate $F(k, x)$ for some adversary chosen $k$ and $x$, then $F_2$ is a PRF? Could you explain why $F_2$ would not be a PRF if that's not the case? $\endgroup$ – cisnjxqu Nov 21 '20 at 21:34
3
$\begingroup$

Since @fgrieu was interested in question 2, I'm going to break with site policy and give a full answer for that part, even though this is almost certainly homework.

Theorem. Let $F : \{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$ be a PRF. Then, $F_2 : \{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$, defined as $$F_2(k,x) := F(F(k,0^n),x)$$ is also a PRF.

Before we give a formal proof, let's build some intuition why this should be the case. Note that the inner invocation of $F$ is not on some part of the input, but instead on a constant (i.e., $0^n$). This means that once we fix the key $k$, the key used by the outer invocation of $F$ for all evaluations of $F_2$ is a fixed key $k' := F(k,0^n)$. Since $k$ is not used elsewhere in the construction, $k'$ should, by the security of the underlying PRF, be indistinguishable from a uniformly random key $k''$, as long as $k$ is chosen uniformly at random. This would mean than an oracle evaluating $F_2(k,\cdot)$ and an oracle evaluating $F(k,\cdot)$ should in fact be indistinguishable. Since $F(k,\cdot)$ is already known to be indistinguishable from a uniformly chosen random function $f(\cdot)$ and indistinguishablity (in the asymptotic sense) is transitive, it would follow that $F_2$ must also be a PRF.

So let's formalize this intuition.

Proof. Let $A$ be an arbitrary PPT algorithm with $$\Bigl|\Pr_k[A^{F_2(k,\cdot)}(1^n)=1] - \Pr_f[A^{f(\cdot)}(1^n)=1]\Bigr|=\epsilon(n).$$ We are looking to give a negligible upper bound for $\epsilon$. To do this we will prove a series of claims.

Claim 1. $\Bigl|\Pr\limits_k[A^{F(F(k,0^n),\cdot)}(1^n)=1] - \Pr\limits_{f}[A^{F(f(0^n),\cdot)}(1^n)=1]\Bigr| \leq \mathsf{negl}(n)$

Consider the following adversary $B$ against the PRF security of $F$. Upon input $1^n$ and given access to an oracle, $B$ queries $0^n$ to the oracle an receives back a value $k'$. It then invokes $A$ on input $1^n$. Whenever $A$ sends a query $x$ to its oracle, $B$ responds by computing $y:=F(k',x)$. Eventually, $A$ will output a bit $b$ which $B$ also outputs.

It is easy to see that $$\Pr_k[B^{F(k,\cdot)}(1^n)=1] = \Pr_k[A^{F(F(k,0^n),\cdot)}(1^n)=1]$$ and $$\Pr_f[B^{f(\cdot)}(1^n)=1] = \Pr_f[A^{F(f(0^n),\cdot)}(1^n)=1].$$ Further, since $F$ is a secure PRF, it must hold that $$\Bigl|\Pr_k[B^{F(k,\cdot)}(1^n)=1]-\Pr_f[B^{f(\cdot)}(1^n)=1]\Bigr|\leq \mathsf{negl}(n)$$ and the claim follows.

Claim 2. $\Pr\limits_{f}[A^{F(f(0^n),\cdot)}(1^n)=1] = \Pr\limits_{k}[A^{F(k,\cdot)}(1^n)=1]$

To see that this is the case, it is easiest to think of $f$ as being lazily sampled when queried. Since $f$ is only ever invoked on $0^n$, sampling $f$ is equivalent to simply sampling $f(0^n)$ once as a uniformly random value $k\in \{0,1\}$, which is identical to the right hand side.

Claim 3. $\Bigl|\Pr_{k}[A^{F(k,\cdot)}(1^n)=1] - \Pr_{f}[A^{f(\cdot)}(1^n)=1]\Bigr| \leq \mathsf{negl}(n)$

This claim is in fact just a restatement of the assumption that $F$ is a PRF and thus follows trivially.

Using the triangle inequality, we can conclude \begin{align} \epsilon(n) =&\quad \Bigl|\Pr_k[A^{F_2(k,\cdot)}(1^n)=1] - \Pr_f[A^{f(\cdot)}(1^n)=1]\Bigr|\\ \leq&\quad\Bigl|\Pr\limits_k[A^{F(F(k,0^n),\cdot)}(1^n)=1] - \Pr\limits_{f}[A^{F(f(0^n),\cdot)}(1^n)=1]\Bigr|\\ &+ \Bigl|\Pr\limits_{f}[A^{F(f(0^n),\cdot)}(1^n)=1] - \Pr\limits_{k}[A^{F(k,\cdot)}(1^n)=1]\Bigr|\\ &+ \Bigl|\Pr_{k}[A^{F(k,\cdot)}(1^n)=1] - \Pr_{f}[A^{f(\cdot)}(1^n)=1]\Bigr|\\ &\leq 2\cdot\mathsf{negl}(n) \end{align} and the theorem statement immediately follows.$\tag*{$\square$}$

$\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.