Această întrebare poate fi legată de Aceasta, deși construcția diferă.
Să luăm în considerare un PRF $f$. Noi definim $g_k$ la fel de $g_k(x)=f(x)\oplus f(x\oplus k)$. Este $g_k$ un PRF, presupunând $k$ este ales la întâmplare?
Am încercat să demonstrez acest lucru după cum urmează. Să considerăm un adversar $\mathcal{A}$ care este capabil să distingă între $g_k$ și un PRF cu avantaj neneglijabil. Lăsa $\mathcal{R}$ fie o reducere care are acces la $\mathcal{A}$ și vrea să spargă securitatea PRF a $f$. În ambele jocuri, $b=0$ denotă lumea reală și $b=1$ lumea aleatorie, unde se aplică o funcție cu adevărat aleatorie în loc de $f$ sau $g_k$.
La începutul jocului, $\mathcal{R}$ lucruri $k$ la intamplare. Când $\mathcal{A}$ interogări pentru $x$, $\mathcal{R}$ interogări pentru $x$ și $x\oplus k$, XOR face rezultatul și îl trimite înapoi la $\mathcal{A}$. Când $\mathcal{A}$ își întoarce ipoteza $b'$, $\mathcal{R}$ returnează același bit.
Pentru a demonstra că $\mathcal{R}$ are un avantaj deloc neglijabil, trebuie doar să arătăm că simulează perfect implementarea unui oracol $g_k$. În cazul $b=0$, este cazul, nimic nu face diferență $\mathcal{R}$ dintr-o implementare oracol $g_k$. Dacă $b=1$ in orice caz, $\mathcal{A}$ se asteapta sa obtina $\pi(x)$ pentru o funcție aleatoare $\pi$, în timp ce primește $\pi(x)\oplus\pi(x\oplus k)$. $\pi(x)$ este uniform aleatorie și, prin definiția unei funcții aleatoare, nu are legătură cu $\pi(x\oplus k)$, şi ce dacă $\mathcal{R}$ se intoarce la $\mathcal{A}$ este de asemenea uniform aleatorie. Este de notat că acum că $\pi$ a fost definit pe $x$ și pe $x\oplus k$, $\mathcal{A}$ poate prezice valoarea de criptare a $x\oplus k$ deoarece aceasta ar fi la fel ca $x$lui. De cand $\mathcal{A}$ nu stie $k$, aceasta nu este o strategie posibilă. Prin urmare, $\mathcal{A}$ nu poate face distincția între aceste situații.
Este corecta aceasta dovada? Lucrul care mă deranjează este că acest nou PRF are o mulțime de ciocniri, ceea ce este destul de surprinzător pentru un PRF, dar cred că adversarul nu le poate găsi decât dacă ajunge să cunoască $k$.
