Aș dori să întreb de ce o permutare corectă nu este într-un singur sens.
Dacă este o singură cale, depinde de modul în care definiți problema.
Dacă vi se oferă acces Oracle la permutarea unică, adică vi se permite să furnizați un număr de interogări $x$ iar Oracle vă oferă evaluarea $F(x)$, ei bine, sperăm ca (presupunând că dimensiunea este mare) să fie unidirecțională. La urma urmei, dacă definim $F$ să fie criptarea blocului AES bazată pe o cheie secretă (deci $n = 2^{128}$), ei bine, această paradigmă Oracle este exact un atac CPA standard și sperăm că AES este în siguranță împotriva acestuia. Și, într-adevăr, se poate dovedi oficial că probabilitatea de succes pe care ați dat-o pentru o permutare aleatorie este apropiată (probabilitatea reală a limitei superioare este puțin mai mare, deoarece atacatorul poate ghici o intrare pe care nu a furnizat-o Oracolului, crescând puțin probabilitatea de succes. ).
Pe de altă parte, dacă vi se oferă descrierea lui $F$, devine mai problematic. Cel mai simplu (și cel mai comun) mod de a genera o permutare puternică este să luați o serie de permutări slabe (runde) și să le concatenați împreună; aceasta este abordarea pe care o folosește Keccak (SHA-3). Acest lucru funcționează, dar este ușor de inversat (doar să calculăm inversul permutărilor slabe în ordinea opusă).
Pe de altă parte, aceasta nu este singura modalitate de a defini o permutare; un exemplu de mod diferit este definirea permutației $F(x) = x^e \bmod n$ pentru un modul RSA $n$ și un exponent public $e$. Aceasta este o permutare a $x \in [0 ... n-1]$, si daca $n, e$ sunt bine alese, este greu de inversat chiar și având în vedere valorile $n, e$ (sau așa sperăm; altfel RSA este nesigură)
