Блюм (Blum) доказал, что любая математическая теорема может быть преобразована в граф, такой, что д о-казательство теоремы будет эквивалентно доказательству существования гамильтонова цикла для этого графа . В общем виде то, что для любого NP-полного утверждения есть доказательство с нулевым знанием, использу тощее однонаправленные функции и, следовательно, хорошие алгоритмы шифрования, доказано в [620]. Любое математическое доказательство может быть преобразовано в доказательство с нулевым знанием . Используя эту методику, исследователь может доказать миру, что ему известно доказательство конкретной теоремы, не ра с-крывая самого решения. Блюм мог опубликовать свои результаты, не раскрывая их .
Также существуют доказательства с минимальным раскрытием[590]. Для доказательства с минимальным раскрытием выполняются следующие свойства:
1. Пегги не может обмануть Виктора. Если Пегги не знает доказательства, ее шансы убедить Виктора в
том, что доказательство ей известно, пренебрежимо малы.
2. Виктор не может обмануть Пегги. Он не получает ни малейшего намека на доказательство кроме того
факта, что доказательство известно Пегги. В частности, Виктор не может продемонстрировать доказ а-
тельство никому другому, не доказав все сам с самого начала.
У доказательств с нулевым знанием есть дополнительное условие :
3. Виктор не узнает от Пегги ничего такого, чего он не смог бы узнать и самостоятельно кроме того фа к-
та, что доказательство известно Пегги.
Существует заметная математическая разница между доказательствами с минимальным раскрытием и док а-зательствами с нулевым знанием. Это различие находится вне рамок данной книги, но более искушенные чит а-тели могут проштудировать другую литературу. Понятия изложены в in [626, 619, 622]. Дальнейшая проработка этих идей, основанная на различных математических предположениях, выполнена в [240, 319, 239].
Существуют различные типы доказательств с нулевым знанием :
— Совершенное.Существует имитатор, который создает стенограммы, полностью соответствующие реал ь-ным стенограммам (примеры с гамильтоновым циклом и изоморфизмом графов).
— Статистическое.Существует имитатор, который создает стенограммы, полностью соответствующие р е-альным стенограммам, кроме фиксированного числа исключений.
— Вычислительное.Существует имитатор, который создает стенограммы, неотличимые от реальных.
— Неиспользующее.Имитатора может и не быть, но мы можем доказать, что Виктор не узнает никакой информации из доказательства (параллельный пример)
Годы тяжелой работы, как теоретической, так и прикладной, присели к появлению доказательств с мин и-мальным раскрытием и нулевым знанием. Майк Берместер (Mike Burmester) и Иво Десмедт изобрели широковещательно интерактивное доказательство, где владелец секрета может широковещательно передавать большой группе контролеров интерактивное доказательство с нулевым знанием [280]. Криптографы доказали, что все, что может быть доказано с помощью интерактивного доказательства, может быть доказано и с помощью инт е-рактивного доказательства с нулевым знанием [753, 137].
Хорошей обзорной статьей по данной теме является [548]. Дополнительные математические подробности, варианты, протоколы и приложения ищите в [590, 619, 240, 319, 620, 113,241, 152, 8, 660, 238, 591, 617, 510, 592, 214, 104, 216, 832, 97, 939, 622, 482, 615, 618, 215, 476, 71]. Много чего было написано по этому вопросу.
5.2 Использование доказательства с нулевым знанием для идентификации
В реальном мире для доказательств подлинности часто используются физические символы: паспорта, вод и-тельские права, кредитные карточки и т.д. Эти символы содержат что-то, связывающее их с конкретным чел о-веком: обычно фотографию или подпись, но с той же вероятностью это может быть отпечаток пальца, снимок сетчатки глаза или рентгеновский снимок челюсти. Как было бы здорово делать что-то подобное цифровым образом?
Использовать доказательства с нулевым знанием для доказательства идентичности было впервые предлож е-но Уриелем Файгом (Uriel Feige), Амосом Фиатом (Amos Fiat) и Ади Шамиром [566, 567]. Закрытый ключ Алисы становится функцией ее "идентичности". Используя доказательство с нулевым знанием, она доказывает, что она знает свой закрытый ключ и, таким образом, свою идентичность . Соответствующие алгоритмы можно найти в разделе 23.11.
Это очень многообещающая идея. Она позволяет человеку доказать свою личность без использования физ и-ческих символов. Однако, она не совершенна. Вот примеры возможных злоупотреблений.