Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
(АТК = ССА2)
Идентичные копии расшифровок
Угаданный бит
С А Й М О
и
Идентичные копии зашифрованных текстов, подобранных до отклика
Расшифровки
Равномерно распределенные случайные величины тО. ml
Идентичные копии зашифрованных текстов, подобранных после оклика
Расшифровки
Ерк(тЬ + 1).
R(x.y)=lecm
и только если у = х+1
О
А: организатор атаки IND-ATK Саймон:
по отношению к атакующему А имитирует оракула
шифрования-расшифровки О в атаке IND-ATK
по отношению к оракулу О в атаке NM-ATK играет роль атакующего
О: оракул шифрования-расшифровки в атаке NM-ATK
Рис. 14.2. Редукция атаки NM к атаке IND
Доказательство. Докажем эту теорему методом от противного, показав, что из уязвимости криптосистемы с открытым ключом ?pk для атак IND-ATK следуеа уязвимость к атакам NM-ATK.
Предположим, что криптосистема ?ф является уязвимой к атакам IND-ATK. Тогда существует полиномиально ограниченный атакующий А, способный взло! мать криптосистему ?ф с помощью атаки IND-ATK с преимуществом Adv(.A),| которое не является пренебрежимо малой величиной. Допустим, что Саймону-i
Глава 14. Определения формальной и сильной стойкости криптосистем... 549
Зашифрованные тексты, подобранные до оклика Идентичные копии зашифрованных текстов,
подобранных до отклика
Идентичные копии расшифровок Расшифровки
тО. ml тО. ml
с* с*
А Зашифрованные тексты, подобранные после оклика С А Й Идентичные копии зашифрованных текстов, подобранных после О
М оклика
Идентичные О и Расшифровки
копии расшифровок
c'.R
с
т (расшифровка зашифрованного текста с")
Ь где ЩтЪ, т) = I
А: организатор атаки NM-CCA2 Саймон:
по отношению к атакующему А имитирует оракула
шифрования-расшифровки О в атаке NM-CCA2
по отношению к оракулу О в атаке IND-ATK играет роль атакующего
О: оракул шифрования-расшифровки в атаке IND-CCA2
Рис. 14.3. Редукция атаки IND-CCA2 к атаке NM-CCA2
имитатору и атакующему Л удалось провести редукцию и взломать криптосистему ?рк с помощью атаки NM-ATK.
Саймон одновременно управляет двумя атаками. Одна из этих атак протекает в режиме IND-ATK (т.е. в соответствии с одним из протоколов 14.1, 14.3 или 14.4). Саймон играет в ней роль оракула О, взаимодействующего с атакующим, т.е. со Злоумышленником. Другая игра проходит в режиме NM-ATK (т.е. по протоколу 14.5). В ней Саймон играет роль Злоумышленника, взаимодействующе-
550
Часть V. Методы формального доказательства стойкости
го с оракулом шифрования (и оракулом расшифровки, если АТКе {ССА, ССА2}). На рис. 14.2 показан наиболее общий процесс редукции, когда АТК = ССА2. В остальных атаках некоторые взаимодействия между участниками игры могут быть пропущены.
Следует заметить, что в атаке на уязвимую криптосистему (см. правую часть! взаимодействий, изображенных на рис. 14.2) распределение подобранных зашифрованных текстов является равномерным. Следовательно, оракул О должен зашифровывать случайные подобранные тексты.
Атакующий А должен "осмысленно" угадать бит Ъ G {0,1}. После этого Саймон может свободно вычислить зашифрованный текст с' = ?рк(гпъ + 1) и отношение R(x, у) = 1 тогда и только тогда, когда у = х + 1 для всех чисел х из пространства исходных текстов. Очевидно, что, если атакующий А использует полиномиально ограниченный алгоритм, Саймон может вычислить правильный результат за полиномиальное время.
Поскольку атакующий А угадывает бит Ь с преимуществом Adv (.А), получаем следующую оценку.
NM-Adv(Simon) = Adv(.A) - РгоЬ[(с,Я) <- ZK-Sim].
Обратите внимание на то, что имитатор ZK-Sim не имеет доступа к зашифрованному оклику с* и, следовательно, не может взаимодействовать с атакующим А. Таким образом, для результирующего зашифрованного текста с вероятность Prob[(c, R) <— ZK-Sim] должна быть пренебрежимо малой. Следовательно, преимущество NM-Adv(Sim) не является пренебрежимо малой величиной, что и требовалось доказать. ?
Напомним, что мы продемонстрировали множество атак в режиме IND-ATK' на самые разнообразные криптосистемы. Из теоремы 14.5.4.2 следует, что все они уязвимы для атак NM-ATK.
Как известно, существуют криптосистемы, стойкие к атакам IND-CPA (соответственно IND-CCA), но уязвимые к атакам NM-CPA (соответственно NM-CCA) [19].
Среди зависимостей между понятиями стойкости к атакам в режимах NM и IND, проанализированных в работе [19], наиболее важным является тот факт, что из неразличимости следует строгая стойкость к атаке на основе адаптивно подобранных зашифрованных текстов.
14.5.4.2 Неразличимость эквивалентна строгой стойкости к атаке на основе адаптивно подобранного зашифрованного текста
Для ситуации, когда АТК = ССА2, справедлива следующая теорема.
Теорема 14.4. Криптосистема с открытым ключом является стойкой к атаке NM-CCA2 тогда и только тогда, когда она является стойкой к атаке IND-CCA2
Глава 14. Определения формальной и сильной стойкости криптосистем... 551
NM-CPA -*- NM-CCA « ' NM-CCA2
IND-CPA -*- IND-CCA -«- IND-CCA2
Рис. 14.4. Отношения между понятиями стойкости криптосистем с открытым ключом
