Da ai dreptate.
O definiție oficială a IND-CPA lipsește într-adevăr din întrebarea mea. Aici, folosesc în mod informal termenul „IND-CPA” pentru a mă referi la proprietatea conform căreia o schemă de criptare poate duce la texte cifrate pseudoaleatoare în $\mathcal{C}_1$
Aceasta este, desigur, o presupunere mai puternică decât a fi IND-CPA, dar este plictisitor să subliniez acest lucru.
Într-adevăr, această presupunere poate fi scrisă ca
$\mathsf{Enc}_k$ este o familie PRF.
Este poate mai simplu să ne gândim la acest lucru în termeni de PRF, așa că voi arăta rapid că dacă $F_k, G_k$ sunt (individual) PRF-uri, atunci $(F_k, G_k)$ nu trebuie să fie, de ex. partajarea cheilor PRF poate distruge securitatea.
Acest lucru se datorează dependenței dintre componentele din stânga și din dreapta, după cum ați ghicit.
Lăsa $F_k$ fi un PRF, și lasă $G_k = F_k^{\circ 2}$, adică $G_k(x) = F_k(F_k(x))$.
Este simplu să vezi asta $G_k$ este (individual) un PRF --- orice deosebitor pentru ea implică un deosebitor pentru $F_k$, deoarece puteți emula eficient accesul la interogări $G_k$ dat acces la interogare $F_k$.
Acum, $(F_k, F_k^{\circ 2})$ nu este un PRF.
Acest lucru se datorează faptului că, dat un oracol $\mathcal{O}(\cdot)$ care este fie real, fie aleatoriu, poți.
- $(y_1, y_2)\obține \mathcal{O}(x)$,
- $(z_1, z_2) \obține \mathcal{O}(y_1)$,
- ghici REAL dacă $y_2 = z_1$, iar RANDOM în caz contrar.
DACĂ $\mathcal{O}(x) = (F_k(x), F_k^{\circ 2}(x))$ este PRF-ul tău, atunci $y_2 = F_k^{\circ 2}(x)$, și $z_1 = F_k(y_1)= F_k(F_k(x)) = F_k^{\circ 2}(x)$ se ciocnesc.
În jocul aleatoriu, probabilitatea ca oricare două valori să se ciocnească este destul de mică, așa că acest lucru implică imediat un deosebitor destul de bun.
Există însă probleme mai imediate.
O modalitate de a construi $\mathsf{Enc}_k(m)$ este prin XORing $m$ cu un PRF, de exemplu $\mathsf{Enc}_k(m) = (r, F_k(r)\oplus m)$.
Acesta este pur și simplu un mod de contor randomizat (unde mesajele sunt un singur bloc).
În acest cadru, construcția îmbinării este $(m_1,m_2)\mapsto (r, F_k(r)\oplus m_1, F_k(m_2))$.
Din nou, interogând $(m_1, m_2)$, iar apoi interogarea $(m_3, r)$, se poate obține un distinctor eficient.
Adică o construcție naturală (unde $\mathsf{Enc}$ este modul de contor randomizat) nu este sigur și în setarea dvs.
