Este posibil ca o cheie diferită să fie decriptată corect?

Mă gândesc la securitatea CPA pentru criptarea simetrică.

Asa de $A$ are acces la un oracol de criptare și poate continua să solicite interogări (faza de antrenament). În această fază de pregătire, întreabă $m_i$ și primește înapoi $y_i$. De asemenea, poate verifica dacă poate găsi o cheie care să decripteze același mesaj pe care l-a criptat, doar verificați dacă $\Pi.\mathsf{Dec}(k, y_i) = m_i$ pentru unii $k$ acea $A$ presupuneri. El poate face același lucru și în timpul fazei de provocare și să vadă dacă $y^*$ a primit înapoi decriptează la oricare dintre $m_0,m_1$.

Acum pot presupune că este greu de găsit $k$ (este ales uniform la întâmplare), dar este posibil să găsiți o altă cheie $k'$ care se întâmplă să funcționeze la unele dintre întrebările de instruire? Bănuiesc că acest lucru nu ar trebui să se întâmple cu o probabilitate mai mare decât neglijabilă dacă $\Pi$ este CPA-secure, dar s-ar putea întâmpla, nu?

Întrebarea mea poate fi similară cu: Este posibil să decriptați un text cifrat cu o cheie privată diferită?

În criptografia simetrică, ceea ce ați descris se poate întâmpla, cel puțin teoretic. Este denumit atacul de recuperare a cheii consistente, spre deosebire de atacul mai comun Target Key Recovery. O recuperare constantă a cheii este atunci când atacatorul găsește o cheie care este în concordanță cu orice pereche de intrare-ieșire. O recuperare a cheii țintă este atunci când atacatorul găsește cheia reală (care va fi în concordanță cu toate perechile de intrare-ieșire). Dacă un atacator efectuează un atac Exhaustive Key Search, este probabil să întâlnească cheia consecventă (care va funcționa la una sau câteva interogări) înainte de a întâlni cheia reală (care va funcționa pentru toate interogările).

S-a pus problema cât de departe este diferența dintre avantajul de a găsi cheia consecventă și avantajul de a găsi cheia țintă. Am găsit o prelegere a lui Bellare care vorbește despre această problemă (dar nimic în format scris). În acea prelegere, Bellare menționează că decalajul aproape nu este prezent (adică aproape același avantaj) dacă cifrul bloc este un cifr bloc real (cum ar fi AES). El a spus că o astfel de concluzie se bazează pe dovezi euristice sau empirice. Dacă avantajele sunt aproape aceleași, înseamnă că cheia țintă este SINGURA cheie care este în concordanță cu interogările de intrare-ieșire. Dar, în teorie, o cheie consistentă (diferită de cheia țintă) este posibilă și poate fi recuperată cu mult înainte ca o cheie țintă să fie recuperată. Puteți urmări întregul lectura pentru că sunt sigur că Bellare o poate explica MULT mai bine decât pot eu.