Введение в современную криптографию
Псевдослучайные генераторы из односторонних перестановок
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Псевдослучайные генераторы с произвольным расширением.
- СЛЕДСТВИЕ 7.10
- СЛЕДСТВИЕ 7.11
| Псевдослучайные генераторы из односторонних перестановок. Следующий
шаг должен показать, как трудный предикат односторонней перестановки может быть использован для построения псевдослучайного генератора. (Известно, что труд- ного предиката односторонней функции достаточно, но доказательство этого чрезвы- чайно сложное, и выходит за рамки данной книги). В частности, мы покажем: ТЕОРЕМА 7.6 Пусть f- односторонняя перестановка и hc - трудный пре- дикат f . Тогда, tt(s) f (s) « hc(s) является псевдослучайным генератором с коэффициентом расширения A(n) = n + 1. Интуитивно догадываясь, для чего tt, как определено в теореме, образует псевдослучайный генератор, сначала заметим, что начальные n битов выхода tt(s) (т.е., битов f (s)) на самом деле распределены равномерно, если s распреде- лено равномерно в силу того, что f является перестановкой. Далее, тот факт, что hc является трудным предикатом f означает, что hc(s) «выглядит случайной», т.е., является псевдо- случайной, даже с учетом f (s) (предполагая еще раз, что s является равномерным). Сопоставляя эти наблюдения, мы видим, что полный выход tt является псевдослучайным. Псевдослучайные генераторы с произвольным расширением. Суще- ствование псевдослучайного генератора, который распространяет свое началь- ное число посредством даже единственного бита (как мы только что видели), уже весьма нетривиально. Но для приложений (например, для эффективного шифрования больших сообщений, как в разделе 3.3) нам требуется псевдос- лучайный генератор с гораздо большим расширением. К счастью, мы можем получить любой коэффициент полиномиального расширения, какой захотим: ТЕОРЕМА 7.7 Если существует псевдослучайный генератор с коэффициен- том расширения A(n)=n+1, то для любого многочлена poly существует псев- дослучайный генератор с коэффициентом расширения poly(n). Мы пришли к выводу, что псевдослучайные генераторы с произвольным (полиноми- альным) расширением могут быть построены из любой односторонней перестановки. Псевдослучайные функции/перестановки из псевдослучайных генераторов. Псевдослучайные генераторы, достаточные для построения безопасных с точки зрения EAV (расширенной проверки приложения) схем шифрования с закрытым ключом. Для достижения безопасного шифрования с закрытым ключом, с точки зрения атаки выбранного открытого текста (CPA) (не говоря уже о кодах аутенти- фикации сообщений), тем не менее, мы опираемся на псевдослучайные функции. Следующий результат показывает, что второе можно построить из первого: 274 ТЕОРЕМА 7.8 Если существует псевдослучайный генератор с коэффициен- том расширения A(n) = 2n, то существует псевдослучайная функция. На самом деле, мы можем сделать еще больше: ТЕОРЕМА 7.9 Если существует псевдослучайная функция, то существует и строгая псевдослучайная перестановка. Комбинируя все указанные выше теоремы, а также результаты глав 3 и 4, име- ем следующие выводы: СЛЕДСТВИЕ 7.10 Если предположить существование односторонних пере- становок, то существуют псевдослучайные генераторы с любым полиномиаль- ным коэффициентом расширения, псевдослучайные функции и строгие псев- дослучайные перестановки. СЛЕДСТВИЕ 7.11 Если предположить существование односторонних пе- рестановок, то существуют схемы шифрования безопасные, с точки зрения атаки, на основе подобранного шифрованного текста и аутентификационные коды безопасных сообщений. Как было отмечено ранее, все эти результаты можно получить только на осно- ве существования односторонних функций. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|