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), чем мы завершаем доказательство.
Достарыңызбен бөлісу: