Věta o pseudonáhodném generátoru - Pseudorandom generator theorem

v teorie výpočetní složitosti a kryptografie, existence pseudonáhodné generátory souvisí s existencí jednosměrné funkce prostřednictvím řady vět, souhrnně označovaných jako věta o generátoru pseudonáhod.

Úvod

Pseudonáhodnost

Uvažuje se o distribuci pseudonáhodné pokud ho žádný efektivní výpočet nedokáže odlišit od skutečného rovnoměrné rozdělení ne-zanedbatelný výhoda. Formálně rodina distribucí Dn je pseudonáhodné pokud pro jakýkoli obvod polynomiální velikosti Ca jakékoli ε nepřímo polynom v n

| ProbX∈U [C(X) = 1] - ProbX∈D [C(X)=1] | ≤ ε.

Generátory pseudonáhodností

Funkce Gl: {0,1}l → {0,1}m, kde l < m je pseudonáhodný generátor, pokud:

  • Gl lze vypočítat v čase polynomu v l
  • Gl(X) je pseudonáhodný, když X je jednotně náhodné.

Jeden další pseudonáhodný bit implikuje polynomiálně více pseudonáhodných bitů

Je možné ukázat, že pokud existuje pseudonáhodný generátor Gl: {0,1}l → {0,1}l+1, tj. generátor, který přidá jen jeden pseudonáhodný bit, pak pro libovolný m = poly(l), existuje pseudonáhodný generátor G'l: {0,1}l → {0,1}m.

Myšlenka důkazu je následující: zaprvé s bity z rovnoměrného rozdělení Ul jsou vybrány a použity jako semeno pro první instanci Gl, o kterém je známo, že je pseudonáhodný generátor. Dále výstup první instance Gl je rozdělena na dvě části: první l bity jsou přiváděny do druhé instance Gl jako seed, zatímco poslední bit se stane prvním bitem výstupu. Opakování tohoto procesu pro m krát poskytuje výstup m pseudonáhodné bity.

Je možné ukázat, že takové G'l, který se skládá z m instance Gl, je skutečně pseudonáhodný generátor pomocí a hybridní přístup a důkaz rozporem jak následuje:

Zvážit m + 1 mezilehlé distribuce Hi: 0 ≤ i ≤ m, kde první i bity jsou vybrány z jednotného rozdělení a poslední m - i bity jsou vybrány z výstupu G'l. Tím pádem, H0 je plný výkon G'l a Hm je skutečné jednotné rozdělení Um. Proto distribuce Hi a Hi + 1 se bude lišit pouze v jednom bitu (číslo bitu) i+1).

Předpokládejme to G'l není pseudonáhodná distribuce; to znamená, že existuje nějaký obvod C které mohou rozlišovat mezi G'l a Um s výhodou ε  =   1/poly(l). Jinými slovy, tento obvod může rozlišovat mezi H0 a Hm. Proto takové existují i že obvod C může rozlišovat mezi Hi a Hi + 1 minimálně ε / m. Všimněte si, že od té doby m jsou polynomy v l, pak ε / m je také polynom v l a stále je nezanedbatelnou výhodou.

Nyní předpokládejme, že jsme dostali l + 1 bity, které jsou buď výstupem z Gl nebo vycházející z jednotného rozdělení. Pojďme znovu použít přístup k vytváření velkých pseudonáhodných generátorů z instancí Gl a zkonstruujte řetězec pseudonáhodných bitů délky m − i − 1 stejným způsobem G'l byl postaven výše pomocí prvního l dané bity jako semeno. Poté vytvořme řetězec skládající se z i bity čerpané z uniformy, zřetězené s posledním z daných bitů, následované vytvořenými m − i − 1 bity. Výsledný výstup je buď Hi nebo Hi + 1, protože i + 1 bit je čerpán z uniformy nebo z Gl. Protože podle předpokladu můžeme rozlišovat mezi Hi a Hi + 1 s nezanedbatelný výhodou pak můžeme rozlišovat mezi U a Gl, což z toho vyplývá Gl není pseudonáhodný generátor, což je v rozporu s hypotézou. Q.E.D.

Nyní si ukážeme, že pokud existuje, obvod pro rozlišení mezi Gl a Ul + 1 nemusí házet náhodné mince. Jak jsme ukázali výše, pokud existuje obvod C pro rozlišení mezi G'l a Um, kde m = poly(l), pak existuje obvod C' pro rozlišení mezi Gl a Ul + 1 který používá i náhodné bity. Pro tento obvod C' : | Probu, s [C' (u1, ..., ui,Gl(s)) = 1] - Probu, y [C' (u1,>, ..., ui, y) = 1] | ≥ ε / m,

kde u je řetězec i rovnoměrně náhodné bity, s je řetězec l rovnoměrně náhodné bity a y je řetězec l+1 rovnoměrně náhodné bity.

Pak,

Probu[| Probs [C' (u1, ..., ui,Gl(s)) = 1] - Proby [C' (u1, ..., ui, y) = 1] | ] ≥ ε / m;

Což znamená, že existuje nějaký pevný řetězec u z i bity, které lze použít jako „radu“ do obvodu C' pro rozlišení mezi Gl a Ul + 1.

Existence pseudonáhodných generátorů

Existence pseudonáhodných generátorů souvisí s existencí jednosměrné funkce a hard-core predikáty. Formálně existují pseudonáhodné generátory tehdy a jen tehdy, pokud existují jednosměrné funkce, nebo

PRG ↔ OWF

Definice

Jednosměrné funkce

Intuitivně jednosměrné funkce jsou funkce, které lze snadno vypočítat a je těžké je invertovat. Jinými slovy, složitost (nebo velikost obvodu) funkce je mnohem menší než složitost její inverze. Formálně: Funkce ƒ: {0,1}n → {0,1}n je (S,ε) jednosměrný pokud pro jakýkoli obvod C o velikosti ≤ S,

Prob [ƒ (C(ƒ (X))) = ƒ (X)] ≤ ε.

Navíc ƒ je jednosměrná funkce -li

  • ƒ lze vypočítat v polynomiálním čase
  • ƒ je (poly(n), 1/poly(n)) jednosměrný

Tvrdý predikát

Funkce B: {0,1}n → {0,1} je a hard-core predikát pro funkci ƒ pokud

  • B lze vypočítat v polynomiálním čase
  • pro libovolný obvod polynomiální velikosti C a jakékoli nezanedbatelné ε = 1/poly(n), Probx ~ U[C(ƒ (X))  = B(X)] ≤ 1/2+ε

Jinými slovy je těžké předvídat B(X) z funkce ƒ (X).

Důkaz

Zde je uveden přehled důkazu. Podrobné důkazy najdete v referencích.

PRG → OWF

Zvažte pseudonáhodný generátor Gl: {0,1}l → {0,1}2 l. Vytvořme následující jednosměrnou funkci ƒ: {0,1}n → {0,1}n který používá první polovinu výstupu z Gl jako jeho výstup. Formálně,

ƒ (X,y) → Gl(X)

Klíčovým postřehem, který odůvodňuje takový výběr, je, že obraz funkce má velikost 2n a je zanedbatelným zlomkem předobrazového vesmíru velikosti 22n.

Abychom dokázali, že ƒ je skutečně jednosměrná funkce, vytvořme argument rozporem. Předpokládejme, že existuje obvod C že převrací ƒ s výhodou ε:

Prob [ƒ (C(ƒ (X,y))) = ƒ (X,y)] > ε

Pak můžeme vytvořit následující algoritmus, který bude rozlišovat Gl z uniformy, což je v rozporu s hypotézou. Algoritmus by vyžadoval zadání 2n bity z a vypočítat (X,y) = C(z). Li Gl(X) = z algoritmus by přijal, jinak odmítne.

Teď když z je čerpáno z rovnoměrného rozdělení, pravděpodobnost, kterou výše uvedený algoritmus akceptuje, je ≤ 1/2l, protože velikost obrázku je 1/2l velikosti předobrazu. Pokud však z byl čerpán z výstupu Gl pak je pravděpodobnost přijetí> ε za předpokladu existence obvodu C. Proto je výhodou, že obvod C má rozlišovat mezi uniformou U a výstup Gl je> ε − 1/2l, což je nezanedbatelné, a je tedy v rozporu s naším předpokladem Gl být generátorem pseudonáhod. Q.E.D.

OWF → PRG

V tomto případě dokážeme a slabší verze věty:

Jednosměrný permutace → generátor pseudonáhod

Jednosměrná permutace je jednosměrná funkce, která je také permutací vstupních bitů. Generátor pseudonáhod lze zkonstruovat z jednosměrné permutace ƒ následovně:

Gl: {0,1}l→{0,1}l+1 = ƒ (X).B(X), kde B je tvrdý predikát ƒ a "." je operátor zřetězení. Všimněte si, že podle věty prokázané výše je potřeba pouze ukázat existenci generátoru, který přidává pouze jeden pseudonáhodný bit.

Hard-core predikát → PRG

Nejprve si ukážeme, že pokud B je pak tvrdý predikát pro ƒ Gl je skutečně pseudonáhodný. Opět použijeme argument rozporem.

Předpokládat, že Gl není pseudonáhodný generátor; to znamená, že existuje obvod C polynomiální velikosti, která odlišuje Gl(X) = ƒ (X).B(X) z Ul + 1 s výhodou ≥ε, kde ε je nezanedbatelný. Všimněte si, že od ƒ (X) je permutace, pak pokud X je čerpáno z rovnoměrného rozdělení, takže pokud ƒ (X). Proto, Ul + 1 je ekvivalentní ƒ (X).b, kde b je trochu vykreslen nezávisle na rovnoměrném rozdělení. Formálně,

Probx ~ U [C(G(X)) = 1] - Probx ~ U, b ~ U [C(x.b)=1]  ≥ ε

Vytvořme následující algoritmus C':

1. Vzhledem k tomu, že z = f (x) hádejte bit b 2. Spusťte C na z.b3. IF C (z.b) = 14. výstup b5. JINÉ6. výstup 1-b

Vzhledem k výstupu ƒ algoritmus nejprve hádá bit b tím, že hodí náhodnou minci, tj. Prob [b= 0] = Prob [b= 1] = 0,5. Poté algoritmus (obvod) C běží dál f (x). b a pokud je výsledek 1, pak b je na výstupu, jinak inverzní k b je vrácen.

Pak pravděpodobnost C' hádám B(X) správně je:

Probx ~ U [C'(z)=B(X)] =

Prob [b=B(X) ∧ C(z.b.) = 1] + Prob [b≠B(X) ∧ C(z.b.)=0] =

Prob [b=B(X)] ⋅Prob [C(z.b.)=1 | b=B(X)] + Prob [b≠B(X)] ⋅Prob [C(z.b.)=0 | b≠B(X)] =

1 / 2⋅Prob [C(z.b.)=1 | b=B(X)] + 1 / 2⋅Prob [C(z.b.)=0 | b≠B(X)] =

(1−1 / 2) robProb [C(z.b.)=1 | b=B(X)] + 1 / 2⋅ (1 − Prob [C(z.b.)=1 | b≠B(X)]) =

1/2 + Probz.b ~ G (x) [C(z.b.) = 1] −1 / 2⋅ (Prob [C(z.b.)=1 | b=B(X)] + Prob [C(z.b.)=1 | b≠B(X)]) =

1/2 + Probz.b ~ G (x) [C(z.b.) = 1] - Probz.b ~ U [C(z.b.)=1] ≥ 1/2+ε

To znamená, že obvod C' umí předvídat B(X) s pravděpodobností více než 1/2 + ε, což znamená, že B nemůže být tvrdým predikátem pro ƒ a hypotéza je v rozporu. Q.E.D.

OWP → predikát hard-core

Osnova dokladu je následující:

Pokud ƒ {0,1}n→{0,1}n je jednosměrná permutace, pak také ƒ '{0,1}2n→{0,1}2n, kde ('(X,y) = ƒ (X).y podle definice. Pak B(X,y)=X⋅y je tvrdý predikát pro ƒ ', kde ⋅ je vektor Tečkovaný produkt. Abychom dokázali, že jde skutečně o tvrdé jádro, předpokládejme opak a prokažme rozpor s hypotézou, že ƒ je jednosměrný. Li B není tvrdý predikát, pak existuje obvod C který to předpovídá, takže

Probx, y[C(ƒ (X),y)=X⋅y] ≥ 1/2+ε. Tuto skutečnost lze použít k obnovení X chytrou konstrukcí permutací y že izolovat kousky dovnitř X. Ve skutečnosti za konstantní zlomek X, existuje polynomiální časový algoritmus, který uvádí Ó(1/& epsilon2) kandidáti, kteří zahrnují všechny platné X. Algoritmus tedy může invertovat ƒ (X) v polynomiálním čase pro nezanedbatelný zlomek X, což je v rozporu s hypotézou.

Reference

  • W. Diffie, ME Hellman. „Nové směry v kryptografii.“ Transakce IEEE na teorii informací, IT-22, str. 644–654, 1976.
  • AC Yao. „Teorie a aplikace funkcí padacích dveří.“ 23. IEEE Symposium on Foundations of Computer Science, str. 80–91, 1982.
  • M. Blum a S. Micali „Jak generovat kryptograficky silné sekvence pseudonáhodných bitů.“ SIAM Journal on Computing, v13, s. 850–864, 1984.
  • J. Hastad, R. Impagliazzo, L.A. Levin a M. Luby. „Generátor pseudonáhodnosti z jakékoli jednosměrné funkce.“ SIAM Journal on Computing, v28 n4, str. 1364-1396, 1999.