РИС. 7.2: Построение псевдослучайной функции. ТЕОРЕМА 7.22

292
рая вероятность – более равномерный выбор s1, . . . , st(n)∈ {0, 1}n.
Доказательство происходит с помощью гибридного аргумента. Зафиксируем 
полином t и ppt алгоритм A, и рассмотрим следующий алгоритм Ar:
Отличительный признак Ar:
Ar задан в качестве входной строки w ∈{0, 1}2n.
1. Выберем равномерное j ∈ {1, . . . , t(n)}.
2. Выберем равномерные, независимые значения r1, . . . , rj−1 ∈{0, 1} и sj+1, . 
. . , st(n) ∈ {0, 1}n.
3. Output A .r1|| • • • ||rj−1|w |tt(sj+1)| • • • |tt(st(n))..
Для любых n и 0 ≤ i ≤ t(n), пусть tti обозначает распределение строк длиной 2n 
• t(n), в которых первые i «блоков» длиной 2n являются равномерными и остальные 
t(n) − i блоки являются псевдослучайными. Обратите внимание, что ttt(n) соответ-
ствует распределению, в котором все блоки t(n) равномерные, тогда как tt0 соответ-
ствует распределению, в котором все t(n) блоки псевдослучайные. То есть,
Пусть Ar выбирает j = j*. Если вход w – равномерная 2n-битная строка, то A
запускается на входе в соответствии с ttnj*. Если, с другой стороны, w = tt(s) для 
равномерного s, то A действует на входе, распределенном в соответствии с ttj
−1. Это означает, что
Следовательно,
Поскольку tt представляет собой псевдослучайный генератор и Ar работает 
в полиномиальном времени, мы знаем, что левая сторона выражения (7.12) 
должна быть пренебрежимо малой; поскольку t(n) – полином, это означает, что 

293
левая часть выражения (7.11) тоже пренебрежимо мала.
Обращаясь к сути доказательства, покажем, что F, как и в конструкции 7.21, яв-
ляется псевдослучайной функцией. Пусть D произвольный ppt отличительный 
признак, который задан 1n в качестве входных данных. Покажем, что D не может 
найти различий между случаем, когда задан прогнозирующий доступ к функции, 
которая равна Fk для равномерного k, или функцией, выбранной равномерно из 
Funcn. (См. раздел 3.5.1.) Для этого мы используем другой гибридный аргумент. 
Определим последовательность распределений, по значениям на концевых эле-
ментах всего двоичного дерева, высоты n. При соединении каждого концевого 
элемента со строкой длиной n, как и в конструкции 7.21, можно так же увидеть их 
в виде распределений по функциям, отображающим n-битные входы на n-битные 
выходы. Для любого n и 0 ≤ i ≤ n, пусть Hi – следующее распределение по зна-
чениям на концевых элементах двоичного дерева высотой n: сначала выберем 
значения для узлов на уровне i , независимо и равномерно из {0, 1}n. Тогда для 
каждого узла на уровне i или ниже со значением k, его левому дочернему эле-
менту задано значение tt0(k), а его правому дочернему элементу задано значение 
tt1(k). Обратите внимание, что Hn соответствует распределению, в котором все 
значения на концевых элементах выбираются равномерно и независимо, и, таким 
образом, соответствуют выбору равномерной функции из Funcn, тогда как H0 со-
ответствует выбору равномерного ключа k в конструкции 7.21, поскольку в этом 
случае только корень (на уровне 0) выбирается равномерно. То есть,
Завершая доказательство, покажем, что выражение (7.13) пренебрежимо мало. 
Пусть t = t(n) – полиномиальная верхняя граница числа запросов D, сделан-
ных по их прогнозу на входе 1n. Определим отличительный признак A, который 
пытается отличить t(n) равномерные 2n-битные строки от t(n) псевдослучайных 
строк, следующим образом:

жүктеу/скачать 6.4 Mb.

Достарыңызбен бөлісу: