Studiez singur folosind „Introducere în criptografia modernă (ediția a doua)”
Încerc să înțeleg cum este valabilă soluția la următoarea problemă:
Demonstrați că o schemă care satisface Definiția 2.5 trebuie să aibă $|K| \geq |M|$ fără a folosi lema 2.4. Mai exact, lasă $\Pi$ fie o schemă de criptare arbitrară cu $|K| < |M|$ Arată un $A$ pentru care $Pr[PrivK^{eav}_{A,\Pi} = 1] > \frac{1}{2}$
Unele notații:
Definiția 2.5 este:
Schema de criptare $\Pi = (Gen, Enc, Dec)$ cu spațiu pentru mesaje $M$ este perfect imposibil de distins dacă pentru fiecare $A$ tine asta
$$
Pr[Priv^{eav}_{A,\Pi} = 1] = \frac{1}{2}
$$
Notația spune că probabilitatea ca adversarul să ghicească corect mesajul de intrare trebuie să fie egală cu $\frac{1}{2}$ pentru perfect-indistingubilitatea de a ține.
Totuși, soluția nu are sens pentru mine.
Solutia este:
Având în vedere următoarele $A$: ieșire uniformă $m_0, m_1 \în M$. La primirea textului cifrat $c$, verificați prin (căutare epuizantă) dacă există o cheie $k$ astfel încât $Dec_k(c) = m_0$. Dacă da, ieșire 0; altfel ieșire 1.
Această soluție pare problematică, deoarece spune că este valabil ca adversarul să facă o căutare exhaustivă în spațiul cheie. Dar dacă acesta ar fi fost cazul, pentru orice experiment de indistinguire, am putea avea un adversar care doar efectuează o căutare obositoare în spațiul-cheie pentru a determina la ce decriptează textul cifrat.
Înțelege cineva ce se întâmplă?
