Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
В заключение атакующий А должен переслать результат осмысленного угадывания бита 6. На этом атака завершается. Как уже несколько раз указывалось, атакующий А не должен возвращать для расшифровки оклик с*. Саймон не должен иметь возможности расшифровать сообщение с*, поскольку именно этого ждет от него атакующий.
Имитация случайных оракулов. Саймон имитирует двух случайных оракулов G и Н, используя преобразование ОАЕР. Для этого Саймон поддерживает два списка: G- и Я-список, которые в начальный момент являются пустыми.
566
Часть V. Методы формального доказательства стойкости
G-оракул. Предположим, что атакующий Л создал запрос д, предназначенный для оракула G. Если запрос д уже хранится в списке, Саймон возвращает атакующему Л результат G(g). В противном случае запрос д является новым. В этом случае Саймон формирует случайную строку G(g), имеющую равномерное распределение и длину ко, возвращает атакующему Л число G(g) и заносит в G-список новую пару (д, G(g)).
Если запрос возник на "этапе угадывания", Саймон пытается инвертировать функцию / в точке с*. Для каждой пары (g,G(g)), принадлежащей G-списку, и каждой пары (/г, H(h)), принадлежащей списку //-списку, Саймон вычисляет значение w = h \\ (д © Н(Ь)) и проверяет равенство с* = f(w). Если это равенство выполняется для некоторой строки, то значение /_1(с*) считается искомым.
//-оракул. Предположим, что атакующий Л создал запрос h, предназначенный для оракула Н. Если запрос h уже хранится в списке, Саймон возвращает атакующему Л результат H(h). В противном случае запрос h является новым. В этом случае Саймон формирует случайную строку H(h), имеющую равномерное распределение и длину к—ко, возвращает атакующему .41 число H(h) и заносит в //-список новую пару (h, H(h)). Если запрос возник на "этапе угадывания", Саймон пытается инвертировать! функцию / в точке с*, как показано выше. Имитация оракула расшифровки. Симон имитирует блок расшифровки (opa-j
кула О) следующим образом. Получив от атакующего Л зашифрованный текст с,
Симон проверяет G- и Н-списки в поисках пар (g, G(g)) и (/г, H(h)). Для каждой
пары, найденной в списке, Симон вычисляет значения
ю = Л || (g(BH(h)), v = G{g) © h,
проверяет равенство
с = f(w)
и отвечает на вопрос:
"Содержит ли число vk\ дополнительных нулей?"
Если на оба вопроса Саймон отвечает утвердительно, он возвращает атакующему Лп = к—ко—к\ старших бит числа v. В противном случае Саймон возвращает атакующему Л ОТКАЗ.
Поскольку атакующий Л является полиномиально ограниченным, количество] запросов случайным оракулам и запросов на расшифровку также ограничено полиномом. Следовательно, Саймон может завершить имитацию за полиномиальное время.
Глава 15. Доказуемо стойкие и эффективные криптосистемы.
567
15.2.3.2 Точность имитации
Как уже указывалось, для того, чтобы атака была успешной, имитация должна быть точной!
Прежде всего, как следует из леммы 15.1, два случайных оракула имитируются точно. Проверим теперь, насколько точно Саймон имитирует блок расшифровки.
Предположим, что Саймон получил подобранный зашифрованный текст с (подобранный до или после оклика, т.е. индифферентно или адаптивно). Саймон очень точно имитирует блок расшифровки. Допустим, что величины
определены корректным зашифрованным текстом с. С этого момента под термином "корректное значение" подразумевается величина, вычисленная реальным оракулом расшифровки О в ответ на полученный зашифрованный текст с.
Если корректный текст s, определенный по формуле (15.2.2), не является запросом оракулу Н, то корректного значения H(s) не существует. Следовательно, вероятность того, что величина г в каждом запросе оракулу G является корректной, равна 2~к°. Таким образом, ни в запросе оракулу Н, ни в запросе оракулу G нет корректных значений (вероятность противоположного события равна 2~к°). Значит, вероятность того, что в числах s и G(r) содержатся кх нулевых младших разрядов, равна 2~kl, поскольку для этого необходимо, чтобы запросы s и G(r) содержали кх идентичных младших бита. Это невозможно, поскольку число s не существует, а запрос G(r) является равномерно распределенным. Заметим, что этот анализ учитывает случай, когда число г является корректным и не содержится в запросе оракулу G: вероятность ошибки в этом случае равна 2~kl.
Итак, мы пришли к следующим выводам.
• Если оба числа s и г содержатся в запросах соответствующим случайным оракулам, то имитация расшифровки позволяет правильно сконструировать значение /-1(с) и расшифровать сообщение с.
• Если число s и/или г не содержится в запросах соответствующим случайным оракулам, то правильная имитация расшифровки должна возвращать отказ с вероятностью ошибки, равной 2~к° + 2~kl.
Отметим, что во втором случае вероятность ошибки имеет статистический смысл, т.е. не зависит от мощности атакующего Л.
Итак, мы доказали, что схема /-ОАЕР является доказуемо стойкой к атаке IND-CCA (т.е. к атаке во время ленча или на основе индифферентно подобранного зашифрованного текста). Это утверждение справедливо, поскольку в атаке IND-CCA блок расшифровки включается только на "этапе поиска", а мы ранее
