Let $F(k,x)$ be a secure PRF over $(\mathcal{K},\mathcal{X},\mathcal{Y})$ where $\mathcal{K} = \mathcal{X} = \mathcal{Y} = \{0,1\}^n$.

Why is the function $F_1(k, (x_1, x_2)) = F(k, x_1) \oplus F(k, x_2)$ an unsecure PRF while the function $F_2(k, x) = F(k, x) \oplus x$ is a secure PRF?

  • $\begingroup$ What's $F_1(k, (x, x))$ for any $x$? $\endgroup$ – Squeamish Ossifrage Apr 17 '18 at 1:49
  • 2
    $\begingroup$ Suppose I have a random algorithm $A$ which distinguishes $x \mapsto F_2(k, x)$ from a uniform random function $G\colon \mathcal X \to \mathcal Y$. Can you define a random algorithm $A'$, using $A$ as a subroutine, which distinguishes $x \mapsto F(k, x)$ from a uniform random function $G\colon \mathcal X \to \mathcal Y$? If you're not sure how, can you quote the definition of the PRF-advantage of an algorithm $A$ for distinguishing $F_2$? $\endgroup$ – Squeamish Ossifrage Apr 17 '18 at 1:52
  • $\begingroup$ $F_1$ is a function that gets as input a key $k \in \mathcal{K}$ and a pair of elements $x_1,x_2 \in \mathcal{X}$ and returns $F(k, x_1) \oplus F(k, x_2)$. $\endgroup$ – Daniel Apr 17 '18 at 1:52
  • 2
    $\begingroup$ Yes, so what happens if $x_1 = x_2$? What is $F(k, x) \oplus F(k, x)$? $\endgroup$ – Squeamish Ossifrage Apr 17 '18 at 1:53
  • 2
    $\begingroup$ Does a uniform random function $G\colon \mathcal X \to \mathcal Y$ often return an $n$-bit $0$ string? $\endgroup$ – Squeamish Ossifrage Apr 17 '18 at 1:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.