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

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] является пренебрежимо малым. Следу-
ющее утверждение, таким образом, завершает доказательство теоремы.

жүктеу/скачать 6.4 Mb.

Достарыңызбен бөлісу: