Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Таким образом, мы сформулировали два понятия стойкости: NM-CCA и NM-CCA2.
Поскольку задачи, лежащие в основе NM-стойкости, носят вычислительный характер, мы не приводим формальных доказательств. Читатели, которых заинтересовала эта тема, могут найти подробную информацию в работе [100]. Естественно ожидать, что формализация понятия NM-стойкости связана с понятиями,' выходящими за рамки IND-стойкости. Например, в отличие от задач принятия решений, в которых размер пространства исходных сообщений не важен (он мо-1 жет быть равен двум, как в криптосистеме Голдвассера-Микали), в теории NM-стойкости пространство исходных сообщений должно быть достаточно большим, чтобы вычисление отношения R оказалось нетривиальной задачей.
В работе [19] авторы предложили немного другой способ формализации понятия NM-стойкости, основанный на игровых атаках, аналогичных IND-атакам. '
Несмотря на это, изложенных выше сведений вполне достаточно для того, чтобы понять идею NM-стойкости. Легко видеть, что большинство учебных алгорит-] мов шифрования, использующих однонаправленную функцию с секретом, весьма! уязвимо. Как показано в главе 9, все однонаправленные функции с секретом, лежащие в основе популярных криптосистем с открытым ключом, можно инвер-1 тировать, используя частичную информацию, полученную от оракула (например,] от "оракула четности"). Именно эти принципы инверсии позволяют организовывать гибкие атаки на неизвестные исходные сообщения. Например, в алгоритме) RSA выполняется равенство с = me(modN). Благодаря этому Злоумышленнш! знает, что неизвестный исходный текст т можно продублировать, если умножить' его на 2е (mod N).
Долев с соавторами разработали схему шифрования с открытым ключом, обладающую доказуемой стойкостью к атаке NM-CCA2 [100]. В этой схеме для' побитового шифрования исходного сообщения используется большое количества пар, состоящих из открытых и закрытых ключей. Кроме того, шифрование каждого бита исходного текста содержит доказательство NIZK,
14.5.4 Связь между неразличимостью и строгостью
Несомненно, понятие строгой стойкости весьма важно. Однако вследствие того, что задачи, лежащие в основе этого понятия, носят вычислительный характер, формальное доказательство строгой стойкости является довольно сложным.
Глава 14. Определения формальной и сильной стойкости криптосистем... 547
Следовательно, разработка строгой криптосистемы и доказательство ее стойкости представляют собой нетривиальную задачу.
К счастью, исследователи обнаружили большое количество важных зависимостей между строгой стойкостью и неразличимостью. Более того, оказалось, что понятие стойкости ССА2 эквивалентно понятию неразличимости. Поскольку формальное доказательство стойкости к атаке IND-CCA2 хорошо известно, с его помощью можно доказать стойкость криптосистемы к атаке NM-CCA2.
Формальное доказательство этих зависимостей можно получить, сконструировав полиномиальный алгоритм редукции (polynomial-time reduction algorithm). Применительно к атакам на криптосистемы это означает, что целевую атаку (Target Attack) можно свести к исходной (Source Attack). Если алгоритм редукции является полиномиальным, то целевую атаку можно реализовать с помощью исходной, причем стоимость организации целевой атаки является полиномиально ограниченной.
Поскольку любая атака на криптосистему всегда основана на некоторых предположениях и сопровождается определенными ограничениями (например, в атаке ССА2 атакующий должен пройти курс обучения криптоанализу до и после получения оклика), алгоритм редукции также должен удовлетворять этим условиям. Как правило, для выполнения редукции мы будем использовать специального агента, Саймона-имитатора (Simon Simulator). Предполагается, что Саймон удовлетворяет всем условиям и ограничениям, предъявляемым к рабочему окружению при организации атаки.
Иногда, после взаимодействия со Злоумышленником Саймон сам становится атакующим, управляя сразу двумя играми между атакующим и оракулом шифрования-расшифровки — целевой и исходной атаками. С одной стороны, Саймон участвует в исходной игре с атакующим, имитируя рабочее окружение (т.е. представляясь атакующему оракулом шифрования-расшифровки). С другой стороны, Саймон участвует в целевой игре с оракулом шифрования-расшифровки, играя роль атакующего. В такой ситуации можно считать, что атакующий в исходной атаке обучает Саймона методам организации целевой атаки. Схема управления атаками изображена на рис. 14.2 и 14.5.4.1.
14.5.4.1 Из строгой стойкости следует неразличимость
Обозначим атаки CPA, CCA и ССА2 через АТК. Покажем, что из стойкости криптосистемы с открытым ключом к атакам NM-ATK следует стойкость к атакам END-ATK.
Теорема 14.3. Если криптосистема с открытым ключом является стойкой к атакам NM-ATK, то она также является стойкой к атакам IND-ATK.
548
Часть V. Методы формального доказательства стойкости
Зашифрованные тексты, подобранные до оклика
(АТК = ССА,ССА2)
Идентичные копии расшифровок
Равномерно распределенные случайные величины тО. ml
Зашифрованные тексты, подобранные после оклика
