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) псевдослучайных
строк, следующим образом:
Достарыңызбен бөлісу: