Twierdzenie generatora pseudolosowego
W teorii złożoności obliczeniowej i kryptografii istnienie generatorów pseudolosowych jest związane z istnieniem funkcji jednokierunkowych poprzez szereg twierdzeń, zbiorczo określanych jako twierdzenie o generatorze pseudolosowym .
Wstęp
Pseudolosowość
Rozkład jest uważany za pseudolosowy , jeśli żadne wydajne obliczenia nie są w stanie odróżnić go od prawdziwego rozkładu jednostajnego z nieistotną przewagą . Formalnie rodzina rozkładów D n jest pseudolosowa , jeśli dla obwodu o dowolnym rozmiarze wielomianu C i dowolnego ε wielomianu odwrotnego w n
- |Prawd x ∈ U [ do ( x )=1] − Prawd x ∈ re [ do ( x )=1] | ≤ ε .
Generatory pseudolosowe
Funkcja G l : {0,1} l → {0,1} m , gdzie l < m jest generatorem pseudolosowym, jeżeli:
- G l można obliczyć wielomianem czasu w l
- G l ( x ) jest pseudolosowe, gdy x jest jednostajnie losowe.
Jeden dodatkowy pseudolosowy bit implikuje wielomianowo więcej pseudolosowych bitów
Można pokazać, że jeśli istnieje generator pseudolosowy G l : {0,1} l → {0,1} l +1 , czyli generator dodający tylko jeden bit pseudolosowy, to dla dowolnego m = poly ( l ), istnieje generator pseudolosowy G' l : {0,1} l → {0,1} m .
Idea dowodu jest następująca: pierwsze s bity z rozkładu jednostajnego U l są wybierane i używane jako ziarno do pierwszego wystąpienia G l , o którym wiadomo, że jest generatorem pseudolosowym. Następnie wyjście pierwszej instancji Gl ostatni jest dzielone na dwie części: l pierwszych bitów jest wprowadzanych do drugiej instancji Gl jako ziarno, podczas gdy . bit staje się pierwszym bitem wyjścia Powtarzanie tego procesu m razy daje wynik m pseudolosowe bity.
Można wykazać, że taki G' l , który składa się z m przypadków G l , jest rzeczywiście generatorem pseudolosowym, stosując podejście hybrydowe i dowód przez sprzeczność w następujący sposób:
Rozważmy rozkłady pośrednie m+1 H i : 0 ≤ i ≤ m , gdzie pierwsze i bity są wybierane z rozkładu jednostajnego, a ostatnie m − i bity są wybierane z wyjścia G' l . Zatem H jest 0 pełnym wyjściem G'l , a Hm jest prawdziwym rozkładem jednorodnym Um . Zatem rozkłady H i oraz H i+1 będzie inny tylko w jednym bicie (bit numer i +1).
Załóżmy teraz, że G' l nie jest rozkładem pseudolosowym; to znaczy, że istnieje pewien obwód C , który może rozróżnić G' l i U m z przewagą ε = 1/ poli ( l ). Innymi słowy, Hm ten obwód może rozróżniać H 0 i . Dlatego istnieje takie i , że obwód C może rozróżnić Hi i H i+1 o co najmniej ε / m . Zauważ, że skoro m są wielomianami w l , to ε / m jest również wielomianem w l i nadal jest zaletą, której nie można pominąć.
Gl że mamy dane l+1 bitów, które są albo wyjściem , albo a losowane z rozkładu jednorodnego. Wykorzystajmy podejście polegające na budowaniu dużych generatorów pseudolosowych z instancji G l i skonstruujmy ciąg pseudolosowych bitów o długości m-i-1 w ten sam sposób, w jaki skonstruowano G' l powyżej, używając pierwszych l danych bitów jako materiału siewnego. Następnie utwórzmy łańcuch składający się z i bity wylosowane z uniformu, połączone z ostatnim z podanych bitów, po których następują utworzone m-i-1 bity. Wynikowym wyjściem jest H i lub H i+1 , ponieważ bit i+1 Gl jest albo pobierany z uniformu, albo z . Skoro z założenia możemy rozróżnić H i i H i+1 z niewątpliwą przewagą, to możemy rozróżnić U i G l , co implikuje, że G l nie jest generatorem pseudolosowym, co jest sprzeczne z hipotezą. CO BYŁO DO OKAZANIA
Teraz zilustrujmy, że jeśli istnieje, obwód rozróżniający Gl . i Ul +1 nie musi rzucać przypadkowymi monetami Jak wykazaliśmy powyżej, jeśli istnieje obwód C do rozróżniania G' l i U m , gdzie m = poly ( l ), to istnieje obwód C' do rozróżniania między G l i U l+1 , który używa i losowe bity. Dla tego obwodu C' : | Prawd u, s [ C' ( u 1 ,..., u ja , G l ( s )) = 1 ] - Prawd u, y [ C' ( u 1 ,>,..., u ja , y ) = 1] | ≥ ε / m ,
gdzie u jest ciągiem i jednolicie losowych bitów, s jest ciągiem l jednolicie losowych bitów, a y jest ciągiem l +1 jednolicie losowych bitów.
Następnie,
Spróbuj u [ | Prawd s [ C' ( u 1 ,..., u ja , G l ( s )) = 1] - Prawd y [ C' ( u 1 ,..., u ja , y ) = 1] | ] ≥ ε / m ;
Co oznacza, że istnieje pewien stały ciąg u i bitów , Gl który może być użyty jako „wskazówka” dla obwodu C' w celu rozróżnienia między i Ul +1 .
Istnienie generatorów pseudolosowych
Istnienie generatorów pseudolosowych jest związane z istnieniem funkcji jednokierunkowych i twardych predykatów . Formalnie generatory pseudolosowe istnieją wtedy i tylko wtedy, gdy istnieją funkcje jednokierunkowe lub
PRG ↔ MFW
Definicje
Funkcje jednokierunkowe
Intuicyjnie funkcje jednokierunkowe to funkcje, które są łatwe do obliczenia i trudne do odwrócenia. Innymi słowy, złożoność (lub rozmiar obwodu) funkcji jest znacznie mniejsza niż jej odwrotności. Formalnie: Funkcja ƒ: {0,1} n → {0,1} n jest ( S , ε ) jednokierunkowa , jeśli dla dowolnego obwodu C o rozmiarze ≤ S ,
Prawd[ƒ( do (ƒ( x ))) = ƒ( x )] ≤ ε .
Ponadto ƒ jest funkcją jednokierunkową, jeśli
- ƒ można obliczyć w czasie wielomianowym
- ƒ jest ( poli ( n ), 1/ poli ( n )) jednokierunkowe
Twardy predykat
Funkcja B : {0,1} n → {0,1} jest twardym predykatem dla funkcji ƒ jeśli
- B można obliczyć w czasie wielomianowym
- dla dowolnego obwodu wielomianowego C i dowolnego nie pomijalnego ε = 1/ poly ( n ), Prob x~U [ C (ƒ( x )) = B ( x )] ≤ 1/2+ ε
Innymi słowy, trudno jest przewidzieć B ( x ) na podstawie funkcji ƒ ( x ).
Dowód
Tutaj podany jest zarys dowodu. Szczegółowe dowody znajdują się w referencjach.
PRG → OWF
Rozważmy generator pseudolosowy G l : {0,1} l → {0,1} 2l . Stwórzmy następującą funkcję jednokierunkową ƒ: {0,1} n → {0,1} n , która używa pierwszej połowy wyjścia G l jako wyjścia. Formalnie,
ƒ( x , y ) → G l ( x )
Kluczową obserwacją uzasadniającą taki wybór jest to, że obraz funkcji ma rozmiar 2 n i jest pomijalnym ułamkiem wszechświata obrazu wstępnego o rozmiarze 2 2n .
Aby udowodnić, że ƒ jest rzeczywiście funkcją jednokierunkową, skonstruujmy argument przez sprzeczność. Załóżmy, że istnieje obwód C , który odwraca ƒ z korzyścią ε :
Prawd[ƒ( do (ƒ( x , y ))) = ƒ( x , y )] > ε
Następnie możemy stworzyć następujący algorytm, który odróżni G l od uniformu, co jest sprzeczne z hipotezą. Algorytm wziąłby wejście 2n bitów z i obliczyłby ( x , y ) = C ( z ). Jeśli G l ( x ) = z algorytm zaakceptowałby, w przeciwnym razie odrzuca.
Teraz, jeśli z jest rysowane z rozkładu jednorodnego, prawdopodobieństwo, że powyższy algorytm zaakceptuje, wynosi ≤ 1/2 l , ponieważ rozmiar obrazu wynosi 1/2 l rozmiaru obrazu wstępnego. Jeśli jednak z zostało wylosowane z wyjścia G l , to prawdopodobieństwo akceptacji wynosi > ε przy założeniu istnienia obwodu C . Dlatego przewaga obwodu C w rozróżnianiu między jednorodnym U a wyjściem Gl > jest ε − 1/2 l , co nie jest pomijalne, a zatem jest sprzeczne z naszym założeniem, że G l jest generatorem pseudolosowym. CO BYŁO DO OKAZANIA
OWF → PRG
W tym przypadku udowodnimy słabszą wersję twierdzenia:
Permutacja jednokierunkowa → generator pseudolosowy
Permutacja jednokierunkowa to funkcja jednokierunkowa będąca jednocześnie permutacją bitów wejściowych. Generator pseudolosowy można zbudować z jednokierunkowej permutacji ƒ w następujący sposób:
Gl : {0,1} l →{0,1} l +1 = ƒ( x ). B ( x ), gdzie B jest twardym predykatem ƒ i „.” jest operatorem konkatenacji. Zauważ, że na podstawie twierdzenia udowodnionego powyżej wystarczy wykazać istnienie generatora, który dodaje tylko jeden pseudolosowy bit.
Twardy predykat → PRG
Najpierw pokażmy, że jeśli B jest twardym predykatem dla ƒ, to Gl jest rzeczywiście pseudolosowy. Ponownie użyjemy argumentu przez sprzeczność.
Załóżmy, że G l nie jest generatorem pseudolosowym; to znaczy istnieje obwód C o rozmiarze wielomianu, który wyróżnia G l ( x ) =ƒ( x ). B ( x ) z U l+1 z przewagą ≥ ε , gdzie ε nie jest pomijalne. Zauważ, że ponieważ ƒ( x ) jest permutacją, to jeśli x jest rysowane z rozkładu jednorodnego, to tak jest, jeśli ƒ ( x ). Dlatego Ul +1 jest równoważne ƒ( x ). b , gdzie b jest bitem rysowanym niezależnie od rozkładu jednorodnego. Formalnie,
Prawd.x ~U [ C ( G ( x ))=1] − Prawd. x~U,b~U [ C ( xb )=1] ≥ ε
Skonstruujmy następujący algorytm C' :
1. Biorąc pod uwagę z=f(x) zgadnij bit b 2. Uruchom C na zb 3. IF C(zb)=1 4. wyjście b 5. ELSE 6. wyjście 1-b
Biorąc pod uwagę wynik ƒ, algorytm najpierw zgaduje bit b , rzucając losową monetą, tj. Prob[ b =0] = Prob[ b =1] = 0,5. Następnie algorytm (obwód) C jest uruchamiany na f(x).b i jeśli wynikiem jest 1, to wyprowadzane jest b , w przeciwnym razie zwracana jest odwrotność b .
Wtedy prawdopodobieństwo poprawnego odgadnięcia przez C' B ( x ) wynosi:
Prawd. x~U [ C' ( z )= B ( x )] =
Prawd[ b = B ( x ) ∧ do ( zb )=1] + Prawd[ b ≠ B ( x ) ∧ do ( zb )=0] =
Prawd[ b = B ( x )]⋅Prób[ C ( zb )=1 | b = B ( x )] + Prawd[ b ≠ B ( x )]⋅Prób[ do ( zb )=0 | b ≠ b ( x )] =
1/2⋅Prób[ C ( zb )=1 | b = B ( x )] + 1/2⋅Prób[ C ( zb )=0 | b ≠ b ( x )] =
(1−1/2)⋅Prób[ C ( zb )=1 | b = B ( x )] + 1/2⋅(1−Pr.[ C ( zb )=1 | b ≠ B ( x )]) =
1/2+Pr.z.b ~G(x) [ C ( zb )=1] − 1/2⋅(Pr.[ C ( zb )=1 | b = B ( x )]+Pr.[ C ( zb )=1 | b ≠ B ( x )]) =
1/2+Pr.z.b ~G(x) [ C ( zb )=1] − Prawd. z.b~U [ C ( zb )=1] ≥ 1/2+ ε
Oznacza to, że obwód C' może przewidywać B ( x ) z prawdopodobieństwem większym niż 1/2 + ε , co oznacza, że B nie może być twardym predykatem dla ƒ i hipoteza jest sprzeczna. CO BYŁO DO OKAZANIA
OWP → twardy predykat
Zarys dowodu jest następujący:
Jeśli ƒ{0,1} n →{0,1} n jest permutacją jednokierunkową, to tak samo jest ƒ'{0,1} 2n →{0,1} 2n , gdzie ƒ'( x , y )= ƒ( x ). z definicji. Wtedy B ( x , y )= x ⋅ y jest twardym predykatem dla ƒ', gdzie ⋅ jest wektorowym iloczynem skalarnym . Aby udowodnić, że jest to rzeczywiście hard-core, załóżmy inaczej i pokażmy sprzeczność z hipotezą, że ƒ jest jednokierunkowa. Jeśli B nie jest twardym predykatem, to istnieje obwód C , który to przewiduje, więc
Prawd. x,y [ do (ƒ( x ), y )= x ⋅ y ] ≥ 1/2+ ε . Fakt ten można wykorzystać do odzyskania x poprzez sprytne skonstruowanie permutacji y , które izolują bity w x . W rzeczywistości dla stałego ułamka x istnieje algorytm czasu wielomianowego, który wymienia kandydatów O (1/ &epsilon 2 ), które obejmują wszystkie poprawne x . Zatem algorytm może odwrócić ƒ ( x ) w czasie wielomianowym dla nie pomijalnego ułamka x , co jest sprzeczne z hipotezą.
- W. Diffie, ja Hellman. „Nowe kierunki w kryptografii”. IEEE Transactions on Information Theory , IT-22, s. 644–654, 1976.
- AC Yao. „Teoria i zastosowanie funkcji zapadni”. 23. Sympozjum IEEE na temat podstaw informatyki , s. 80–91, 1982.
- M. Blum i S. Micali „Jak generować kryptograficznie silne sekwencje pseudolosowych bitów”. SIAM Journal on Computing , v13, s. 850–864, 1984.
- J. Hastad, R. Impagliazzo, LA Levin i M. Luby. „Generator pseudolosowości z dowolnej funkcji jednokierunkowej”. SIAM Journal on Computing , v28 n4, s.-1364-1396, 1999.