0
$\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?

New contributor
Paris is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
  • 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 at 12:12
  • $\begingroup$ @Maeher So what can we say about the pseudorandomness of $1.$? $\endgroup$ – Paris Nov 18 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 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 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 at 14:58
1
$\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!

| improve this answer | |
$\endgroup$
  • $\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 yesterday
  • $\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 yesterday
  • $\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 yesterday
  • $\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 yesterday
  • $\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 yesterday

Your Answer

Paris is a new contributor. Be nice, and check out our Code of Conduct.

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.