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



Pdf көрінісі
бет111/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   107   108   109   110   111   112   113   114   ...   249
Криптография Катц

УТВЕРЖДЕНИЕ 4.21 Существует пренебрежимо малая функция negl , за-
ключающаяся в том, что


154
Чтобы доказать данное утверждение мы воспользуемся защитой от атак на 
основе подобранного открытого текста ΠE . Рассмотрим следующего злоумыш-
ленника AE, атакующего ΠE при помощи атаки на основе открытого текста:
Злоумышленник AE :
AE получает входные данные 1n и доступ к Enck(•).
1. Выберем универсальный kM ∈ {0, 1}n.
2. Запускаем A на вводе 1n. Когда A совершает запрос оракулу дешифрования 
на сообщение m, ответим ему следующим образом:
(i) Опрашиваем m у EnckE (•) и получаем c в ответ.
(ii) Вычисляем t ← MackM (c) и возвращаем (c, t) to A.
Когда A совершает запрос оракулу дешифрования на шифротекст (c, t), от-
ветим ему следующим образом: 
• Если (c, t) был ответом на предыдущий запрос оракулу шифрования на со-
общение m, верните m. Иначе, верните ┴.
3. Когда A выводит сообщения (m0, m1), выведите эти же самые сообщения и 
получите шифротекст-испытаниеc в ответ. Вычислите t ← MackM (c) и верните 
(c, t) в качестве шифротекста-испытания для A. Продолжайте отвечать на за-
просы оракула A, как указано выше.
4. Выведите один и тот же бит br , что вывел A.
Обратите внимание, что AE не требует оракула дешифрования, потому что он 
просто предполагает, сто любой запрос дешифрования A , который не был резуль-
татом предыдущего запроса оракулу шифрования является недействительным.
Очевидно, что AE работает в вероятностном полиномиальном времени. Бо-
лее того, the view of A видимость A когда он работает в качестве подпрограммы 
AE распространяется идентично видимости A в эксперименте 
так 
как событие ValidQuery ни разу не случилось. Таким образом, вероятность того, 
что AE добьется успеха, если ValidQuery не случится равняется вероятности 
того, что A добьется успеха, если ValidQuery не случится; то есть
это значит, что
Поскольку ΠE является CPA-защищенным, существует пренебрежимо малая функ-
ция negl такая, что Pr[
= 1] ≤ 1/2 + negl(n). Это доказывает утверждение.


155


Достарыңызбен бөлісу:
1   ...   107   108   109   110   111   112   113   114   ...   249




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

    Басты бет