Pseudoslumpgeneratorsats
Inom beräkningskomplexitetsteori och kryptografi är förekomsten av pseudoslumpgeneratorer relaterad till förekomsten av envägsfunktioner genom ett antal satser, kollektivt kallade pseudoslumpgeneratorteorem .
Introduktion
Pseudoslumpmässighet
En fördelning anses vara pseudoslumpmässig om ingen effektiv beräkning kan skilja den från den verkliga enhetliga fördelningen med en icke- försumbar fördel . Formellt är en familj av distributioner D n pseudoslumpmässig om för vilken polynomstorlekskrets C som helst , och alla ε omvänt polynom i n
- |Prob x ∈ U [ C ( x )=1] − Sannolik x ∈ D [ C ( x )=1] | ≤ ε .
Pseudoslumpgeneratorer
En funktion G l : {0,1} l → {0,1} m , där l < m är en pseudoslumpgenerator om:
- G l kan beräknas i tidspolynom i l
- Gl , ( x ) är pseudoslump när x är enhetligt slumpmässigt.
En ytterligare pseudoslumpmässig bit innebär polynomiskt fler pseudoslumpmässiga bitar
Det kan visas att om det finns en pseudoslumpgenerator G l : {0,1} l → {0,1} l +1 , dvs en generator som bara adderar en pseudoslumpmässig bit, då för valfri m = poly ( l ), det finns en pseudoslumpgenerator G' l : {0,1} l → {0,1} m .
Tanken med beviset är följande: första s bitar från enhetlig distribution U l plockas och används som frö till den första instansen av Gl , som är känd för att vara en pseudoslumpgenerator. Därefter delas utsignalen från den första instansen av Gl i ett Gl som två delar: första 1 bitar matas in i den andra instansen av frö, medan den sista biten blir den första biten av utgången. Att upprepa denna process i m gånger ger en utmatning av m pseudoslumpmässiga bitar.
Det kan visas att sådan G'l en , som består av m instanser av Gl , verkligen är genom pseudoslumpgenerator genom att använda en hybrid metod och bevis motsägelse enligt följande:
Betrakta m+1 mellanfördelningar H i : : 0 ≤ i ≤ m, where first i bits are chosen from the uniform distribution, and last m − i bits are chosen from the output of G'l. Thus, H0 is the full output of G'l and Hm is a true uniform distribution Um. Therefore, distributions Hi and Hi+1 will be different in only one bit (bit number i+1).
Antag nu att G'l ; det vill inte är en pseudoslumpmässig fördelning Um säga det finns någon krets C som kan skilja mellan G' l och med fördelen ε = 1/ poly ( l ). Med andra ord kan denna krets skilja mellan H 0 och Hm . Därför finns det sådan i att kretsen C kan skilja mellan Hi . och Hi 1 + med åtminstone ε/m Observera att eftersom m är polynom i l , så är ε / m också polynom i l och är fortfarande en icke försumbar fördel.
Antag nu att vi får l+1 bitar som antingen utmatas av Gl . eller dras från enhetlig fördelning Låt oss återanvända metoden att bygga stora pseudoslumpgeneratorer av instanser av G'l Gl och m konstruera en sträng av pseudoslumpmässiga bitar med längden −i−1 på samma sätt som konstruerades ovan med de första l givna bitarna som frö. Låt oss sedan skapa en sträng som består av i- bitar dragna från uniform, sammanlänkade med den sista av de givna bitarna, följt av de skapade m−i−1- bitarna. Den resulterande utsignalen är antingen Hi . eller Hi 1 Gl + , eftersom i + 1 -biten antingen hämtas från uniform eller från Eftersom vi genom antagande kan skilja mellan H i och H i+1 med en icke försumbar fördel Gl , då kan vi skilja mellan U och G l , vilket innebär att inte är en pseudoslumpgenerator, vilket är en motsägelse till hypotesen. QED
Låt oss nu illustrera att om den finns behöver kretsen för att skilja mellan Gl . och Ul +1 inte kasta slumpmässiga mynt Som vi visade ovan, om det finns en krets C för att skilja mellan G'l ' och Um C Gl , där m = poly ( l ), så existerar en krets för att skilja mellan och Ul +1 som använder i slumpmässiga bitar. För denna krets C' : | Prob u, s [ C' ( u 1 ,...,u i ,G l ( s )) = 1 ] − Prob u, y [ C' ( u 1 ,>,...,u i ,y ) = 1] | ≥ ε / m ,
där u är en sträng med i likformigt slumpmässiga bitar, s är en sträng med l likformigt slumpmässiga bitar och y är en sträng med l +1 likformigt slumpmässiga bitar.
Sedan,
Förmodligen u [ | Sannolikhet s [ C' ( u 1 , ..., ui , G l ( s )) = 1] - Sannolikhet [ C ' ( u 1 ,..., u i , y ) = 1] | ] ≥ e/m ;
Vilket betyder att det finns någon fast sträng u av i -bitar som kan användas som ett "råd" till krets C ' för att skilja mellan Gl . och Ul +1
Förekomsten av pseudoslumpgeneratorer
Förekomsten av pseudoslumpgeneratorer är relaterad till förekomsten av envägsfunktioner och hårda predikat . Formellt existerar pseudoslumpgeneratorer om och endast om envägsfunktioner finns, eller
PRG ↔ OWF
Definitioner
Envägsfunktioner
Intuitivt envägsfunktioner är funktioner som är lätta att beräkna och svåra att invertera. Med andra ord är komplexiteten (eller kretsstorleken) för funktionen mycket mindre än den för dess inversa. Formellt: En funktion ƒ: {0,1} n → {0,1} n är ( S , ε ) enkelriktad om för någon krets C med storlek ≤ S ,
Sannolikt[ƒ( C (ƒ( x ))) = ƒ( x )] ≤ ε .
Dessutom är ƒ en enkelriktad funktion if
- ƒ kan beräknas i polynomtid
- ƒ är ( poly ( n ), 1/ poly ( n )) enkelriktad
Hård kärna predikat
Funktion B : {0,1} n → {0,1} är ett fast predikat för funktion ƒ om
- B kan beräknas i polynomtid
- C som helst av polynomstorlek och vilken som helst icke försumbar ε = 1/ poly ( n ), Sannolikt x~U [ C (ƒ( x )) = B ( x )] ≤ 1/2+ ε
Med andra ord är det svårt att förutsäga B ( x ) från funktion ƒ( x ).
Bevis
Här ges en översikt över beviset. Se referenser för detaljerade bevis.
PRG → OWF
Betrakta en pseudoslumpgenerator G l : {0,1} l → {0,1} 2l . Låt oss skapa följande envägsfunktion ƒ: {0,1} n → {0,1} n som använder den första hälften av utdata från G l som sin utdata. Formellt,
ƒ( x , y ) → G l ( x )
En nyckelobservation som motiverar ett sådant urval är att bilden av funktionen är av storleken 2n och är en försumbar del av förbildsuniversumet av storleken 22n .
För att bevisa att ƒ verkligen är en enkelriktad funktion låt oss konstruera ett argument genom motsägelse. Antag att det finns en krets C som inverterar ƒ med fördel ε :
Sannolikt[ƒ( C (ƒ( x , y ))) = ƒ( x , y )] > ε
Sedan kan vi skapa följande algoritm som kommer att skilja G l från uniform, vilket motsäger hypotesen. Algoritmen skulle ta en ingång på 2n bitar z och beräkna ( x , y ) = C ( z ). Om G l ( x ) = z skulle algoritmen acceptera, annars avvisar den.
Nu, om z dras från enhetlig fördelning, är sannolikheten att ovanstående algoritm accepterar ≤ 1/2 l , eftersom storleken på bilden är 1/2 l av storleken på förbilden. Emellertid, om z togs från utsignalen från Gl om så är sannolikheten för acceptans > ε genom antagandet förekomsten av krets C . Därför är fördelen som krets C har när det gäller Gl att skilja mellan den enhetliga U och utsignalen från Gl är > ε − 1/2 l , vilket icke försumbart och således motsäger vårt antagande om att är en pseudoslumpgenerator. QED
OWF → PRG
För det här fallet bevisar vi en svagare version av satsen:
Enkelriktad permutation → pseudoslumpgenerator
En envägspermutation är en envägsfunktion som också är en permutation av inmatningsbitarna. En pseudoslumpgenerator kan konstrueras från envägspermutation ƒ enligt följande:
Gl : {0,1} l →{0,1} l +1 = ƒ( x ). B ( x ), där B är ett fast predikat för ƒ och "." är en sammanlänkningsoperatör. Notera att genom satsen som bevisats ovan behövs det bara för att visa existensen av en generator som bara lägger till en pseudoslumpmässig bit.
Hård kärna predikat → PRG
Låt oss först visa att om B är ett hårt predikat för ƒ så är G l verkligen pseudoslumpmässigt. Återigen kommer vi att använda ett argument med motsägelse.
Antag att Gl inte är en pseudoslumpgenerator; det vill säga det finns krets C med polynomstorlek som särskiljer G l ( x ) =ƒ( x ). B ( x ) från U l+1 med fördel ≥ ε , där ε är icke försumbar. Observera att eftersom ƒ( x ) är en permutation, så om x dras från enhetlig fördelning, så om ƒ( x ). Därför U l+1 ekvivalent med ƒ( x ). b , där b är lite ritad oberoende av en enhetlig fördelning. Formellt,
Sannolikt x~U [ C ( G ( x ))=1] − Sannolikt x~U,b~U [ C ( xb )=1] ≥ ε
Låt oss konstruera följande algoritm C' :
1. Givet z=f(x) gissningsbit b 2. Kör C på zb 3. OM C(zb)=1 4. utgång b 5. ANNAT 6. utgång 1-b
Givet utdata från ƒ gissar algoritmen först bit b genom att kasta ett slumpmässigt mynt, dvs Sannolik[ b =0] = Sannolik[ b =1] = 0,5. Sedan körs algoritmen (kretsen) C på f(x).b och om resultatet är 1 matas b ut, annars returneras inversen av b .
Då är sannolikheten för att C' gissar B ( x ) korrekt:
Sannolikt x~U [ C' ( z )= B ( x )] =
Sannolikt[ b = B ( x ) ∧ C ( zb )=1] + Sannolikt[ b ≠ B ( x ) ∧ C ( zb )=0] =
Sannolikt[ b = B ( x )] ⋅ Sannolikt[ C ( zb )=1 | b = B ( x )] + Sannolikt[ b ≠ B ( x )]⋅Prob[ C ( zb )=0 | b ≠ B ( x )] =
1/2⋅Prob[ C ( zb )=1 | b = B ( x )] + 1/2⋅Prob[ C ( zb )=0 | b ≠ B ( x )] =
(1−1/2)⋅Prob[ C ( zb )=1 | b = B ( x )] + 1/2⋅(1−Prob[ C ( zb )=1 | b ≠ B ( x )]) =
1/2+Prob z.b~G(x) [ C ( zb )=1] − 1/2⋅(Prob[ C ( zb )=1 | b = B ( x )]+Prob[ C ( zb )=1 | b ≠ B ( x )]) =
1/2+Prob z.b~G(x) [ C ( zb )=1] − Sannolikt z.b~U [ C ( zb )=1] ≥ 1/2+ ε
Detta innebär att krets C' kan förutsäga B ( x ) med sannolikhet mer än 1/2 + ε , vilket betyder att B inte kan vara ett hårt kärnpredikat för ƒ och hypotesen motsägs. QED
OWP → hårt predikat
Konturen av beviset är som följer:
Om ƒ{0,1} n →{0,1} n är en enkelriktad permutation, så är det också ƒ'{0,1} 2n →{0,1} 2n , där ƒ'( x , y )= ƒ( x ). y per definition. Då B ( x , y )= x ⋅ y ett hårt predikat för ƒ', där ⋅ är en vektorprickprodukt . För att bevisa att det verkligen är hårt, låt oss anta något annat, och visa en motsägelse med hypotesen om att ƒ är enkelriktad. Om B inte är ett hårt predikat, så finns det en krets C som förutsäger det, så
Sannolikt x,y [ C (ƒ( x ), y )= x ⋅ y ] ≥ 1/2+ ε . Det faktum kan användas för att återställa x genom att på ett smart sätt konstruera permutationer y som isolerar bitar i x . För en konstant bråkdel av x finns det faktiskt en polynomtidsalgoritm som listar O (1/ &epsilon 2 ) kandidater som inkluderar alla giltiga x . Således kan en algoritm invertera ƒ( x ) i polynomtid för en icke försumbar bråkdel av x , vilket motsäger hypotesen.
- W. Diffie, ME Hellman. "Nya riktningar i kryptografi." IEEE Transactions on Information Theory , IT-22, s. 644–654, 1976.
- AC Yao. "Teori och tillämpning av falldörrsfunktioner." 23:e IEEE Symposium on Foundations of Computer Science , s. 80–91, 1982.
- M. Blum och S. Micali "Hur man genererar kryptografiskt starka sekvenser av pseudo-slumpmässiga bitar." SIAM Journal on Computing , v13, s. 850–864, 1984.
- J. Hastad, R. Impagliazzo, LA Levin och M. Luby. "En pseudoslumpgenerator från vilken enkelriktad funktion som helst." SIAM Journal on Computing , v28 n4, s.-1364-1396, 1999.