Sprawdzanie bezpieczeństwa generatora liczb pseudolosowych Nisan-Wigderson

13

Niech częściowe -design i być funkcją logiczną. Generator Nisan- jest zdefiniowany w następujący sposób:S={Si}1in(m,k)f:{0,1}m{0,1}Gf:{0,1}l{0,1}n

Gf(x)=(f(x|S1),,f(x|Sn))

Aby obliczyć ty bit , bierzemy bity z indeksami w a następnie stosujemy do nich .iGfxSif

Załóżmy, że jest twarde dla obwodów o rozmiarze gdzie jest stałą. Jak możemy udowodnić, że jest bezpiecznym generatorem liczb pseudolosowych?f1ncnccGf(nc2,2nc)

Definicje:

Częściowa -design to zbiór podzbiorów tak, że(m,k)S1,,Sn[l]={1,,l}

  • dla wszystkich : orazi|Si|=m
  • dla wszystkich : .ij|SiSj|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ϵssfϵ

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{0,1}n(s,ϵ)sGfϵ

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

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
3
i niech rozpocznie się bitwa CS.SE kontra crypto.SE! (:
Ran G.
1
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

Odpowiedzi:

1

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

Yuval Filmus
źródło