Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Соединение с потоковыми шифрами.
- Гибридные аргументы.
| Соединим все это вместе. Пусть f будет односторонней перестановкой. Используя
псевдослучайный генератор с коэффициентом расширения n + 1 из теоремы 7.19, и увеличивая коэффициент расширения до n + A, используя подход из доказательства теоремы 7.20, получим следующий псевдослучайный генератор ttˆ: ttˆ(s) = f (A)(s) || hc(f (A−1)(s)) || • • • || hc(s), где f (i)(s) относится к i-кратной итерации f . Обратите внимание, что ttˆ ис- пользует l оценок f и генерирует один псевдослучайный бит на одну оценку, 289 используя трудный предикат hc. Соединение с потоковыми шифрами. Напомним из раздела 3.3.1, что по- токовый шифр (без IV ) определяется с помощью алгоритмов (Init, GetBits), где Init берет начальное число s ∈ {0, 1}n и возвращает исходное состояние st, а GetBits использует в качестве входных данных текущее состояние st и выво- дит бит σ, а также обновляет состояние str. Конструкция ttˆиз предыдущего доказательства вполне вписывается в эту парадигму: возьмем Init в качестве тривиального алгоритма, который выводит st = s, и определим GetBits(st), чтобы вычислить tt(st), проанализируем результат как str»σ с |str| = n, и выведем бит σ и обновленное состояние str. (Если мы используем этот потоковый шифр, чтобы генерировать p(n) выходные биты, начиная с начального числа s, то получим точно конечные p(n) битов ttˆ(s) в обратном порядке). Предшествующее доказа- тельство показывает, что это дает псевдослучайный генератор. Гибридные аргументы. Гибридный аргумент представляет собой базовый инструмент для доказательства неразличимости, когда базовый примитив (или несколько различных примитивов) применяется несколько раз. Отчасти произ- вольно, метод работает при определении ряда промежуточных «гибридных рас- пределений», образуя связку между двумя «крайними распределениями», для которых нам требуется доказать неразличимость. (В приведенном выше доказа- тельстве, эти крайние распределения соответствуют выходным данным ttˆ и слу- чайной строке). Чтобы применить метод доказательства, должны выполняться три условия. Во-первых, крайние распределения должны соответствовать исход- ным случаям, представляющим интерес. (В приведенном выше доказательстве, Hn0 было равно распределению, индуцированному ttˆ, тогда как было равно- мерным распределением). Во-вторых, должно быть возможно транслировать воз- можность различения последовательных гибридных распределений в нарушение некоего основного предположения. (Выше мы показали, что отличие Hni от Hni+1 было эквивалентно отличию выхода tt от случайного). И наконец, количество ги- бридных распределений должно быть полиномом. См. также теорему 7.32. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|