287
РИС. 7.1: Увеличение расширения псевдослучайного генератора.
Для любого n и 0 ≤ j ≤ p(n), пусть Hj будет распределением строк длиной n
+p(n), определенных следующим образом: выберем равномерное tj ∈ {0, 1}n+j,
затем запустим ttˆ , начиная с итерации j + 1 и выведем tp(n). (Когда j = p(n), это
означает, что мы просто выбираем равномерное tp(n) ∈ {0, 1}n+p(n) и выводим
его.) Ключевое наблюдение состоит в том, что H0
соответствует выводимому
ttˆ(s) для равномерного s∈{0, 1}n, тогда как соответствует выводимой равно-
мерной (n + p(n))-битной строке. Зафиксируем любой полиномиально-времен-
ной отличительный признак D, это
означает
.
Мы доказали, что указанная
выше функция пренебрежимо мала, следова-
тельно ttˆ является псевдослучайным генератором.
Зафиксируем D, как указано выше, и рассмотрим отличительный признак Dr,
который делает следующее, когда в качестве входных данных задана строка w
∈
{0, 1}n+1:
1. Выберем равномерное j ∈ {1, . . . , p(n)}.
2. Выберем равномерное σr ∈ {0, 1}j−1. (Когда j = 1, тогда σr– пустая строка).
3. Зададим tj := w||σr. Затем запустим ttˆ, начиная с итерации j + 1, чтобы вы-
числить tp(n) ∈ {0, 1}n+p(n). Выведем D(tp(n)).
Очевидно, что Dr действует в течение полиномиального времени. Анализи-
руя поведение Dr, отметим, что оно является более сложным, чем ранее, хотя
основные идеи те же. Зафиксируем n и, скажем, что Dr выбирает j = j*.
Если w
является равномерным, то tj* является равномерным и, таким образом, распре-
деление по t t p(n) точно такое же, как и распределение Hj. То есть,
Поскольку каждое значение для j выбирается с равной вероятностью,
288
С другой стороны, скажем Dr выбирает j = j* и w = tt(s)
для равномерного s
∈
{0, 1}n. Определив tj* −1= s||σr, мы видим, что tj* −1 является равномерным
и, таким образом, эксперимент с участием Dr эквивалентен запуску ttˆ от ите-
рации j*, чтобы вычислить tp(n). То есть распределение по t
= tp(n) теперь
точно такое же, как Hnj* −1. То есть,
Следовательно,
Теперь мы можем проанализировать, насколько хорошо Dr отличает выход-
ные данные tt от случайных:
.
опираясь на выражения (7.8) и (7.9) для первого равенства. (Второе равенство
выполняется, поскольку в каждую сумму входят одни и те же элементы, за ис-
ключением первого элемента левой суммы и последнего элемента правой сум-
мы). Поскольку tt является псевдослучайным генератором, то элемент с левой
стороны равенства (7.10) – пренебрежимо мал; поскольку p является полино-
мом, это означает, что равенство (7.7) пренебрежимо мало, завершая доказа-
тельство, что ttˆ – псевдослучайный генератор.
Достарыңызбен бөлісу: