Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
570
Часть V. Методы формального доказательства стойкости
Рассмотрим теперь схему шифрования /-OWTP, использующую функцию /. Напомним, что если с* — зашифрованный оклик, то в схеме /-ОАЕР ему соответствуют величины s*, ?*, г* и тпъ || 0fcl.
Поскольку атакующий Л представляет собой черный ящик, корректный зашифрованный текст можно легко получить с помощью модификации другого, корректного зашифрованного текста. Получив зашифрованный оклик с*, атакующий Л представляет зашифрованный текст в виде с* = s* || /о(?*)- Затем он выбирает произвольное ненулевое сообщение Л е {0,1 }k~k°~kl и вычисляет слеЛ дующее значение.
s = s* © (Л || 0fcl), v = /„(** © H{s*) © H(s)), с = s || v.
Очевидно, что для того, чтобы создать новый зашифрованный текст с на основе! зашифрованного оклика с*, атакующему А необходимо лишь послать оракулу Н, запросы s* и s.
Докажем теперь, что число с является корректной величиной тпъ © А, зашифрованной по схеме /-ОАЕР, поскольку зашифрованный текст с* является числом! тпъ, корректно зашифрованным по схеме /-ОАЕР. По числу t = t* © H(s*) © H(s)( можно найти величину г.
г = H{s) ®t = t*Q H(s*) = г*. (15.2.8)
Очевидно, что формула (15.2.8) выполняется даже тогда, когда атакующий А не посылает оракулу G запрос г = г* (вполне вероятно, что ему не известно числя г*, так как он может не знать число ?*).
Если бы в этой игре участвовали атакующий А и реальный оракул расшифровки О, то оракул О мог бы восстановить число г, выполнив следующие вычис! ления.
Г\С) = 8 || t,
г - H(s) © t.
Однако, учитывая формулу (15.2.8), на самом деле оракул О может найти число г*| Итак, применяя функцию хэширования G, оракул О может вычислить следующие значения.
G(r) © s = G(r*) © s* © (Л || 0fcl) = (тпь © Л) || 0fcl.
Выполняя поиск младших к\ нулевых разрядов, оракул О в результате правильно* расшифровки сообщения с должен вернуть число тпь © Л. Получив исходный текст тпъ © А, атакующий А может легко найти число тпъ и взломать таким образом схему /-ОАЕР с помощью атаки IND-CCA2.
Глава 15. Доказуемо стойкие и эффективные криптосистемы.
571
Однако, поскольку атака разыгрывается между атакующим Л и Саймоном, а не реальным оракулом расшифровки, G-список, поддерживаемый Саймоном, является пустым, и Саймон должен немедленно вернуть атакующему отрицательный ответ. Вот теперь атакующий Л действительно очень громко воскликнет:
"ПРЕКРАТИТЕ ДУРАЧИТЬСЯ!"
15.2.3.4 Вероятность того, что атакующий Л пошлет запрос s* на "этапе угадывания"
Мы оставили в стороне одну маленькую тонкость, связанную с оригинальным доказательством Белларе-Роджуэя: вероятность того, что атакующий Л пошлет запрос s* на "этапе угадывания" при условии, что он может правильно определить бит оклика. Поскольку эта часть доказательства связана с оценкой вероятности, ее можно безболезненно пропустить. (На самом деле это доказательство элементарно, и для его понимания достаточно знать правила, установленные в главе 3.)
Для начала предположим, что атакующий Л может правильно угадать бит b в оклике с преимуществом Adv после долгого обучения адаптивному подбору зашифрованного текста.
В ходе обучения Саймон может ошибочно отвергнуть корректный зашифрованный текст, содержащийся в запросе на расшифровку. Это — неприятное событие, демонстрирующее низкое качество обучения атакующего А. По этой причине обозначим это событие символами DBad. В разделе 15.2.3.2 анализ процедуры, выполняемой Саймоном, показал, что имитация расшифровки является точной: вероятность ошибки равна 2~к° + 2~kl. Таким образом,
Prob[DBad] и 2~к° + 2~kl. (15.2.9)
Пусть символы AskG (соответственно AskH) обозначают событие, которое заключается в том, что число г* (соответственно s*) содержится в G-списке (соответственно в /^-списке). Эти два события являются нежелательными, поскольку они сообщают атакующему, что оклик с* на самом деле не связан с подобранными исходными сообщениями то и тх. Определим событие Bad следующим образом.
Bad = AskG U AskH U DBad.
Обозначим через .Awins событие, которое заключается в том, что атакующий А правильно угадывает бит оклика 6. Очевидно, что в отсутствие события Bad бит оклика 6 не зависит от зашифрованного текста с*, поскольку все случайные величины, которые генерируются случайными оракулами, имеют равномерное распределение. Следовательно,
Prob[.4wins | Bad] = -.
(15.2.10)
572
Часть V. Методы формального доказательства стойкости
Применяя правило вычисления условной вероятности (определение 3.3 в разделе 3.4.1), выразим формулу (15.2.10) иначе.
_ Prob [Aw'ms П Bad] 1
Prob[.4wins j Bad]
Prob [Bad] 2
Prob[.4wins П Bad] = -(1 - Prob[Bad]). (15.2.11)
Необходимо отметить, что при событии Bad (т.е. в отсутствие события Bad) имитируемые случайные оракулы и имитируемый блок расшифровки работают идеально. Итак,
Prob[.4wins] = ^ + Adv. (15.2.12) j
С другой стороны (теорема 3.1 из раздела 3.4.3),
Prob[.4wins] = Prob[.4wins П Bad] + Prob[.4wins П Bad]. (15.2.13)
Сопоставив формулы (15.2.12) и (15.2.13), получаем
Prob[.Awins П Bad] + Prob[.4wins П Bad] = - + Adv.
