Здесь мы покажем, что односторонние функции также необходимы

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 является односторонним.

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

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