Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Кроме того, гипотеза V ф NV является необходимым условием существования однонаправленной функции (one-way function). В начале книги (раздел 1.1.1) было сформулировано предположение, что однонаправленная функция f(x) должна обладать "волшебным" свойством 1.1: значение f(x) для всех целых чисел х вычисляется легко, а восстановить число х для большинства значений f(x) (за исключением пренебрежимо малого количества случаев) чрезвычайно трудно. Теперь мы знаем, что это условие выполняется для алгоритмов из класса NV. Например, задача SATISFIABILITY определяет однонаправленную функцию, отображающую тг-мерное пространство булевских кортежей в множество {True, False}.
В свою очередь, существование однонаправленной функции представляет собой необходимое условие для применения цифровых подписей (digital signatures), которые легко распознать, но трудно подделать.
Более того, понятие полиномиальной неразличимости, изученное нами в разделе 4.7, также основано на гипотезе V ф NV. Задача полиномиальной неразличимости представляет собой задачу принятия решений из класса NV. В главах 14, 15 и 17 мы рассмотрим роль, которую играет полиномиальная неразличимость в современной криптографии при доказательстве корректности криптографических алгоритмов и протоколов.
Необходимо упомянуть о том, насколько важна гипотеза V ф NV для протоколов с нулевым разглашением [126] и для интерактивных систем доказательства.
Протокол с нулевым разглашением — это интерактивная процедура, выполняемая двумя участниками, называемыми доказывающим (prover) и верификатором (verifier), причем последний обладает полиномиально ограниченными вычислительными мощностями. Протокол позволяет доказывающему лицу убедить верификатора, что доказывающий знает ответ "ДА" для NP-задачи (например, ответ "ДА" для задачи SQUARE-FREENESS или ответ "ДА" на вопрос "Порождено ли число N в ходе эксперимента -E,2_Prime?")» поскольку доказывающий владеет вспомогательной информацией, но не раскрывает проверяющему ее суть. Следовательно, проверяющий ничего не знает о доказательстве, которым владеет доказывающий. Такое доказательство можно смоделировать с помощью недетерминированной машины Тьюринга с дополнительной случайной лентой. Доказыва-
Глава 4. Вычислительная сложность
171
ющий может использовать вспомогательную информацию, поэтому машина под управлением доказывающего всегда может выполнить правильный такт вдоль последовательности распознавания (т.е. продемонстрировать, что доказывающий действительно знает ответ "ДА"). Следовательно, временная сложность доказательства полиномиально зависит от размера входной информации. Верификатор должен послать доказывающему запрос и попросить его провести машину Тьюринга вдоль последовательности распознавания или вдоль какой-либо иной последовательности, причем запрос должен быть равномерно распределенной случайной величиной. Итак, с точки зрения верификатора, система доказательств ведет себя как рандомизированная машина Тьюринга (раздел 4.4). Независимо повторяя запуски машины Тьюринга, ошибку рандомизированной машины Тьюринга можно уменьшить до ничтожно малой величины (раздел 4.4.1.1). Это убеждает верификатора, что доказывающий действительно знает ответ "ДА" для поставленной задачи.
Гипотеза V ф HV имеет для протоколов с нулевым разглашением двойное значение: 1) вспомогательная информация для NP-задачи позволяет доказывающему провести эффективное доказательство и 2) трудность задачи означает, что верификатор самостоятельно не в состоянии проверить утверждение доказывающего лица.
4.8.2 Недостаточное условие
Гипотеза V ф HV не является достаточным условием стойкости криптосистем, даже если криптосистема основана на решении NP-полной задачи. Примером нестойкой NP-полной задачи является задача об укладке ранца [200].
Изучив основы теории вычислительной сложности, перейдем к разбору причин, по которым криптосистемы, основанные на решении NP-задачи, часто оказываются нестойкими.
Во-первых, как мы уже указывали (определение 4.1), в рамках теории вычислительной сложности язык L (задача) включается в класс сложности с помощью квантора всеобщности: "любое предложение / € L". Это ограничение приводит на анализу худшего случая (worst-case complexity): задача считается трудноразрешимой, даже если у нее есть лишь несколько сложных вариантов. В противоположность этому криптоанализ считается успешным, если с его помощью удается решить значительное количество вариантов. Именно по этой причине взлом криптосистемы, основанной на решении NP-задачи, не означает решения самой задачи. Очевидно, что анализ худших вариантов бесполезен для измерения стойкости практических криптосистем.
Вторая причина заключается в изначальной трудности определения новой, более низкой верхней границы сложности для NP-задачи (см. раздел 4.5). Стойкость криптосистем, основанных на решении NP-задачи, даже если задача является
172
Часть II. Математические основы
трудноразрешимой, в лучшем случае остается недоказанной. Как правило, остается недоказанной даже сама трудная разрешимость задач, лежащих в основе стойкости таких криптосистем.
