Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
Рассмотрим довольно простой, но элегантный пример предложенного Одедом Голдрейчем, Сильвио Микэли и Эви Вигдерсо-ном [196] протокола доказательства с минимальным раскрытием, который позволяет Алисе убедить Боба в том, что она знает некоторый изоморфизм между двумя заданными графами G и Я,
Доказательства с наименьшим раскрытием 99
таким образом, что это никак не помогает Бобу разгадать этот изоморфизм. Данный пример иллюстрирует применение принципа «разрезания-и-выбора» (и раскрывает ссылку, которая была сделана в конце § 2 в том абзаце, где приводится описание примера схемы битового обязательства, основанной на изоморфизме графов). В произвольном раунде этого протокола Алиса случайно переставляет вершины G, чтобы получить некоторый граф К, изоморфный как графу G, так и графу Н, и передает К Бобу. Очевидно, что если Алиса правдива, то она должна знать также и изоморфизм между Н и К (посредством композиции сделанной перестановки с перестановкой, определяющей изоморфизм между G и Н, о знании которого она заявила).
После этого Боб выбирает G или Н и предлагает Алисе предоставить ему изоморфизм между выбранным им графом и К. Ясно, что Алиса в состоянии решить эту трудную задачу, только если она не врет. Однако Алиса, вне зависимости от того, каким способом она получает К (даже полагая, что она попытается мошенничать), не сможет быть готова ответить на оба возможных вопроса, если она в действительности не знает изоморфизма между G и Н. Следовательно, поскольку Алиса, не может! предсказывать, какой из вопросов будет поставлен Бобом, любая ее попытка смошенничать будет выявлена им с вероятностью равной по крайней мере одной второй. Вероятность не выявленного обмана может быть, таким образом, сделана сколь угодно малой при помощи повторения этого процесса достаточно большое число раз. Несколько труднее, однако, увидеть, что этот протокол не в состоянии помочь Бобу определить изоморфизм между графами G и Н. Для выяснения дальнейших деталей обращайтесь к [196].
Описанный протокол хорошо работает для такой специфической проблемы, как изоморфизм графов. Однако ^ля того чтобы показать, что справедливость любой эффективно проверяемой информации может быть подтверждена с помощью доказательства с минимальным раскрытием, нам необходим более сильный результат. С помощью теоремы Стевена Кука [120] техника доказательства с минимальным раскрытием для задачи о выполнимости (или любой другой NP-полной проблемы [186]) будет автоматически давать такое доказательство для любого позитивного утверждения, относящегося к произвольному языку из. NP. При
100 Применения
Глава 6
подходящих криптографических предположениях такие протоколы были получены Одедом Голдрейчем, Сильвио Микэли и Эви Вигдерсоном для такой NP-полаой проблемы, как 3-раскраска графов [196], а Дэвидом Чаумом — для задачи о выполнимости [103]. Сходные результаты для булевых схем были получены независимо, но несколько позднее, Жилем Брассаром и Клодом Крепеу [79, 78].
Понятие доказательства с минимальным раскрытием естественным образом распространяется на вероятностно проверяемую информацию [78]. В принципе можно даже публиковать доказательства с минимальным раскрытием (так что интерактивность, вообще говоря, не является обязательной) [55]. По этому поводу читайте также [183, 54, 114, 21, 206, 345, 346, 78]. О дискуссии на эту тему относительно Министерства обороны Соединенных Штатов сообщается в [189, 103]. Сейчас же мы приведем конструкцию Чаума в деталях.
Предположим, что Алисе известно какое-то выполнимое присваивание истинностных значений для некоторой булевой формулы. Протокол, который будет представлен ниже, позволяет Алисе убедить Боба в том, что она знает это присваивание, не выдавая при этом никакой информации о нем. (Заметим, что булева формула сама по себе не является секретной — таково лишь то выполнимое присваивание, которое Алиса хочет утаить от Боба.) В качестве примера рассмотрим булеву формулу
ф = [(р A q) © {q V г)] Л [(г ® q) V (р Л г)]
и предположим, что {р = true, q = false, г = true) — выполнимое секретное присваивание Алисы. (Само собой разумеется, что рассматриваемый пример нельзя считать реальным, так как для Боба было бы слишком легко выяснить, каким образом можно сделать выполнимым столь простое булево выражение.)
На первом шаге Алиса и Боб договариваются о реализации булевой схемы, вычисляющей Ф. Для простоты мы используем в качестве базиса только двухвходовые вентили и инверторы. Схема для Ф изображена на рис. 6.1 на стр. 101. Кроме того, на этом рисунке приведено выполнимое присваивание Алисы и представлены таблицы истинности для каждого из вентилей (за исключением вентилей отрицания).
Отметим, что. в каждой таблице истинности выделена одна из
Доказательства с наименьшим раскрытием 101
Рис. 6.1. Булева схема с полными таблицами истинности
строк, которая соответствует результатам работы рассматриваемой схемы в соответствии с выполнимым присваиванием Алисы. Анализируя эти строки, довольно легко проверить, что Ф является выполнимой. Это можно выяснить с помощью простых независимых проверок на совместность каждой цепи. Например, выходное значение для верхнего левого вентиля Л равно 0, которое, в свою очередь, является первым входным значением в средней строке таблицы истинности для вентиля ф. К тому же первые входы верхнего левого и верхнего правого вентиля Л являются одинаковыми, как это и должно быть, так как они соответствуют одной и той же входной переменной. Наконец, выход последнего вентиля равен 1. Заметим также, что просмотр этих выделенных строк выявляет и соответствующее выполнимое присваивание (даже если оно не было выписано явно). Поэтому нам потребуется такой протокол, который позволил бы Алисе убедить Боба, что она знает, каким образом должно быть сделано вы-
