152
A отправил новый шифротекст (c, t) своему оракулу дешифрования, который
действительный, то есть для которого VrfykM (c, t) = 1. Мы доказываем:
УТВЕРЖДЕНИЕ 4.20 Pr[ValidQuery] является пренебрежимо малым.
ДОКАЗАТЕЛЬСТВО Интуитивно, это благодаря тому факту, что, если
ValidQuery слечается, тогда злоумышленник подделывает новую действителную
пару (c, t) в эксперименте Mac-sforge.
Строго говоря, пусть q(•) будет полиномиаль-
ной верней границей количества запрсов оракулу дешифрования, выполненных A,
и рассмотрим следующего злоумышленника AM, атакующего код аутентификации
сообщений ΠM (то есть запущенный в эксперименте Mac-sforgeAM.ПМ(n)):
Злоумышленник AM :
AM получает входные данные 1n и имеет доступ к оракулу MAC MackM(•).
1. Выбираем универсальный kE ∈{0, 1}n и i ∈ {1, . . . , q(n)}.
2. Запускаем A на вводе 1n. Когда A совершает запрос оракулу дешифрования
на сообщение m, ответим ему следующим образом:
(i) Вычислите c ← EnckE (m).
(ii) Опросите c оракула MAC и получите t в ответ. Верните (c, t) к A.
Шифротекст-испытание приготовлен точно таким же образом (с универсаль-
ным битом b ∈ {0, 1} , подобранным для выбора сообщения mb , которое ста-
новится зашифрованным).
Когда A совершает запрос оракулу дешифрования касательно шифротекста
(c, t), ответим ему следующим образом: Если это запрос i оракулу дешифрова-
ния, выведите (c, t). Иначе:
(i) Если (c, t) был ответом на предыдущий запрос оракулу шифрования каса-
тельно
сообщения m, верните m.
(ii) Иначе, верните ┴.
По сути, AM «гадает», что запрос i оракулу дешифрования A будет новым, дей-
ствующим запросом, который выполняет A . В том случае, AM выводит действи-
тельную подделку сообщения c, которое он никогда ранее не передавал своему
собственному оракулу MAC. Очевидно, что AM работает в течение вероятност-
ного полиномиального времени. Теперь мы проанализируем вероятность того,
что AM выполнил хорошую подделку. Важно то, что видимость A , когда он
работает в качестве подпрограммы AM распространяется идентично виду A в
эксперименте
, пока событие ValidQuery не случится. Чтобы в этом
убедиться, обратите внимание, что запрос A оракулу шифрования (равно как и
вычисление шифротекста-испытания) идеально симулируется AM . Что касается
запроса A оракулу дешифрования, пока не случится ValidQuery, все это останется
свойством симуляции. В случае (i) - это очевидно. Что касается случая (ii), если
153
шифротекст (c, t) , передаваемый оракулу дешифрования, новый, тогда, пока не
случился ValidQuery , правильный ответ на запрос оракулу шифрования будет
действительно┴. (Обратите внимание, что случай (i) как раз тот случай, когда (c,
t) не новый, а случай (ii) как раз тот случай когда (c, t) новый.) Вспомним, что A не
разрешается передавать шифротекст-испытание оракулу дешифрования.
Потому что видимость A когда он работает в качестве подпрограммы AM рас-
пространяется идентично видимости A в эксперименте PrivKcca t (n), пока не
случится событие ValidQuery, вероятность события ValidQuery в эксперименте
Mac-forge идентичная вероятности события в эксперименте
Если AM правильно угадает первый индекс i , когда случится ValidQuery, тогда AM
выведет (c, t), для которого VrfykM (c, t) = 1 (поскольку (c, t) является действитель-
ным), и которому никогда не был дан тег t в ответ на запрос MackM (c) (поскольку( c, t)
является новым). В этом случае AM достигнет успеха в эксперименте Mac-sforge (n).
Вероятность того, что AM угадает i правильно - 1/q(n).
Таким образом,
Pr[Mac-sforge AMΠM (n) = 1] ≥ Pr[ValidQuery]/q(n).
Поскольку ΠM является строго защищенным MAC, а q является полиномиальным,
мы в заключении скажем, что Pr[ValidQuery] является незначительным .Мы использу-
ем Утверждение 4.20, чтобы доказатеь безопасность Πr. Более легкий пример должен
доказать, что Πr не поддается подделке. Это вытекает прямо из утверждения, и так
мы только что представили скорее неформальное обоснование, чем формальное дока-
зательство. Очевидно, что злоумышленник Ar в эксперименте на шифрование, которое
не поддается подделке, является ограниченной версией злоумышленника в экспери-
менте на подобранный шифротекст (в первом злоумышленник имеет только доступ к
оракулу шифрования). Когда Ar выводит шифротекст (c, t) в конце своего эксперимента,
он «добивается успеха, только, если (c, t) действительный и новый. Но предыдущее ут-
верждение
четко показывает, что вероятность такого события пренебрежимо мала.
Совсем немного сложнее доказать, что Πr является защищенным с точки зре-
ния атаки на основе подобранного шифрованного текста Пусть A снова будет
вероятностным полиномиально-временным злоумышленником, атакующим Πr
атакой на сонове подобранного шифротекста. Мы имеем
Pr[
=1]A≤Pr[ValidQuery]+ Pr[
= 1^ alidQuery].(4.8)
Мы уже показали, что Pr[ValidQuery] является пренебрежимо малым. Следу-
ющее
утверждение, таким образом, завершает доказательство теоремы.
Достарыңызбен бөлісу: