2
$\begingroup$

enter image description here

Hey crypto SE, i'm having a bit of trouble with this question. Can anyone help me to understand how to go about solving this problem? Any help is appreciated :)

Show G is insecure against adaptive adversaries by designing an adaptive adversary?

Is it possible that a comparable advantage could be achieved by a non-adaptive adversary.

$\endgroup$
  • $\begingroup$ Would trying to find $F_K(F_K(F_K(x)))$ help you? (Hint: It does!) $\endgroup$ – SEJPM Feb 3 '17 at 19:37
3
$\begingroup$

(a) Adaptive case: To show that the adversary can get a very large advantage, send an arbitrary query $x$ to the oracle. The left part of the response is the input of the second query. If the oracle is a PRF, the left part of the second response equals the right part of the first response. If the oracle is a random oracle the two parts are not equal with a very high probability $p \rightarrow 1$ for $n \rightarrow \infty$.

Let $$L: \{0,1\}^{2n} \rightarrow \{0,1\}^n, ~L(x_1, \ldots, x_n, x_{n+1}, \ldots, x_{2n}) = (x_1, \ldots, x_n)$$ and $$R: \{0,1\}^{2n} \rightarrow \{0,1\}^n, L(x_1, \ldots, x_n, x_{n+1}, \ldots, x_{2n}) = (x_{n+1}, \ldots, x_{2n})$$ be the projection to the left and right $n$ Bits, respectively.

  1. Query $$G_k(x) = F_K(x) \parallel F_K(F_K(x))$$

  2. Query $$G_k(L(G_k(x))) = F_K(L(G_k(x))) \parallel F_K(F_K(L(G_k(x)))) = F_K(F_K(x)) \parallel F_K(F_K(F_K(x)))$$

And hence $$R(G_k(x)) = L(G_k(L(G_k(x))))$$

(b) Non-adaptive case: Since $F$ is a PRF both $F_K(x)$ and $F_K(F_K(x))$, and hence $G_k(x)$ cannot be distinguished from random output. Since the inputs in a sequence of queries are chosen beforehand, their responses appear completely unrelated and do not provide any information about the nature of the oracle.

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