În general, dacă întrebați despre o anumită definiție, este bine să includeți un link către definiția în cauză.
În general însă, se știe că PKE cere criptare aleatorie (sau non-uri nerepetate, voi ignora acest lucru).
Aceasta înseamnă că (cu excepția setărilor de specialitate) funcția:
$$\mathsf{Enc} : \mathcal{PK}\times\mathcal{M}\to\mathcal{C}$$
este o randomizat algoritm (unde $\mathcal{PK}$ este spațiul tuturor cheilor publice).
Puteți oricând [1] să scrieți un algoritm randomizat ca a determinat algoritm care ia ca intrare un șir aleator, adică scrie:
$$\mathsf{Enc}^{det} : \mathcal{PK}\times\mathcal{M}\times\mathcal{R}\to\mathcal{C}$$
Unde $\mathsf{Enc}^{det}(pk, m;r)$ simulează algoritmul $\mathsf{Enc}(pk,m)$, iar când algoritmul solicită biți aleatori, folosește șirul (fix). $r$ ca sursă a biților „aleatorii”.
Acest lucru este relevant pentru transformarea FO, deoarece poate fi „factorizat” în doi pași ( $T$-transforma si $U$-transforma, vezi această hârtie).
The $T$-transforma se modifică $\mathsf{Enc}$ în două moduri:
Derandomizare: În loc să folosiți aleatoriu $r$, se folosește un oracol aleatoriu $G$ a seta $r := G(m)$, adică alege $\mathsf{Enc}^{det}(pk,m) := \mathsf{Enc}(pk,m; G(m))$
Re-criptare: Se modifică și decriptarea, și anume se verifică asta pentru $m'\gets\mathsf{Dec}(sk, c)$ relatia $c = \mathsf{Enc}^{det}(pk, m')$ tine. Pentru ca această verificare să aibă sens, criptarea trebuie (desigur) să fie deterministă.
Oricum, pentru a putea face primul pas al $T$-transforma, trebuie sa stii $\mathcal{R}$, deoarece trebuie să puteți alege un oracol aleatoriu $G : \mathcal{M}\to\mathcal{R}$. De obicei $\mathcal{R}$ poate fi scris de forma $\{0,1\}^k$ pentru unii $k$ [2].
[1] Ar putea exista unele patologii aici dacă algoritmul randomizat are un timp de rulare „așteptat polinomial”, mai degrabă decât să se încheie într-un timp de rulare polinomial.Voi ignora acest lucru, nu este relevant pentru criptare.
[2] Rețineți că există scheme pentru care s-ar putea să vă faceți griji $\mathcal{R} \neq \{0,1\}^k$, sau chiar $\mathcal{R} = \{0,1\}^k$ dar distribuţia zgomotului care $\mathsf{Enc}$ nevoile nu este uniformă peste $\{0,1\}^k$. Mă gândesc în special la schemele bazate pe zăbrele, în care aleatorietatea este adesea „ca Gaussian” (sau să zicem binom centrat), deși acest lucru se întâmplă și pentru schemele bazate pe cod, unde deseori aleatorietatea a fixat greutatea hamming iirc. Un oracol aleatoriu va avea de obicei rezultate $G(m)$ care este uniform aleatoriu $\{0,1\}$. Totuși, aceasta nu este o problemă reală --- se poate folosi un algoritm de eșantionare $\mathsf{Eșantion} : \{0,1\}^k \la \mathcal{R}$ pentru a converti rezultatul oracolului aleatoriu în distribuția dorită. Acest lucru se întâmplă chiar și pentru criptarea aleatorie, unde, în loc să folosească un RO pentru aleatorie, algoritmul folosește o anumită formă de aleatorie a sistemului (care se presupune că nu poate fi distinsă din punct de vedere computațional de biții aleatori uniformi).
