Puncte:2

Enc și Dec trebuie să fie o funcție pseudo-aleatorie pentru ca o schemă să fie sigură CPA?

drapel br

În prezent, trec prin întrebările finale anterioare ca exerciții pentru examenul meu și nu sunt oferite soluții.

Întrebarea pe care o pun în prezent este:

Fie â = (Enc, Dec, Gen) o schemă de criptare securizată CPA. Demonstrați sau infirmați urmatoarele doua afirmatii: a) Enc trebuie să fie o funcție pseudo-aleatorie. b) Dec trebuie să fie o funcție pseudo-aleatorie.

Pentru a), intuitiv știu că trebuie să fie pseudoaleatoare, dar nu sunt sigur cum să procedez pentru a-l dovedi într-un mod formal. Deoarece adversarul are acces la un oracol de criptare, vrem să ne asigurăm că nu poate distinge între diferitele mesaje și că nu află nicio informație utilă despre schemă. Și din moment ce pseudoaleatoriu nu se poate distinge de aleatoriu, atunci este necesar?

Pentru b), nu cred că este adevărat, doar pentru că, pe baza atacurilor CPA, nu implică cu adevărat decriptare, așa că nu are rost să fie o funcție pseudoaleatorie. Cu toate acestea, dacă Enc este pseudoaleatoare, nu ar avea nevoie de o funcție pseudoaleatoare pentru a decripta?

Poate cineva să-mi spună dacă această gândire este pe drumul cel bun, dacă nu, ați putea vă rog să oferiți o explicație?

Mulțumesc.

Morrolan avatar
drapel ng
Intuiția ta pentru a) este destul de corectă. Presupun că ați oficializat securitatea IND-CPA prin intermediul unui „joc” care este jucat de adversar? Dacă da - luați în considerare că funcția de criptare a schemei dvs. a fost complet deterministă, adică $Enc_{k}(m)$ (prin intermediul oracolului de criptare) ar da întotdeauna același rezultat pentru o cheie fixă ​​$k$ și un mesaj $m$. Puteți defini atunci un adversar $A$ care are un avantaj deloc neglijabil în câștigarea jocului?
Morrolan avatar
drapel ng
Pentru b), luați în considerare ce s-ar întâmpla dacă funcția de decriptare a schemei ar fi nedeterministă. Adică, $Dec_k(c)$ nu ar da întotdeauna același rezultat pentru o cheie fixă ​​$k$ și un text cifrat $c$. Ar fi utilă o astfel de schemă? Mai exact, cum ar afecta aceasta de ex. proprietatea de corectitudine a schemei?
paul lacher avatar
drapel br
@Morrolan L-am definit ca P (succes)
paul lacher avatar
drapel br
@Morrolan Ohh, are sens pentru b), mulțumesc!
paul lacher avatar
drapel br
@Morrolan S-ar aplica același lucru și pentru securitatea IND-CCA? Nu sunt sigur, deoarece pentru CCA, adversarul are acces la un oracol de decriptare, ar trebui Dec să fie PRF, dar asta nu are sens, deoarece nu vrem să primim un mesaj mishmashed. Deci, Enc ar mai trebui să facă PRF, deoarece în contextul securității CCA, am văzut-o într-o setare cheie publică și dacă nu există aleatorie, atunci devine deterministă.
Morrolan avatar
drapel ng
"Dacă a fost determinist, atunci [...] există mai mult de 1/2 șansă ca adversarul să distingă diferitele texte clare." Da, cam mult. :) Pentru examen ați putea dori să descrieți cu precizie pașii pe care îi face adversarul $A$, de ex. în ce fel $A$ numește oracolul de criptare și cum folosesc acea ieșire pentru a distinge dacă textul cifrat $c$ pe care l-au primit este o criptare a fie $m_0$, fie $m_1$ pe care l-au furnizat. După ce ați făcut acest lucru, puteți determina cu ușurință șansa exactă pe care o are $A$ de a distinge corect acest lucru.
Morrolan avatar
drapel ng
Pentru securitatea IND-CCA, puteți argumenta exact în același mod ca și pentru IND-CPA.
paul lacher avatar
drapel br
@Morrolan Mulțumesc! Chiar m-a ajutat să clarific lucrurile.
Puncte:1
drapel in

Câteva indicii:

O funcție pseudoaleatoare trebuie să fie a determinat funcția de la cheie și intrare la ieșire. Mai mult, ieșirile ar trebui să „apare aleatoare și independente” atunci când cheia este aleasă aleatoriu (și fixă) și intrările sunt alese de atacator.

Pentru (a): într-o schemă de criptare securizată CPA, Enc poate fi determinist în acest fel? De ce sau de ce nu?

Pentru (b): într-o schemă de criptare securizată CPA cu o schemă aleatorie $sk$, trebuie să ieșirile de $\text{Dec}_{sk}(\cdot)$ apar aleatoriu și independent pe măsură ce atacatorul modifică intrarea? De ce sau de ce nu?

paul lacher avatar
drapel br
ohhh, ok multumesc!

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.