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.
Достарыңызбен бөлісу: