Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| Дистинктор 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), чем мы завершаем доказательство. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|