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). Это доказывает утверждение.