Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| Общий случай. Та же идея, что и выше, может быть итеративно примене-
на, чтобы генерировать столько псевдослучайных битов, сколько необходимо. Говоря формально, мы хотим построить псевдослучайный генератор ttˆ с коэф- фициентом расширения n + p(n), для некого полинома p. На входе s ∈{0, 1}n алгоритм ttˆ делает (см. рис. 7.1): 1. Зададим t0 := s. Для i = 1, . . . , p(n) выполним: (a) Пусть si−1 будут первые n битов из ti−1, и пусть σi−1 обозначает осталь- ные i − 1 биты. (Если i = 1, s0 = t0 и σ0 является пустой строкой.) (b) Зададим ti := tt(sr)||σi−1. 2. Выведем tp(n). Покажем, что ttˆ – псевдослучайный генератор. Это доказательство использу- ет общепринятую технику, известную как гибридный аргумент. (На самом деле, даже в случае p(n) = 2, приведенном выше, использовался гибридный аргумент). Основное отличие от предыдущего доказательства – техническое. Ранее мы мог- ли бы определить и четко работать с тремя последовательностями распределений {H n 0}, {H n 1}, and {H n 2}. В данном случае это невозможно, поскольку количе- ство рассматриваемых распределений увеличивается с ростом n. 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ˆ – псевдослучайный генератор. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|