Puncte:2

Katz/Lindell 2.4 - Generalizarea de la 2 mesaje în orice spațiu de mesaje?

drapel fr

Încerc să rezolv problema 2.4 din „Introduction to Modern Criptography” (ediția a 2-a) pentru auto-studiu.

Problema cere să se dovedească acel secret perfect $$ Pr[M = m | C = c] = Pr[M = m] $$

implică

$$ Pr[Enc_k(m) = c] = Pr[Enc_k(m') = c] $$

Soluția merge după cum urmează:

Remediați două mesaje $m, m'$ și un text cifrat $c$ care are loc cu probabilitate diferită de zero și luați în considerare distribuția uniformă peste $\{m, m'\}$. Secretul perfect implică asta $Pr[M = m | C = c] = \frac{1}{2} = Pr[M = m' | C = c]$ Asa de

$$ \frac{1}{2} = Pr[M = m| C = c] = \frac{Pr[C = c| M = m] * Pr[M = m]}{Pr[C = c]} $$

simplifică la

$$ \frac{\frac{1}{2}Pr[C = c | M = m]}{Pr[C = c]} $$

Așadar $Pr[C = c | M = m]$ = $Pr[Enc_k(m) = c]$ = $Pr[C = c]$. Deoarece un calcul analog este valabil pentru $m'$ de asemenea, tragem concluzia că $Pr[Enc_k(m) = c]$ = $Pr[Enc_k(m') = c]$

Problema mea este că această soluție presupune un spațiu de mesaje de 2, care nu este generalizabil.

Există ceva care îmi lipsește care face ca această soluție să fie generalizată?

Editați | ×: Pentru a fi clar, iată textul complet al problemei.

Lema 2.4: O schemă de criptare (Gen, Enc, Dec) cu spațiu pentru mesaje $M$ este perfect secret dacă și numai dacă Ecuația (2.1) este valabilă pentru fiecare $m,m' \în M$ si fiecare $c \în C$. Unde ecuația 2.1 este a doua egalitate din această postare.

Problema cere să se demonstreze „altă direcție”, ceea ce înseamnă în acest caz demonstrarea secretului perfect => ecuația 2.1. (În manual, sensul invers este deja dovedit).

Myath avatar
drapel in
Ce vrei sa spui "solutia"? Cartea oferă soluția respectivă?
Foobar avatar
drapel fr
Da, cartea da.
kelalaka avatar
drapel in
Nu, cartea nu are o soluție. Există o soluție pe care o puteți cumpăra separat. După cum vedeți rezultatul, nu există $1/2$, așa că ați putea ghici că se va anula. Pentru a lucra cu un spațiu mai mare pentru mesaje, va fi nevoie de $1/n$, jucați în acest fel?
Puncte:3
drapel ru

Aceasta nu este o afirmație despre un „spațiu de mesaje de dimensiunea 2”. Spațiul de mesaje poate fi atât de mare pe cât doriți, iar a doua caracterizare spune pur și simplu asta, pentru fiecare $m,m'$ alegeți din acest spațiu de mesaje și pentru fiecare text cifrat posibil $c$, probabilitatea ca $m$ este criptat ca $c$ este aceeași cu cea a $m'$ fiind criptat ca $c$, care este scris ca $\Pr[\mathsf{Enc}_k(m) = c] = \Pr[\mathsf{Enc}_k(m') = c]$.

Acum, în ceea ce privește schița soluției pe care o oferiți, nu este chiar adevărat că „presupune” un spațiu de mesaje de dimensiunea doi. Doriți să dovediți o afirmație despre două mesaje fixe $m$ și $m'$ (și anume, vrei să demonstrezi asta $\Pr[\mathsf{Enc}_k(m) = c] = \Pr[\mathsf{Enc}_k(m') = c]$), și doriți să faceți acest lucru în timp ce utilizați secretul perfect, care prevede asta, pentru fiecare mesaj $\mu$ și fiecare text cifrat $\gamma$,$^*$ si foarte important, pentru fiecare distributie $M$ peste spațiul de mesaje, asta tine $\Pr[M=\mu|C=\gamma] = \Pr[M=\mu]$.

Având în vedere că secretul perfect este valabil pentru orice distribuție, putem alege în mod arbitrar orice distribuție care ne ajută să ne dovedim afirmația. Soluția pe care o propuneți ia pur și simplu distribuția de probabilitate pe care o eșantionează $m$ cu probabilitate $1/2$, $m'$ tot cu probabilitate $1/2$, iar toate celelalte mesaje sunt eșantionate cu probabilitate $0$. Se poate spune, de asemenea, că spațiul de mesaje este „restrâns” la $\{m,m'\}$, dar ceea ce se întâmplă de fapt este ceea ce am spus chiar înainte. Acum că am fixat distribuția probabilității, o reparăm și $\mu = m$ și $\gamma = c$ mai întâi, aplicați secretul perfect, apoi remediați $\mu = m'$ și aplicați din nou secretul perfect, pentru a obține diferite expresii care pot fi manipulate pentru a obține ceea ce ne trebuie.

Pe scurt, acesta este doar un artefact al dovezii, deoarece afirmația pe care doriți să o demonstrați se referă doar la o pereche fixă ​​de mesaje $m,m'$, deci tu poate sa restrângeți o distribuție de probabilitate doar la aceste două elemente și aplicați secretul perfect acestei distribuții.


$^*$ Observați că folosesc alte nume în loc de $m$ și $c$, deoarece acestea din urmă sunt fixate deja în contextul nostru.

Daniel avatar
drapel ru
@kelalaka Cu excepția cazului în care îmi lipsește ceva, aceasta nu este o presupunere în sine, ci mai degrabă o alegere pe care *poți* să o faci în dovezi pentru ca aceasta să funcționeze. Nu este o presupunere în sensul că nu este că nu funcționează pentru setări mai „generale” sau așa ceva. Revendicarea în sine tratează o pereche fixă ​​de mesaje $m,m'$. Dacă se dorește ceva mai general, atunci ar trebui să se uite mai degrabă la modificarea caracterizării decât la demonstrarea acesteia.
Daniel avatar
drapel ru
@kelalaka Nu sunt sigur că vorbim despre același lucru aici.Ai dreptate că securitatea perfectă nu se limitează la uniformă, deoarece se aplică pentru *orice* distribuție (cum am menționat deja în răspunsul meu), dar caracterizarea care este dovedită aici vorbește despre *orice pereche fixă ​​de mesaje $m,m '$. Pentru a demonstra că această caracterizare este echivalentă cu securitatea perfectă, se consideră că spațiul mesajului este $\{m,m'\}$ și se aplică atunci securitatea perfectă, dar aceasta nu este o simplificare, nici o presupunere, aceasta este doar o parte din dovada.
Daniel avatar
drapel ru
@kelalaka Acestea fiind spuse, pentru a aborda în mod concret ceea ce ați spus: Caracterizarea propusă vorbește despre **perechi** $m,m'$, așa că este firesc să luăm în considerare o dovadă în care se aplică securitatea perfectă spațiului mesajului $\{ m,m'\}$. Insist că aceasta nu este o simplificare, aceasta este *modul* de a proceda cu demonstrația. Dacă se dorește o „generalizare”, atunci trebuie să găsească o altă caracterizare de demonstrat, cum ar fi: „pentru fiecare $c$ valoarea lui $\Pr[\mathsf{Enc}_k(m) = c]$ este constantă, indiferent de $ m$".
kelalaka avatar
drapel in
Sunt mai educativ. Răspunsul cărții simplificat ca „luați în considerare distribuția uniformă pe {m1,m2}”, acesta a fost punctul meu de vedere. Între primul și al doilea paragraf al răspunsului dvs., lipsește dovada distribuției uniforme a spațiului mai mare de mesaje! După aceea, este bine să vorbim despre distribuția arbitrară.
Daniel avatar
drapel ru
@kelalaka Acest „luați în considerare distribuția uniformă pe $\{m,m'\}$” **nu** este o simplificare, este **modul** de a continua cu demonstrația. Cred că sugerezi că acesta este doar „cazul de bază” în scopuri ilustrative și că lipsește cazul general, dar insist că acesta este pur și simplu *nu* cazul. Afirmația este despre o pereche (fixă) de mesaje $m,m'$, acestea sunt deja remediate odată ce intri în demonstrație și poți alege ORICE distribuție pe spațiul potențial mult mai mare pentru a demonstra că $\Pr [\mathsf{Enc}_k(m) = c] = \Pr[\mathsf{Enc}_k(m') = c]$....
Daniel avatar
drapel ru
@kelalaka...alegeți distribuția care atribuie $1/2$ la $m$ și $1/2$ la $m'$ și $0$ tuturor celorlalte mesaje, care pot fi exprimate ca distribuție uniformă peste $\{m,m '\}$ și apoi aplicați secretul perfect acestei distribuții, pentru a obține ceea ce doriți. Dovada este completă 100% în acest moment, nu trebuie abordate cazuri generale.
Foobar avatar
drapel fr
@Daniel Mulțumesc pentru explicația detaliată! Am adăugat textul complet al problemei pentru a clarifica lucrurile. Se spune că ecuația trebuie să fie valabilă pentru fiecare $m, m' \în M$ (nu sunt sigur dacă asta schimbă ceva)
Foobar avatar
drapel fr
@Daniel am adăugat și eu în soluția completă
Daniel avatar
drapel ru
@Roymunson Exercițiul vă cere să demonstrați că, presupunând secretul perfect (care vorbește despre distribuții arbitrare pe întreg spațiul de mesaje), rezultă că, **pentru fiecare pereche** $m,m'$ și pentru fiecare text cifrat $c$ , $\Pr[\mathsf{Enc}_k(m) = c] = \Pr[\mathsf{Enc}_k(m') = c]$. Pentru a demonstra o astfel de afirmație, începeți prin a fixa $m,m'$ și $c$, deci pentru restul dovezii, aceste valori sunt doar constante și puteți aplica secretul perfect cu *orice* distribuție la alegere, în special, dvs. poate folosi cea care atribuie $1/2$ atât pentru $m$ cât și pentru $m'$ și zero tuturor celorlalte mesaje.
Foobar avatar
drapel fr
@Daniel Nu este implicit că $M$ ar putea fi orice distribuție?
Daniel avatar
drapel ru
@Roymunson Confuzia de aici vine într-adevăr din matematică și dovezi, nu din criptografie.Aveți două definiții: o schemă este perfect sigură dacă, pentru fiecare distribuție $M$ pe spațiul de mesaje $\mathcal{M}$, pentru fiecare mesaj $m$ și fiecare text cifrat $c$, se consideră că $\Pr[ M = m | C = c] = \Pr[M = m]$. Pe de altă parte, să dăm un nume celei de-a doua noțiuni, să presupunem că o schemă este „variantă” perfect sigură dacă, pentru fiecare pereche de mesaje $m$ și $m'$, și fiecare text cifrat $c$, susține că $\Pr[\mathsf{Enc}_k(m) = c] = \Pr[\mathsf{Enc}_k(m') = c]$....
Daniel avatar
drapel ru
@Roymunson ... Rețineți că această a doua definiție a securității perfecte „variante” *nu* vorbește deloc despre distribuțiile în spațiul de mesaje, în timp ce prima definiție o face. Aceste două noțiuni sunt echivalente, chiar dacă, încă o dată, una necesită ca anumite proprietăți să fie valabile pentru *orice* distribuție posibilă, în timp ce cealaltă nu vorbește deloc despre distribuții.

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.