283
Подобный аргумент показывает, что существует пренебрежимо малая функ-
ция neglr ,
для которой
что завершает доказательство.
Сначала
отметим
используя тот факт, что f является перестановкой для второго равенства, и того,
что равномерный бит rr равен hc(s) с вероятностью точно 1/2 для третьего ра-
венства. Поскольку
(при определении tt), это
означает, что равенство (7.3) эквивалентно
Рассмотрим следующий алгоритм A, который задает в качестве входного зна-
чение y = f (s) и пытается предсказать значение hc(s):
1. Выберем равномерное rr ∈ {0, 1}.
2. Запустим D(y||rr). Если D выводит 0, выведем rr; иначе выведем r¯r . Очевидно,
что A работает в течение полиномиального времени. По
определению A, имеем
284
Поскольку hc является трудным предикатом f , то отсюда следует, что суще-
ствует пренебрежимо малая функция negl, для которой
что и требовалось доказать.
Достарыңызбен бөлісу: