Pseudoslumpgenerator

Inom teoretisk datavetenskap och kryptografi är en pseudoslumpgenerator (PRG) för en klass av statistiska tester en deterministisk procedur som mappar ett slumpmässigt frö till en längre pseudoslumpmässig sträng så att inget statistiskt test i klassen kan skilja mellan utdata från generatorn och den enhetliga fördelningen. Själva slumpmässiga fröet är vanligtvis en kort binär sträng som dras från den enhetliga fördelningen .

Många olika klasser av statistiska tester har övervägts i litteraturen, bland dem klassen för alla booleska kretsar av en given storlek. Det är inte känt om det finns bra pseudoslumpgeneratorer för denna klass, men det är känt att deras existens i en viss mening är likvärdig med (obevisade) nedre kretsgränser i beräkningskomplexitetsteori . Därför vilar konstruktionen av pseudoslumpgeneratorer för klassen av booleska kretsar av en given storlek på för närvarande oprövade hårdhetsantaganden.

Definition

Låt ${\mathcal {A}}=\{A:\{0,1\}^{n}\to \{0, 1\}^{*}\}$ vara en klass av funktioner. Dessa funktioner är de statistiska tester som pseudoslumpgeneratorn kommer att försöka lura, och de är vanligtvis algoritmer . Ibland kallas de statistiska testerna även för motståndare eller särskiljare . Notationen i funktionernas koddomän är Kleene-stjärnan .

En funktion $G:\{0,1\}^{\ell }\to \{0,1\}^{n}$ med $\ell <n$ är en pseudoslumpgenerator mot ${\mathcal {A}}$ med bias $\varepsilon$ if, för varje $A$ i ${ \mathcal {A}}$ , det statistiska avståndet mellan fördelningarna $A(G(U_{\ell }))$ och $A(U_{ n})$ är högst $\varepsilon$ , där $U_{k}$ är den enhetliga fördelningen på $\{0,1\}^{k}$ .

Kvantiteten $\ell$ kallas frölängden och kvantiteten $n-\ell$ kallas sträckan av pseudoslumpgeneratorn.

En pseudoslumpgenerator mot en familj av motståndare $({\mathcal {A}}_{n})_{n\in \mathbb {N} }$ med bias $\varepsilon (n)$ är en familj av pseudoslumpgeneratorer ${\displaystyle (G_{n})_{n\in \mathbb {N} }} ,$ där ${\displaystyle G_{n}:\{0,1\}^{\ell (n)}\to \{0,1\}^{n}} är$ en pseudoslumpgenerator mot ${\mathcal {A}}_{n}$ med bias $\varepsilon (n)$ och frölängd $\ell (n)$ .

I de flesta applikationer representerar familjen ${\mathcal {A}}$ någon beräkningsmodell eller någon uppsättning algoritmer , och man är intresserad av att designa en pseudoslumpgenerator med liten frölängd och bias, och så att utdata av generatorn kan beräknas med samma sorts algoritm.

I kryptografi

Inom kryptografi består klassen ${\mathcal {A}}$ vanligtvis av alla kretsar av storlekspolynom i ingången och med en enbitsutgång, och man är intresserad av att designa pseudoslumpgeneratorer som är beräkningsbara av ett polynom- tidsalgoritm och vars bias är försumbar i kretsstorleken. Dessa pseudoslumpgeneratorer kallas ibland kryptografiskt säkra pseudoslumpgeneratorer (CSPRGs) .

Det är inte känt om det finns kryptografiskt säkra pseudoslumpgeneratorer. Att bevisa att de existerar är svårt eftersom deras existens innebär P ≠ NP , vilket är allmänt trott men ett känt öppet problem. Förekomsten av kryptografiskt säkra pseudoslumpgeneratorer tros allmänt. Detta beror på att det har bevisats att pseudoslumpgeneratorer kan konstrueras från vilken envägsfunktion som helst som tros existera. Pseudoslumpgeneratorer är nödvändiga för många applikationer inom kryptografi .

Teoremet för pseudoslumpgenerator visar att kryptografiskt säkra pseudoslumpgeneratorer existerar om och endast om envägsfunktioner finns.

Används

Pseudoslumpgeneratorer har många tillämpningar inom kryptografi. Till exempel ger pseudoslumpgeneratorer en effektiv analog av engångsplattor . Det är välkänt att för att kryptera ett meddelande m på ett sätt så att chiffertexten inte ger någon information om klartexten, måste nyckeln k som används vara slumpmässig över strängar med längd |m|. Perfekt säker kryptering är mycket kostsamt när det gäller nyckellängd. Nyckellängden kan reduceras avsevärt med en pseudoslumpgenerator om perfekt säkerhet ersätts av semantisk säkerhet . Vanliga konstruktioner av strömchiffer är baserade på pseudoslumpgeneratorer.

Pseudoslumpgeneratorer kan också användas för att konstruera symmetriska nyckelkryptosystem , där ett stort antal meddelanden säkert kan krypteras under samma nyckel. En sådan konstruktion kan baseras på en pseudoslumpmässig funktionsfamilj , som generaliserar föreställningen om en pseudoslumpgenerator.

På 1980-talet började simuleringar inom fysiken använda pseudoslumpgeneratorer för att producera sekvenser med miljarder element, och i slutet av 1980-talet hade bevis utvecklats för att ett fåtal vanliga generatorer gav felaktiga resultat i sådana fall som fasövergångsegenskaper hos 3D Ising- modellen och former av diffusionsbegränsade aggregat. Sedan på 1990-talet användes olika idealiseringar av fysiksimuleringar - baserade på slumpmässiga vandringar , korrelationsfunktioner , lokalisering av egentillstånd, etc., som test av pseudoslumpgeneratorer.

Testning

NIST tillkännagav SP800-22 slumpmässighetstester för att testa om en pseudoslumpgenerator producerar slumpmässiga bitar av hög kvalitet. Yongge Wang visade att NIST-testning inte är tillräckligt för att upptäcka svaga pseudoslumpgeneratorer och utvecklade statistisk distansbaserad testteknik LILtest.

För avrandomisering

En huvudsaklig tillämpning av pseudoslumpgeneratorer ligger i avrandomisering av beräkningar som förlitar sig på slumpmässighet, utan att förstöra resultatet av beräkningen. Fysiska datorer är deterministiska maskiner, och att få sann slumpmässighet kan vara en utmaning. Pseudoslumpgeneratorer kan användas för att effektivt simulera randomiserade algoritmer med liten eller ingen slumpmässighet. I sådana applikationer beskriver klassen ${\mathcal {A}}$ den randomiserade algoritmen eller klassen av randomiserade algoritmer som man vill simulera, och målet är att designa en "effektivt beräkningsbar" pseudoslumpgenerator mot ${\ displaystyle {\mathcal {A}}}$ vars frölängd är så kort som möjligt. Om en fullständig derandomisering önskas, fortsätter en fullständigt deterministisk simulering genom att ersätta den slumpmässiga ingången till den randomiserade algoritmen med den pseudoslumpmässiga strängen som produceras av pseudoslumpgeneratorn. Simuleringen gör detta för alla möjliga frön och medelvärdet av utdata från de olika körningarna av den randomiserade algoritmen på ett lämpligt sätt.

Konstruktioner

För polynomtid

En grundläggande fråga inom beräkningskomplexitetsteorin är om alla polynomtidsrandomiserade algoritmer för beslutsproblem deterministiskt kan simuleras i polynomtid. Förekomsten av en sådan simulering skulle innebära att BPP = P . För att utföra en sådan simulering är det tillräckligt att konstruera pseudoslumpgeneratorer mot familjen F av alla kretsar av storleken s ( n ) vars ingångar har längden n och matar ut en enda bit, där s ( n ) är ett godtyckligt polynom, frölängden för pseudoslumpgeneratorn är O(log n ) och dess förspänning är ⅓.

1991 tillhandahöll Noam Nisan och Avi Wigderson en kandidat pseudoslumpgenerator med dessa egenskaper. 1997 Russell Impagliazzo och Avi Wigderson att konstruktionen av Nisan och Wigderson är en pseudoslumpgenerator förutsatt att det finns ett beslutsproblem som kan beräknas i tiden 2 ^{O( n )} på ingångar med längden n men kräver kretsar av storleken 2 ^{Ω( n )} .

För logaritmiskt utrymme

Även om obevisade antaganden om kretskomplexitet behövs för att bevisa att Nisan–Wigderson-generatorn fungerar för tidsbegränsade maskiner, är det naturligt att begränsa klassen av statistiska tester ytterligare så att vi inte behöver förlita oss på sådana obevisade antaganden. En klass för vilken detta har gjorts är klassen av maskiner vars arbetsutrymme begränsas av $O(\log n)$ . Genom att använda ett upprepat kvadratknep känt som Savitchs teorem är det lätt att visa att varje probabilistisk log-rymdberäkning kan simuleras i rymden $O(\log ^{2}n)$ . Noam Nisan (1992) visade att denna derandomisering faktiskt kan uppnås med en pseudoslumpgenerator av frölängd $O(\log ^{2}n)$ som lurar alla $O(\log n)$ -mellanrumsmaskiner. Nisans generator har använts av Saks och Zhou (1999) för att visa att probabilistisk log-rymdsberäkning kan simuleras deterministiskt i rymden $O(\log ^{1.5}n)$ . Detta resultat är fortfarande det mest kända avrandomiseringsresultatet för generella loggutrymmesmaskiner 2012.

För linjära funktioner

När de statistiska testerna består av alla multivariata linjära funktioner över något ändligt fält $\mathbb {F}$ , talar man om epsilon-biased generatorer . Konstruktionen av Naor & Naor (1990) uppnår en frölängd på $\ell =\log n+O(\log(\epsilon ^{- 1}))$ , vilket är optimalt upp till konstanta faktorer. Pseudoslumpgeneratorer för linjära funktioner fungerar ofta som en byggsten för mer komplicerade pseudoslumpgeneratorer.

För polynom

Viola (2008) bevisar att om man tar summan av $d$ småförspänningsgeneratorer lurar polynom med graden $d$ . Frölängden är $\ell =d\cdot \log n+O(2^{d}\cdot \log( \epsilon ^{-1}))$ .

För kretsar med konstant djup

Kretsar med konstant djup som producerar en enda utgångsbit. ^{[ citat behövs ]}

Begränsningar av sannolikhet

De pseudoslumpgeneratorer som används i kryptografi och universell algoritmisk derandomisering har inte bevisats existera, även om deras existens tros allmänt [ ^{citat behövs ]} . Bevis för deras existens skulle innebära bevis på lägre gränser för kretskomplexiteten hos vissa explicita funktioner. Sådana nedre gränser för kretsar kan inte bevisas inom ramen för naturliga bevis förutsatt att det finns starkare varianter av kryptografiska pseudoslumpgeneratorer [ ^{citat behövs ]} .

Sanjeev Arora och Boaz Barak, Computational Complexity: A Modern Approach , Cambridge University Press (2009), ISBN 9780521424264 .
Oded Goldreich , Computational Complexity: A Conceptual Perspective , Cambridge University Press (2008), ISBN 978-0-521-88473-0 .
Oded Goldreich , Foundations of Cryptography: Basic Tools , Cambridge University Press (2001), ISBN 9780521791724 .
Naor, Joseph; Naor, Moni (1990), " Small -bias Probability Spaces: efficient constructions and Applications" , Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, STOC 1990 : 213–223, CiteSeerX 10.1.1.421,017 ,017 ,017 , 017 . 100216.100244 , ISBN 978-0897913614 , S2CID 14031194
Viola, Emanuele (2008), "Summan av d småförspänningsgeneratorer lurar polynom av grad d" (PDF) , Proceedings of the 23rd Annual Conference on Computational Complexity (CCC 2008) : 124–127, CiteSeerX 10.1.1.5420 , doi : 10.1109/CCC.2008.16 , ISBN 978-0-7695-3169-4
Den här artikeln innehåller material från Pseudorandom-generatorn på PlanetMath , som är licensierad under Creative Commons Attribution/Share-Alike-licensen .