Făceam următorul exercițiu din Introducerea criptografiei moderne de la Katz și Lindell:
Lăsa $F$ să fie o funcție pseudoaleatoare care păstrează lungimea. Pentru următoarele construcții ale unei funcții cu taste $F' : \{0,1\}^n \times \{0,1\}^{n-1} \rightarrow \{0,1\}^{2n}$, precizați dacă $F'$ este o funcție pseudoaleatoare. Dacă da, dovediți-o; dacă nu, arată un atac.
(d) $F'_k(x) \stackrel{def}{=} F_k(0||x) || F_k(x||1)$
Înțeleg că în acest caz $F'_k$ nu este o funcție pseudoaleatoare, deoarece am putea, eficient și cu o probabilitate deloc neglijabilă, să distingem $F'$ dintr-o funcție aleatorie prin interogare $x = 0^{n-2}||1$ și $x = 0^{n-1}$, și verificând dacă este cel mai din stânga $n$ biți din prima interogare este egal cu cea din dreapta $n$ biți din a doua interogare.
Totuși, mi-aș putea presupune și un adversar $A$ care distinge $F'$ dintr-o funcție aleatorie și folosiți-o ca subrutină pentru a ataca $F$. Pentru orice întrebare $x$ din $A$, întreb pentru $0 ||x$ și $x||1$, concatenează rezultatele și dă-le înapoi la $A$. Tot ceea ce $A$ răspunsuri, acesta ar fi răspunsul meu.
Din păcate, nu pot justifica de ce dovada este greșită. Poate pentru că există o probabilitate scăzută să pot folosi rezultatul din $A$ a sparge $F$? Dar cum oficializez asta dacă nu știu nimic despre asta $A$?
