ф = [(р Л ?) е (? V г)] Л [(г ф ?) V (р Л г)

и предположим, что {р = true, q = false, г = true) - выполнимое секретное присваивание Алисы, (Само собой разумеется, что рассматриваемый пример нельзя считать реальным, так как для Боба было бы слишком легко выяснить, каким образом можно сделать выполнимым столь простое булево выражение.)

Па первом шаге Алиса и Боб договариваются о peajH3anHH булевой схемы, вычисляющей Ф. Для простоты мы используем в качестве базиса только двухвходовые вентили и инверторы. Схема для Ф изображена на рис. 6.1 на стр.101. Кроме того, на этом рисунке приведено выполнимое присваивание Алисы и представлены таблицы истинности для каждого из вентилей (за исключением вентилей отрицания).

Отметим, что в каждой таблице истинности выделена одна из

подходяыщх криптографических предположениях такие протоколы были получены Одедом Голдрейчем, Сильвио Микэли и Эви Вигдерсоном для такой JVP-полаой проблемы, как 3-раскраска графов [196], а Дэвидом Чаумом - для задачи о выполнимости [103]. Сходные результаты для булевых схем были получены независимо, но несколько позднее, Жилем Брассаром и Клодом Крепеу [79, 78].

Понятие доказательства с минимальным раскрытием естественным образом распространяется на вероятностно проверяемую информацию [78]. В принципе можно даже публиковать доказательства с минимальным раскрытием (так что интерактивность, вообще говоря, не является обязательной) [55]. По этому поводу читайте также [183, 54, 114, 21, 206, 345, 346, 78]. О дискуссии на эту тему относительно Министерства обороны Соединенных Штатов сообщается в [189, 103]. Сейчас же мы приведем конструкцию Чаума в деталях.

Предположим, что Алисе известно какое-то выполнимое присваивание истинностных значений для некоторой булевой формулы. Протокол, который будет представлен ниже, позволяет Алисе убедить Боба в том, что она знает это присваивание, не выдавая при этом никакой информации о нем. (Заметим, что булева формула сама по себе не является секретной - таково лишь то выполнимое присваивание, которое Алиса хочет утаить от Боба.) В качестве примера рассмотрим булеву формулу

Q © Q

-<5>-

Рис. 6.1. Булева схема с полными таблицами истинности

строк, которая соответствует результатам работы рассматриваемой схемы в соответствии с выполнимым присваиванием Алисы. Анализируя эти строки, довольно легко проверить, что Ф является выполнимой. Это можно выяснить с помош;ью простых независимых проверок на совместность каждой цепи. Например, выходное значение для верхнего левого вентиля Л равно О, которое, в свою очередь, является первым входным значением в средней строке таблицы истинности для вентиля ф. К тому же первые входы верхнего левого и верхнего правого вентиля Л являются одинаковыми, как это и должно быть, так как они соответствуют одной и той же входной переменной. Наконец, выход последнего вентиля равен 1. Заметим также, что просмотр этих выделенных строк выявляет и соответствующее выполнимое присваивание (даже если оно не было выписано явно). Поэтому нам потребуется такой протокол, который позволил бы Алисе убедить Боба, что она знает, каким обргьзом должно быть сделано вы-

деление строк в каждой таблице истинности, не раскрывая при этом какой бы то ни было информации о том, что это за строки.

Как и ранее, это достигается посредством интерактивного протокола, состоящего из нескольких раундов. В каждом раунде Алиса сначала «перетасовывает» все таблицы истинности рассматриваемой схемы й принимает в качестве обязательства соответствующие им семейства блобов (см. § 2). После этого Боб задает Алисе один из двух трудных проверочных вопросов: в качестве ответа на один из них от Алисы требуется, чтобы она показала, что принятые ею блобы и в самом деле кодируют правильное перетасовывание таблиц истинрости схемы; для ответа на другой вопрос Алисе необходимо открыть строку, которая должна быть выделенной, в предположении, что перетасовывание сделано правильно. Как и всегда, вопросы формулируются так, чтобы Алиса была в состоянии правильно ответить на оба из них, только если она знает, как обеспечить выполнимость схемы, но отвечая на какой-то один из них, она не должна предоставлять никакой информации о том, как это можно сделать. Как было показано ранее, поскольку у Алисы нет возможности заранее предугадать, какой из вопросов будет задан Бобом, то с каждым успещно проведенным раундом доверие Боба к утверждению Алисы будет возрастать.

Перетасовывание каждой таблицы истинности, которое осуществляет Алиса, состоит из случайной перестановки ее строк в сочетании со случайным инвертированием содержимого ее столбцов. Проиллюстрируем этот механизм на примере. Па рис. 6.2 на стр. 103 в части (а) изображена таблица истинности для булевой конъюнкции (л). Строки этой таблицы случайным образом переставляются и получается таблица, которая приведена на рис. 6.2 (Ь). (При этом каждая из 24 возможных перестановок, включая тождественную перестановку, может быть выбрана с одинаковой вероятностью.) Затем для каждого из трех столбцбв таблицы истинности случайно задается значение некоторого бита. И наконец, для каждого из столбцов, тогда и только тогда, когда соответствующий ему случайный бит равен 1, вычисляется его дополнение (при котором инвертируются все биты, составляющие данный столбец) тгж, как это показано на трех промежуточных таблицах. Окончательный результат представлен на рис. 6.2(c). Заметим, что .полностью перетасованная таким образом таблица