Un primitiv criptografic $Q$ este mai puternică decât o altă primitivă criptografică $P$ dacă $Q$ implică $P$ dar invers nu este adevărat. Pentru concret, gândiți-vă $P$ ca funcţii unidirecţionale şi $Q$ ca criptare cu cheie publică.
Modul convențional de a arăta asta $Q$ implică $P$ este prin a reducerea cutie neagră de $P$ la $Q$: adica,
- mai întâi arată un eficient constructie $C^{(\cdot)}$ asta, având acces la cutia neagră la fiecare instanță (nu neapărat eficient) $\mathsf{Q}$ de $Q$, dă o instanță $\mathsf{P}=C^{\mathsf{Q}}$ de $P$; și
- apoi arata o eficienta reducerea securității $\mathsf{R}^{(\cdot)}$ asta, având acces la cutia neagră pentru fiecare adversar (nu neapărat eficient) $\mathsf{A}_P$ care se rupe $\mathsf{P}$, dă un adversar $\mathsf{A}_Q$ care se rupe $\mathsf{Q}$.
Pentru a vedea că o criptare cu cheie publică $(\mathsf{G},\mathsf{E},\mathsf{D})$ implică funcții unidirecționale, (de exemplu) setați algoritmul de generare a cheilor ca funcție unidirecțională, adică $\mathsf{F}(1^n,r):=pk$, Unde $(pk,sk):=\mathsf{G}(1^n;r)$.
Pe de altă parte, pentru a arăta că $P$ nu implică $Q$ trebuie exclus toate reduceri de $Q$ la $P$, adică arată a separare. De exemplu, pentru a arăta asta $P$ nu implică $Q$ prin reduceri de cutie neagră, este suficient să descriem un oracol $\mathcal{O}$ astfel încât primitivul $P$ există relativ la $\mathcal{O}$, dar toate cazuri de $Q$ sunt stricate. Din moment ce reducerile de cutie neagră relativiza, astfel de reduceri nu pot exista. S-a arătat în [IR] că funcțiile unidirecționale nu implică criptarea cheii publice prin reduceri de cutie neagră (acest lucru este foarte netrivial).
Puteți citi mai multe despre diferitele arome de reduceri și separări în [RTV].
[IR]: Impagliazzo și Rudich, Limitele consecințelor dovedibile ale permutărilor unidirecționale, STOC'89.
[RTV]: Reingold, Trevisan și Vadhan, Noțiuni de reducere între primitivele criptografice, TCC'04.
