înregistrare Logare
Puncte:1
Awerde avatar Crypto

Arătați că cifrul bloc cu CTR este un PRNG bun

drapel br
Awerde

Să presupunem acea schemă de cifrare în bloc $(KeyGen, Enc, Dec)$ este securizat CPA. Arata asta $CTR_{Enc_k(0^n)}$ este un PRNG bun.

Modul contor funcționează după cum urmează:

$Y_i = Enc_k(IV + f(i))$

$C_i = Y_i \bigoplus P_i = Y_i \bigoplus \{0^k\}= Y_i$

Deci rezultatul de aici este simplu $Enc_k(IV + f(i))$. Acum, la fel de bun PRNG, înțeleg că trebuie să nu fie distins de o sursă aleatorie. Să presupunem că nu este. Astfel, dacă $X_0$ este sursa noastră și $R$ este o sursă cu adevărat aleatorie, avem $$|Pr[A(x)=0|x=X_0]-Pr[A(x)=0|x=R]|=\delta$$ și $\delta$ este deloc neglijabilă. După cum putem distinge ieșirea, blocurile nu sunt independente unele de altele. Deci există niște relații între $Enc_k(IV+f(i))$. Aici nu am nicio idee despre cum să procedez. Bănuiesc că este cumva în contradicție cu securitatea CPA, dar nu știu cum să arăt asta.

91
0 + 0
ctr
Maarten Bodewes avatar
drapel in
Maarten Bodewes
De fapt, dacă ai un bloc de dimensiune mică, mă întreb cât de bun poate fi un PRNG, pentru că nu ai avea posibilitatea ca blocurile să se repete. Cu siguranță nu aș paria același număr câștigător la acea loterie. Dacă rulați un CTR pe un cifr de bloc de 8 octeți, atunci după $2^{32}$ blocuri / 32 GiB de date, atunci unul din $2^{32}$ blocuri nu mai poate fi generat. Nu aș numi asta o proprietate bună pentru un PRNG. Am mai văzut această misiune și personal cred că este destul de stupidă; ei uită totul despre dimensiunile mai mici ale setului de intrare/ieșire al permutării.
0
Răspunde
Awerde avatar
drapel br
Awerde
@MaartenBodewes așa cum ai spus-o, este într-adevăr foarte stupid ;) Cred că pur și simplu uită de asta pentru că nu este principala preocupare aici...
0
Răspunde
Maarten Bodewes avatar
drapel in
Maarten Bodewes
Nu sunt împotriva simplificărilor, dar sunt împotriva sarcinilor sau exemplelor care încearcă să vă învețe ceva, în timp ce, în același timp, vă învață ceva care este *incorect*. Asta încearcă să te lase să înveți cum să alergi în timp ce stai pe marginea unei stânci. Dar destul de spus, presupun.
1
Răspunde
Awerde avatar
drapel br
Awerde
@MaartenBodewes ai spus că ai mai văzut această misiune înainte, poate ai ceva indicii pentru mine?
0
Răspunde
Maarten Bodewes avatar
drapel in
Maarten Bodewes
Nu sunt persoana cea mai potrivită pentru a da indicii aici, eventual, când vine vorba de dovezi formale. Aș include argumentul de securitate pentru modul CTR, dacă este sigur, atunci din cauza XOR fluxul de chei ar trebui să fie complet randomizat. Desigur, puteți încă presupune că este inversul argumentului dvs. și puteți demonstra că este greșit. A apărut o căutare rapidă [această prelegere](https://www.csa.iisc.ac.in/~arpita/Cryptography15/CT2.pdf) cu o dovadă CPA pentru CTR.
0
Răspunde
drapel cn
Maeher
@MaartenBodewes Dacă afirmația este adevărată sau nu, depinde de contextul care nu ne-a fost dat. În contextul definițiilor de securitate asimptotice, afirmația este absolut corectă. În contextul definițiilor de securitate *concrete*, depinde de parametrii exacti.
0
Răspunde
drapel cn
Maeher
Din punct de vedere conceptual, cel mai simplu mod de a înțelege dovada este prin intermediul unei serii de distribuții hibride.Începeți cu distribuția dvs. $X_0$ și aplicați succesiv definiția de securitate a unei permutări pseudoaleatoare, lema de comutare PRP/PRF și observația că pentru o funcție uniform aleatorie $g : \{0,1\}^n \to \{0 ,1\}^n$, $g(0)\Vert\cdots\Vert g(N)$ este distribuit uniform. Acest lucru vă va conduce în cele din urmă la o distribuție $X_3=R$. Pentru fiecare pas de-a lungul drumului puteți demonstra că distribuțiile nu se pot distinge și apoi aplicați inegalitatea triunghiului pentru a obține afirmația dorită.
2
Răspunde
Awerde avatar
drapel br
Awerde
Vă mulțumesc amândoi, nu sunt sigur că acesta este calea pe care ar trebui să o urmez - dovada pare a fi prea complicată pentru acest gen de sarcină, dar mulțumesc oricum ;)
0
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

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.