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



Pdf көрінісі
бет71/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   67   68   69   70   71   72   73   74   ...   249
Криптография Катц

Дистинктор D:
D получает вход 1n и доступ к оракулу O:{0, 1}n→ 0, 1}n.
1. Запустить A(1n). Когда A посылает запрос своему шифровальному оракулу 
о сообщении m∈{0, 1}n, ответить на запрос следующим образом:
(a) Выбрать равномерную r∈{0, 1}n.
(b) Сделать запрос O(r) и получить ответ y.
(c) Вернуть A шифртекст (r, y⊕m) .
2. Когда A выдает сообщения m0, m1∈{0, 1}n, выбрать единообразный бит 
b∈{0, 1} и затем:
(a) Выбрать равномерную r∈{0, 1}n.
(b) Сделать запрос O(r) и получить ответ y.
(c) Вернуть A анализируемый шифртекст (r, y⊕mb) .
3. Продолжить таким же образом отвечать на запросы A к шифровальному ора-
кулу, пока A не выведет бит br. Вывести 1, если br = b, и 0 в противном случае.
D работает в полиномиальном времени, так как A работает в полиномиаль-
ном времени. Основные моменты следующие:
1. Если оракул дистинктора D является псевдослучайной функцией, то когда 
A работает как подпрограмма D , обзор A распределен так же, как и при экспе-
рименте 
. Это происходит потому, что в этом случае ключ k выбран 
равномерно и произвольно и, таким образом, каждое шифрование происходит 
путем выбора равномерной r, вычисляя y := Fk (r), и устанавливая шифртексти 
равный (r, y⊕m), так же как в Конструкции 3.30. Таким образом,
где мы подчеркиваем, что k выбирается равномерно с левой стороны.
2. Если оракул дистинктора D является случайной функцией, то когда A работает как 
подпрограмма D , обзор A распределен так же, как и при эксперименте 
. Это можно рассматривать так же, как приведено выше, с единственной разницей 
в том, что вместо Fk используется равномерная функция f∈Funcn . Таким образом,
где f выбирается равномерно из Funcn с левой стороны.
Следуя из предположения, что F —псевдослучайна функция (и так как D явля-


98
ется эффективным), существует пренебрежимо малая функция negl , для которой
.
Объединение вышеприведенных Уравнений (3.9) и (3.10) дает Уравнение (3.8).
Для следующей части доказательства, продемострируем, что
(Напомним, что q(n) — это предельное значение числа шифровальных запросов, 
сделанных A. Это утверждение действует, даже если мы не налагаем никаких вычис-
лительных ограничений на A.) Чтобы удостовериться, что Уравнение (3.11) действует, 
можно пронаблюдать, что, каждый раз, когда сообщение m шифруется в
(либо шифровальным оракулом, либо при вычислении анализируемого шифртекста), 
выбирается равномерная r∈{0, 1}n и шифртекст становится равным (r, f (r)⊕m). Пусть
r* обозначает произвольную последовательность, используемую при генерации анали-
зируемого шифртекста (r* , f (r*) ⊕mb). Существуют две возможности:
1. Значение r* никогда не используется при ответе на запросы A к шифровальному 
оракулу: В этом случае A ничего не узнает о f (r*) из взаимодействия с шифровальным 
оракулом (так как f является действительно случайной функцией). Это означает, что A
считает, что значение f (r*), объединенное с mb операцией исключающего ИЛИ, равно-
мерно распределено и независимо от остальной части эксперимента, так что вероят-
ность того, что A выдаст br = b в этом случае равна 1/2 (как в случае шифра Вермана).
2. Значение r* используется при ответе на хотя бы один из запросов A к шиф-
ровальному оракулу: В этом случае, A может легко определить, был ли за-
шифрован m0 или m1. Это происходит потому, что, если шифровальный оракул 
когда-либо возвращает шифртекст (r*, s) в ответ на запрос зашифровать со-
общение m, то противник узнает, что f (r*) = s ⊕m.
Однако, так как A делает не больше q(n) запросов к шифровальному оракулу 
(и, таким образом, максимальное число значений r , используемых при ответе на 
запросы A к шифровальному оракулу, равно q(n) ), и так как r* выбирается равно-
мерно из {0, 1}n, то максимальная вероятность этого события равна q(n)/2n.
Пусть Repeat обозначает событие, при котором r* используется шифровальным ора-
кулом при ответе на хотя бы один из запросов A. Как только что было объяснено, мак-
симальная вероятность Repeat равна q(n)/2n, а вероятность того, что успешно взломает
в случае, если Repeat не имеет место, равна 1/2. Таким образом:


99
Объединив вышеприведенное уравнение с Уравнением (3.8), мы ви-
дим, что существует пренебрежимо малая функция negl , такая что
Поскольку q полиномиально, q(n)/2n 
тоже полиномиально. Кроме того, сумма двух пренебрежимо малых функций 
тоже пренебрежимо мала, так что существует пренебрежимо малая функция neglr 
, такая что Pr[
= 1] ≤ 1 + neglr(n), чем мы завершаем доказательство.


Достарыңызбен бөлісу:
1   ...   67   68   69   70   71   72   73   74   ...   249




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

    Басты бет