Sprawdzanie bezpieczeństwa generatora liczb pseudolosowych Nisan-Wigderson

Niech częściowe -design i być funkcją logiczną. Generator Nisan- jest zdefiniowany w następujący sposób: $\cal{S}=\{S_i\}_{1\leq i\leq n}$ $(m,k)$ $f: \{0,1\}^m \to \{0,1\}$ $G_f: \{0,1\}^l \to \{0,1\}^n$

G_{f} (x) = (f (x |_{S_{1}}), \dots, f (x |_{S_{n}}))

$G_f(x) = (f(x|_{S_1}) , \ldots, f(x|_{S_n}) )$

Aby obliczyć ty bit , bierzemy bity z indeksami w a następnie stosujemy do nich . $i$ $G_f$ $x$ $S_i$ $f$

Załóżmy, że jest twarde dla obwodów o rozmiarze gdzie jest stałą. Jak możemy udowodnić, że jest bezpiecznym generatorem liczb pseudolosowych? $f$ $\frac{1}{n^c}$ $n^c$ $c$ $G_f$ $(\frac{n^c}{2}, \frac{2}{n^c})$

Definicje:

Częściowa -design to zbiór podzbiorów tak, że $(m,k)$ $S_1, \ldots, S_n \subseteq [l] = \{1, \ldots, l\}$

dla wszystkich : oraz $i$ $|S_i|=m$
dla wszystkich : . $i \neq j$ $|S_i \cap S_j| \leq k$

Funkcja jest twarda dla obwodów o rozmiarze iff żaden obwód o rozmiarze może przewidzieć z prawdopodobieństwem lepiej niż rzut monetą. $f$ $\epsilon$ $s$ $s$ $f$ $\epsilon$

Funkcja jest -bezpiecznym generatorem liczb pseudolosowych, jeśli żaden obwód wielkości potrafi rozróżnić liczby losowej oraz liczba wygenerowana przez z prawdopodobieństwem lepszym niż . $G:\{0,1\}^l \to \{0,1\}^n$ $(s, \epsilon)$ $s$ $G_f$ $\epsilon$

Używamy na łańcuch składający się bitów „S z indeksami w . $x|_A$ $x$ $A$

cryptography pseudo-random-generators

— Kaveh
źródło

ps: to nie jest tak naprawdę moja praca domowa, ale traktuj ją tak, jakbyś traktował pytanie o pracę domową, czasami otrzymuje się ją od studentów biorących udział w kursie kryptografii.

— Kaveh

i niech rozpocznie się bitwa CS.SE kontra crypto.SE! (:

— Ran G.

google daje całkiem niezłe wyniki: 1 , 2

— Ran G.

To nie jest dobra odpowiedź - to tylko wyszukiwarka Google. Może chcesz z tego udzielić odpowiedzi?

— Ran G.

@RanG., Dobra uwaga.

— Kaveh

Oto odpowiedź Ran G. wspomniana w komentarzach: Google daje całkiem niezłe wyniki: 1 , 2 .

— Yuval Filmus
źródło