Введение в современную криптографию


Построение псевдослучайных генераторов



Pdf көрінісі
бет208/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   204   205   206   207   208   209   210   211   ...   249
Криптография Катц

Построение псевдослучайных генераторов
Сначала покажем, как построить псевдослучайные генераторы, которые рас-
ширяют свои входные данные на один бит в предположениии, что существует 
односторонняя перестановка. Затем мы покажем, как расширить это, чтобы по-
лучить какой-либо полиномиальный коэффициент расширения.
Псевдослучайные генераторы с минимальным расширением
Пусть f – односторонняя перестанока с трудным предикатом hc. Это означа-
ет, что hc(s) «выглядит случайным» с учетом f (s), когда s является равномер-
ным. Кроме того, так как f является перестановкой, то сама f (s) распределена 
равномерно. (Применение перестановки к равномерно распределенному значе-
нию, дает равномерно распределенное значение). Таким образом, если s явля-
ется равномерной n-битной строкой, то (n +1)-битная строка f (s)||hc(s) состоит 
из равномерной n-битной строки плюс дополнительный бит, который выглядит 
равномерным, даже обусловленный начальными n битами; другими словами, (n 
+ 1)-битная строка является псевдослучайной. Таким образом, алгоритм tt, опре-
деляемый tt(s) = f (s)||hc(s) представляет собой псевдослучайный генератор.
ТЕОРЕМА 7.19 Пусть f – односторонняя перестановка с трудным преди-
катом hc. Тогда алгоритм tt, определяемый tt(s) = f (s)||hc(s), является псевдос-
лучайным генератором с коэффициентом расширения A(n) = n + 1.
ДОКАЗАТЕЛЬСТВО Пусть D – вероятностный полиномиально-временной 
алгоритм. Докажем, что существует пренебрежимо малая функция negl, такая что


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, для которой
что и требовалось доказать.


Достарыңызбен бөлісу:
1   ...   204   205   206   207   208   209   210   211   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет