Доказательство безопасности генератора псевдослучайных чисел Нисана-Вигдерсона

13

Пусть 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))

Чтобы вычислить i й бит Gf мы берем биты x с индексами в Si и затем применяем f к ним.

Предположим, что является -твердым для цепей размером где - константа. Как мы можем доказать, что является безопасным генератором псевдослучайных чисел?1f1ncnccGf(nc2,2nc)

Определения:

Частичный -дизайн представляет собой набор подмножеств таких, что(m,k)S1,,Sn[l]={1,,l}

  • для всех : иi|Si|=m
  • для всех : .ij|SiSj|k

Функция является -hard для цепей размером если никакая схема размера может предсказать с вероятностью лучше, чем бросок монеты.s s s f ϵfϵssfϵ

Функция является ( s , ϵ ) -безопасным генератором псевдослучайных чисел, если только схема с размером s не может различить случайное число и число, сгенерированное G f с помощью вероятность лучше, чем ϵ .G:{0,1}l{0,1}n(s,ϵ)sGfϵ

Мы используем Для строки , состоящей из й бит «ы с индексами в A .x|AxA

Кава
источник
PS: на самом деле это не моя домашняя работа, но, пожалуйста, относитесь к ней так же, как к домашней задаче, иногда ее дают студентам, изучающим курс криптографии.
Каве
3
и пусть битва CS.SE против crypto.SE начнется! (:
Ран Г.
1
Google дает довольно хорошие результаты: 1 , 2
Ран Г.
Это не очень хороший ответ - это только поиск в Google. Может быть, вы хотите сделать ответ из этого?
Ран Г.
@RanG., Хорошая мысль.
Каве

Ответы:

1

Вот ответ Ран Г., упомянутый в комментариях: Google дает довольно хорошие результаты: 1 , 2 .

Юваль Фильмус
источник