7.6 풀이

가정에서 언급되는 key-recovery attack을 구현한 adversary를 $\mathcal A$라고 하자. $\mathcal A$에게 $F_k$의 oracle access를 주면 $n$번의 시행 후 키 $k$를 반환한다.

이제 이 $\mathcal A$를 사용해 distinguisher $D$를 구성한다. $D$는 우선 $\mathcal A$에게 oracle $\mathcal O$를 넘겨주고, $k$를 먼저 받는다. 이후 $x \in \{ 0, 1 \}^n$를 골라 $\mathcal O(x) = F_k(x)$라면 $1$을 반환한다.

$$\left|P(D^{F_k}(1^n) = 1) - P(D^f(1^n) = 1)\right| \leq {\rm negl}(n)$$

$D$가 위 수식을 만족하면 $F_k$는 pseudorandom permutation이다. 위에서 구성한 $D$를 사용하면 좌변은 $1$이 되고, 우변은 $\dfrac1{n!}$이 된다. 이는 negligible하지 않으므로, $F_k$는 pseudorandom permutation이 아니다.