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



Pdf көрінісі
бет211/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   207   208   209   210   211   212   213   214   ...   249
Криптография Катц

Соединим все это вместе. Пусть 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.


Достарыңызбен бөлісу:
1   ...   207   208   209   210   211   212   213   214   ...   249




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

    Басты бет