274
ТЕОРЕМА 7.8 Если существует псевдослучайный генератор с коэффициен-
том расширения A(n) = 2n, то существует псевдослучайная функция.
На
самом деле, мы можем сделать еще больше:
ТЕОРЕМА 7.9 Если существует псевдослучайная функция, то существует
и строгая псевдослучайная перестановка.
Комбинируя все указанные выше теоремы, а также результаты глав 3 и 4, име-
ем следующие выводы:
СЛЕДСТВИЕ 7.10 Если предположить существование односторонних пере-
становок, то существуют псевдослучайные генераторы с любым полиномиаль-
ным коэффициентом расширения, псевдослучайные функции и строгие псев-
дослучайные перестановки.
СЛЕДСТВИЕ 7.11 Если предположить существование односторонних пе-
рестановок, то существуют схемы шифрования безопасные,
с точки зрения
атаки, на основе подобранного шифрованного текста и аутентификационные
коды безопасных сообщений.
Как было отмечено ранее, все эти результаты можно получить только на осно-
ве существования односторонних функций.
Достарыңызбен бөлісу: