Am vrut să fac ceva practică cu privire la dovezile de reducere a securității și sunt nedumerit de acesta din cartea Boneh-Shoup.
Dacă $F(k, x)$ este un PRF sigur, apoi arată-l $F'(k, x) := F(F(k, 0^{n}), x)$ este un PRF sigur.
Ce am pana acum este:
Presupune $F'$ este nesigur, cu un distins $D'$. Aceasta înseamnă că $F$ este, de asemenea, nesigur, cu un distinctor $D$. Acum voi arăta construct $D$ folosind $D'$.
- $D$ primește o cheie, $k$.
- $D$ începe să alerge $D'$.
- Oricând $D'$ își interoghează oracolul pe un mesaj $x \leftarrow \lbrace0,1\rbrace^{n}$, da $x$ la $D$, calculează $y:= O(x)$, Unde $O$ este $D$oracolul lui. Apoi trimite $F(F(k, y), x)$ la $D'$.
- Ieșire orice $D'$ iesiri.
Aceasta înseamnă că:
Relatii cu publicul[$D'^{F'}(1^{n}) = 1] =$ Relatii cu publicul[$D^{F}(1^{n}) = 1]$ și Pr[$D'^{r}(1^{n}) = 1] =$ Relatii cu publicul[$D^{r}(1^{n}) = 1]$, Unde $r$ este o funcție aleatorie. De asemenea,
$|$Relatii cu publicul$[D^{F}(1^{n}) = 1] - Pr[D^{r}(1^{n}) = 1]| > $ neglijare$n$)
prin presupunere. Cu toate acestea, din moment ce $F$ este un PRF, aceasta este o contradicție, deci $F'$ este un PRF. $\pătrat$
Are sens această dovadă? Am senzația că am greșit definirea $D$, dar nu sunt sigur. Multumesc pentru orice ajutor!