299
ронних функций:
ПРЕДПОЛОЖЕНИЕ 7.28 Если существует псевдослучайный генератор,
то существует также и односторонняя функция.
ДОКАЗАТЕЛЬСТВО Пусть tt – псевдослучайный
генератор с коэффици-
ентом расширения A(n) = 2n. (Из теоремы 7.20, мы знаем, что существование
псевдослучайного генератора предполагает существование псевдослучайного
генератора с коэффициентом расширения). Покажем, что сам tt является односто-
ронним. Эффективная вычисляемость проста (поскольку tt можно вычислить в
течение полиномиального времени). Покажем, что способность инвертировать tt
может быть преобразована в способность отличать выход tt от равномерного. Ин-
туитивно понятно, что это справедливо, поскольку способность инвертировать tt
подразумевает способность
найти начальное число, используемое генератором.
Пусть A – произвольный вероятностный полиномиально-временной алго-
ритм. Покажем, что Pr[InvertA,G(n) = 1] пренебрежимо мало (см.
определение
7.1). Чтобы убедиться в этом, рассмотрим следующий ppt отличительный при-
знак D: на входе строка w ∈ {0, 1}2n, запустим A(w), чтобы получить выход s.
Если tt(s) = w, то выход 1; иначе, выход 0.
Проанализируем поведение D. Сначала рассмотрим вероятность того, что D
выводит 1, когда его входная строка w является равномерной. Поскольку суще-
ствует не более 2n значений в диапазоне tt (а именно, значения {tt(s)}s∈{0,1}n ),
то вероятность того, что w находится в диапазоне tt составляет не более 2n/22n =
2−n. Если w не находится в диапазоне tt, то для A невозможно вычислить инвер-
сию w и,
таким образом, невозможно для D вывести 1.
Приходим к выводу, что
С другой стороны, если w = tt(s) для начального числа s ∈ {0, 1}n выбраны равномер-
но и случайно, то по определению, A вычисляет правильную инверсию (и, таким об-
разом, D выводит 1) с вероятностью точно равной Pr[InvertA,G(n) = 1].
Таким образом,
Поскольку tt представляет собой псевдослучайный генератор, то указанное
выше должно быть пренебрежимо малым. Поскольку 2−n пренебрежимо мало,
то это предполагает, что Pr[Invert A,G (n) = 1] также пренебрежимо мало и, та-
ким образом, tt является односторонним.
Достарыңызбен бөлісу: