Введение в современную криптографию
Построение псевдослучайных генераторов
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Псевдослучайные генераторы с минимальным расширением
- ТЕОРЕМА 7.19
- ДОКАЗАТЕЛЬСТВО
| Построение псевдослучайных генераторов
Сначала покажем, как построить псевдослучайные генераторы, которые рас- ширяют свои входные данные на один бит в предположениии, что существует односторонняя перестановка. Затем мы покажем, как расширить это, чтобы по- лучить какой-либо полиномиальный коэффициент расширения. Псевдослучайные генераторы с минимальным расширением Пусть 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, для которой что и требовалось доказать. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|