4
$\begingroup$

I am new in Cryptography and I saw this question in a note I solved it but I'm not sure about my answers.

Let $F : \{0, 1\}^n × \{0, 1\}^n→ \{0, 1\}^n$ be a secure PRF (i.e. a PRF where the key space, input space, and output space are all $\{0, 1\}^n$) and say $n = 128$. Which of the following is a secure PRF. In the following functions, + operation indicates the binary sum module $2^n$ where an n-bit string is interpreted as number in $Z_{2^n}$ and $≪$ operation indicates left rotation.

  1. $F ′(k1||k2), x) = F (k1, x) ⊕ F (k2, x)$
  2. $F ′(k, x) = (x + k) ⊕ (x ≪ 1)$
  3. $F ′(k, x) = (x + k) ⊕ (k ≪ 1)$
  4. $F ′(k, x) = (x + k) ⊕ (k ≪ 1) ⊕ (x ≪ 1)$

I think number 1 is PRF because the input key of each F is different, and number 2, 3, 4 are PRF because $x+k$ term could be any string of $\{0, 1\}^n$. Is that correct?

$\endgroup$
  • 1
    $\begingroup$ In 2-4, your reasoning also applies to $F'(k, x) = x$, which is clearly not PRF. $\endgroup$ – otus Nov 23 '15 at 9:40
  • $\begingroup$ @otus in that case you said we have distinguisher function with $adv = 1$ but in the questions I couldn't find any distinguisher function! $\endgroup$ – Kiriptogeraaf Nov 23 '15 at 9:50
4
$\begingroup$

I think number 1 is PRF because the input key of each F is different

That is correct, though I might not give full marks for your reasoning. The XOR of two PRFs is PRF. The probability that a random $k1||k2$ has $k1 = k2$ is negligible.

number 2, 3, 4 are PRF because $x+k$ term could be any string of $\{0, 1\}^n$. Is that correct?

This is wrong. You can come up with distinguishers for them. I've spoilered my solutions below if you want to try them individually.

2:

In the second case, you can calculate $(F'(k, x) \oplus x) - x$ to find the key, and thus find the value for any $x$ so it is not PRF.

3:

In the third case, you can look at the low bit: $f_1 = x_1 \oplus k_1 \oplus k_n$. So by calculating $k_1 \oplus k_n$ from one value of $F'$ you can predict the value for any $x$. Again, not PRF, since you have a distinguisher for the low bit.

4:

The fourth case reduces to the third, because you can just XOR out the $x \ll 1$ term.

$\endgroup$
2
$\begingroup$

Here's a more elaborate proof for number 1. Given a distinguisher $D'$ for $F'$, we construct a distinguisher $D$ for $F$ as follows: we first pick a uniform $k_2$ of length $n$, and we run $D'$. When $D'$ asks to call its oracle on a string $x$, we give it $O_D(x) \oplus F_{k_2}(x)$ instead of $O_{D'}(x)$, where $O_D$ (resp. $O_{D'}$) is the oracle of $D$ (resp. $D'$). At the end, we output whatever $D'$ outputs.

If $O_D$ implements $F_{k_1}$ for a uniform $k_1$, $O_D(x) \oplus F_{k_2}(x)$ will be distributed identically to $F'_{k_1||k_2}(x)$ for a uniform $k_1||k_2$, whereas if $O_D$ implements a uniform $f$, it will be distributed identically to $f(x)$ for a uniform $f$. Those two cases can be distinguished by $D'$ by hypothesis, and thus $D$ can distinguish $F_{k_1}$ from a uniform $f$.

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