Я хотел немного попрактиковаться в доказательствах снижения безопасности, и я застрял на этом из книги Боне-Шоупа.
Если $F(к, х)$ является безопасным PRF, затем покажите, что $F'(k, x):= F(F(k, 0^{n}), x)$ является безопасным PRF.
Что у меня есть до сих пор:
Предполагать $F'$ ненадежно, с отличительным знаком $D'$. Это означает, что $F$ также ненадежно, с отличительным признаком $Д$. сейчас покажу конструкцию $Д$ с использованием $D'$.
- $Д$ получает ключ, $к$.
- $Д$ начинает работать $D'$.
- В любое время $D'$ запрашивает у своего оракула сообщение $x \leftarrow \lbrace0,1\rbrace^{n}$, дайте $х$ к $Д$, вычислить $у:= О(х)$, куда $О$ является $Д$оракул. Затем отправьте $F(F(к, у), х)$ к $D'$.
- Выводить что угодно $D'$ выходы.
Это означает, что:
пр[$D'^{F'}(1^{n}) = 1] =$ пр[$D^{F}(1^{n}) = 1]$ и Пр[$D'^{r}(1^{n}) = 1] =$ пр[$D^{r}(1^{n}) = 1]$, куда $г$ является случайной функцией. Также,
$|$Пр$[D^{F}(1^{n}) = 1] - Pr[D^{r}(1^{n}) = 1]| > $ негл($n$)
по предположению. Однако, поскольку $F$ является PRF, это противоречие, поэтому $F'$ является ПРФ. $\квадрат$
Имеет ли это доказательство смысл? У меня такое чувство, что я перепутал определение $Д$, но я не уверен. Спасибо за любую помощь!
