Puncte:2

Ce este în neregulă cu Middle Square PRNG?

drapel tf
Tom

Conform articolului:

https://www.pcg-random.org/posts/too-big-to-fail.html

Când N de Piața Mijloc este $2^{128}$ ne putem aștepta să producem $2^{64.3}$ numere înainte de a începe să vedem repetări în generator. Este suficient pentru 320 de exaocteți de date aleatorii, cu mult mai mult decât va consuma vreodată orice test PractRand.

Aceasta este dimensiunea suficientă a căii pentru a ajunge la ciclu și ciclul în sine. Trece testele de aleatorie și probabil este destul de rapid. Deci este ceva în neregulă cu Piața Mijloc suficient de mare? Mai ales dacă nu ne-am plânge de viteza și cerințele de matematică pe 256 de biți.

Mellisa O'Neil a scris că, dacă un generator este o mapare aleatorie, va exista un anumit risc de stări proaste și cicluri scurte. Dar care este această probabilitate în acest caz? Pare foarte mic, oricum nu pot dovedi.

fgrieu avatar
drapel ng
Calitatea pătratului din mijloc PRNG cu starea $n$ de biți va depinde foarte mult de modul în care este definită ieșirea sa în funcție de starea sa și, într-o măsură mai mică, de modul în care este inițializată de la cheia sa.Te-ai hotărât cu asta? Independent; mărimea ciclului așteptată de $2^{64.3}$ pare a fi derivată prin _presupunând_ că funcția repetată se comportă ca o funcție aleatorie pseudo-aleatorie de la și către setul de șiruri de biți de 128 de biți; astfel, a trage concluzii despre calitatea pătratului din mijloc PRNG din acel număr este în mare măsură un argument circular. De gândit: câte antecedente de zero?
Tom avatar
drapel tf
Tom
@fgrieu, dar acest argument circular este oarecum prezent în cazul fiecărui generator PRNG. Desigur, la majoritatea generatoarelor cunoaștem perioada, dar nu putem avea dovezi că se vor comporta bine cu mulți terabytes de date. Trebuie să credem în comportamentul bun. Și noi credem. La fel, dacă dovedim un comportament bun al Middle Square pentru primii terabytes de date, nu există motive întemeiate să ne temem că va eșua cu o cantitate mai mare de date și ar avea o perioadă scurtă. Deoarece legitimăm calitatea altor generatori prin credință pentru cantități mari de date, de ce să nu o facem pentru lungimea ciclului Middle Square.
drapel cn
@Tom Este afirmația ta că acest tip de „argument circular” se aplică „fiecărui generator de PRNG” bazată pe înțelegerea matematicii sau pe propria părere personală despre ceea ce s-ar putea întâmpla? Sigur, există *câteva* generatoare PNRG teribile, dar „unii” nu este același lucru cu „toți”.
Puncte:6
drapel ru

Declarația „ne așteptăm să producem $2^{64.3}$ numere înainte de a începe să repetăm" este adevărată numai dacă credem că pătratul mijlociu pe 128 de biți se comportă ca o mapare aleatorie pe $\{0,1\}^{128}$. Cu toate acestea, putem arăta că are proprietăți care sunt foarte puțin probabile pentru o mapare aleatorie.

Amintiți-vă că Middle Square de 128 de biți menține o stare de 128 de biți $S_t$. Actualizările se fac efectiv prin pătrat $S_t$, și luând biții 64-191 ca noi $S_{t+1}$ adică $$S_{t+1}=(S_t^2>>64)\%2^{128}.$$

Statul $S_t=0$ reprezintă un punct fix. Deși mapările aleatoare au puncte fixe cu probabilitate aproximativ $(1-1/e)$, aceasta este una neobișnuită, deoarece are un număr mare de preimagini. Orice număr $S<2^{32}$ se va mapa la 0 la fel ca orice număr $S$ divizibil cu $2^{96}$. Numai aceste preimagini (pot fi altele) total $2^{33}$ când pentru o hartă mare aleatorie ne așteptăm ca numărul de preimagini să fie distribuit Poisson(1). Mai mult, dacă ne gândim la predecesori, orice număr $S<2^{64}$ se va mapa la un număr mai mic și un număr mai mic decât $2^{63}$ va ajunge la 0 în mai puțin de 6 pași. La fel pentru numerele divizibile cu $2^{65}$. Asta dă cel puțin $2^{64}$ predecesorul afirmă pentru 0 când s-ar aștepta o hartă aleatorie $2^{64}\sqrt{\pi/8}$ (cu timpul de coalescență aproximativ același). Numărul de stări predecesoare crește și mai mult atunci când luăm în considerare posibilii predecesori ai garanției noastre $2^{64}$ statele predecesoare, dacă acestea au fiecare $2^{64}\sqrt{\pi/8}$ predecesori am putea vedea o proporție pozitivă a spațiului nostru degenerând la starea 0.

Există, de asemenea, un subspațiu păstrat al numărului exact divizibil cu $2^{64}$ (acest spatiu este de dimensiuni $2^{63}$) pe care ne-am putea aștepta să prezinte statistici de cartografiere aleatoare pentru spațiul mai mic (de ex.o lungime de ciclu de $2^{31,5}\sqrt{\pi/8}$). Apoi luăm în considerare predecesorii acestui subspațiu și producem așteptări semnificativ diferite de o mapare aleatorie completă.

Toate în toate aceste structuri sunt foarte atipice pentru o mapare aleatorie și ar trebui să concluzionăm că maparea aleatoare nu este un model bun în acest caz.

Tom avatar
drapel tf
Tom
Ok, majoritatea îndoielilor mele au fost legate de - dacă aceasta este atât de aproape de cartografierea aleatorie, ce este în neregulă. Acum înțeleg mai bine că avem abateri de la maparea aleatoare și, chiar dacă a funcționat ca o mapare aleatoare, mai avem aici un fel de argument circular.
fgrieu avatar
drapel ng
Încă din [ENIAC](https://en.wikipedia.org/wiki/ENIAC), se știa că proprietățile metodei pătratului mijlociu a lui Von Neumann analizate în acest răspuns conduc la cicluri scurte atunci când sunt iterate. Volumul 2 al lui Knuth TAOCP afirmă: „secvența tinde să intre într-o rut, un ciclu scurt de elemente care se repetă. (â¦) Teste mai ample au fost efectuate de N. Metropolis, mai ales în sistemul numeric binar. El a arătat că atunci când Sunt utilizate numere de 20 de biți, există 13 cicluri diferite în care secvența pătratului mijlociu ar putea degenera, cel mai lung dintre acestea având o perioadă de lungime de 142"_.
Puncte:4
drapel ng

Citind pagina legată de întrebare: recunoaște că metoda de bază a pătratului mijlociu duce la cicluri scurte, explică de ce (la fel și aceasta alt raspuns), și propune în schimb o variație „Meddle square”, care repetă $x\mapsto g(x):=2^n-1-\left\lfloor x^2/2^{\left\lfloor n/2\right\rfloor}\right\rfloor\bmod 2^n$ în loc de $x\mapsto f(x):=\left\lfloor x^2/2^{\left\lfloor n/2\right\rfloor}\right\rfloor\bmod 2^n$.

Această variație elimină orice punct fix evident și, mai important, orice clasă mare evidentă de puncte care urmează să cadă rapid într-un ciclu scurt. Aceasta este o îmbunătățire. In orice caz:

  • Dacă scoatem starea completă a generatorului la fiecare pas, acesta este destul de eficient (pentru implementare competentă pe o mașină cu multiplicator rapid), dar trivial previzibil din ieșirea trecută, deci nesigur din punct de vedere criptografic. Mi se pare foarte credibilă afirmația articolului că (pentru $n=128$) Pătratul Meddle trece toate testele statistice standard. Aceasta este o ilustrare a faptului că testele statistice standard pe rezultatul unui PRNG sunt inutile atunci când vine vorba de argumentul că este un CSPRNG. Și într-adevăr, articolul pare să introducă pătratul Meddle tocmai pentru a ilustra faptul că a avea o stare mare fără punct fix evident sau ciclu de absorbție și trecerea testelor nu este un criteriu de securitate valid pentru un CSPRNG.
  • Dacă scoatem un singur bit, pătratul mijlociu și variații este $n$ de ori mai puțin eficient și încă nu avem un argument solid că este un CSPRNG. Adevărul este că putem crea cu ușurință un PRNG care iterează o funcție, schimbându-i starea mare, care scoate un singur bit din acea stare la fiecare pas, trece toate testele standard, dar în cele din urmă își scurge starea completă și, prin urmare, sunt nesigure din punct de vedere criptografic.
  • Ne-am putea mulțumi cu o cale de mijloc, cum ar fi o stare de 256 de biți din care sunt scoși 64 de biți la fiecare etapă. Acest lucru poate recâștiga multă eficiență, dar fără a încerca, nu am nicio certitudine cu privire la modul în care se compară debitul cu, de ex. Chacha; și aș spune că este mult mai greu să obțineți o implementare eficientă corectă.
  • Ca orice generator bazat pe repetarea unei funcții pseudoaleatoare, este imposibil să înaintezi rapid generatorul, ceea ce îl face nepotrivit pentru multe aplicații (cum ar fi un cifr de flux pentru o cantitate mare de date care acceptă accesul de citire aleatoriu*).

Pentru a rezuma: PRNG-ul Middle Square și chiar și varianta sa îmbunătățită Meddle Square sunt greșite deoarece:

  1. Le lipsește un argument solid de securitate, indiferent de variantă. Ar trebui să fie suficient.
  2. Ei sunt trivial nesiguri atunci când scoatem starea lor completă la fiecare pas.
  3. Când scoatem mai puțin din starea lor, ei devin mai puțin eficienți.
  4. Nu există acces direct* la fluxul generat, o proprietate utilă a multor CSPRNG-uri.

* Adică, capacitatea de a calcula eficient $j^\text{th}$ puterea generatorului pentru mari $j$, cu efort în esență independent de cât de mare $j$ este. Acest lucru este la îndemână când $j$ este un index dintr-un film uriaș criptat de XOR cu ieșirea generatorului și vrem să începem să vedem ultima treime a filmului.

Tom avatar
drapel tf
Tom
Ce este accesul direct la fluxul generat?
fgrieu avatar
drapel ng
@Tom: vezi * în răspunsul actualizat.

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.