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


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



Pdf көрінісі
бет202/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   198   199   200   201   202   203   204   205   ...   249
Криптография Катц

Псевдослучайные генераторы из односторонних перестановок. Следующий 
шаг должен показать, как трудный предикат односторонней перестановки может 
быть использован для построения псевдослучайного генератора. (Известно, что труд-
ного предиката односторонней функции достаточно, но доказательство этого чрезвы-
чайно сложное, и выходит за рамки данной книги). В частности, мы покажем:
ТЕОРЕМА 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 Если предположить существование односторонних пе-
рестановок, то существуют схемы шифрования безопасные, с точки зрения 
атаки, на основе подобранного шифрованного текста и аутентификационные 
коды безопасных сообщений.
Как было отмечено ранее, все эти результаты можно получить только на осно-
ве существования односторонних функций.


Достарыңызбен бөлісу:
1   ...   198   199   200   201   202   203   204   205   ...   249




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

    Басты бет