Amintiți-vă că adversarul din jocul de securitate IND-CPA primește un „oracol stânga-dreapta”:
$$\mathsf{LR}(m_0,m_1) := \mathsf{Enc}_{pk}(m_b)$$
Unde $b\în\{0,1\}$ este un secret pe care adversarul trebuie să încerce să-l recupereze.
să presupunem că există un adversar care poate descoperi că cele două texte cifrate sunt criptate din același text simplu.
În cele de mai sus, puteți vedea că există doar unu text cifrat totuși --- $\mathsf{LR}(m_0,m_1)$ returnează singur text cifrat $\mathsf{Enc}_{pk}(m_b)$. Aceasta înseamnă că nu sunt 100% sigur de ceea ce intenționați să întrebați. Dacă vă modificăm întrebarea la:
Să presupunem că există un adversar $\mathcal{A}$ care, având în vedere două texte cifrate arbitrare $c, c'$ criptate sub aceeași cheie publică, pot determina dacă criptează același lucru --- adică poate răspunde la întrebare
$$\mathsf{Dec}_{sk}(c)\stackrel{?}{=}\mathsf{Dec}_{sk}(c')$$
Poate acest adversar să rupă securitatea IND-CPA?
Raspunsul este da.
Atacul este simplu --- pentru distinct $m_0, m_1, m_2$, interogare $c\obține \mathsf{LR}(m_0, m_1)$, $c'\obține \mathsf{LR}(m_2, m_1)$. Dacă adversarul stabileşte că $c, c'$ criptați același mesaj, apoi ambele $\mathsf{LR}$ interogări criptate $m_1$, de exemplu. $b = 1$. In caz contrar, $b = 0$.
Acesta este de fapt fundamentul unui rezultat destul de fundamental în criptarea cu chei publice.
Criptarea deterministă a cheii publice este imposibilă.
Cred că citarea pentru aceasta este Goldwasser-Micali 1982, dar indiferent de detalii, este unul dintre rezultatele „primare” în criptografia teoretică.
Pentru a demonstra acest lucru, tot ce trebuie să faceți este să observați că dacă $\mathsf{LR}$ este determinist, construind adversarul $\mathcal{A}$ am menționat mai înainte este destul de simplu (vă las să vă gândiți cum).
Apoi putem lansa atacul pe care l-am menționat anterior.
