Введение в современную криптографию



Pdf көрінісі
бет210/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   206   207   208   209   210   211   212   213   ...   249
Криптография Катц

Общий случай. Та же идея, что и выше, может быть итеративно примене-
на, чтобы генерировать столько псевдослучайных битов, сколько необходимо. 
Говоря формально, мы хотим построить псевдослучайный генератор 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ˆ – псевдослучайный генератор.


Достарыңызбен бөлісу:
1   ...   206   207   208   209   210   211   212   213   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет