Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
162 Применения
Глава 6
деление строк в каждой таблице истинности, не раскрывая при этом какой бы то ни было информации о том, что это за строки.
Как и ранее, это достигается посредством интерактивного протокола, состоящего из нескольких раундов. В каждом раунде Алиса сначала «перетасовывает» все таблицы истинности рассматриваемой схемы й принимает в качестве обязательства соответствующие им семейства блобов (см. § 2). После этого Боб задает Алисе один из двух трудных проверочных вопросов: в качестве ответа на один из них от Алисы требуется, чтобы она показала, что принятые ею блобы и в самом деле кодируют правильное перетасовывание таблиц/ истинрости схемы; для ответа на другой вопрос Алисе необходимо открыть строку, которая должна быть выделенной, в предположении, что перетасовывание сделано правильно. Как и всегда, вопросы формулируются так, чтобы Алис а была в состоянии правильно ответить на оба из них, только если она знает, как обеспечить выполнимость схемы, но отвечая на какой-то один из них, она не должна предоставлять никакой информации о том, как это можно сделать. Как было показано ранее, поскольку у Алисы нет возможности заранее предугадать, какой из вопросов будет задан Бобом, то с каждым успешно проведенным раундом доверие Боба к утверждению Алисы будет возрастать.
Перетасовывание каждой таблицы истинности, которое осуществляет Алиса, состоит из случайной перестановки ее строк в сочетании со случайным инвертированием содержимого ее столбцов. Проиллюстрируем этот механизм на примере. На рис. 6.2 на стр. 103 в части (а) изображена таблица истинности для булевой конъюнкции (Л). Строки этой таблицы случайным образом переставляются и получается таблица, которая приведена на рис. 6.2
(Ь). (При этом каждая из 24 возможных перестановок, включая тождественную перестановку, может быть выбрана с одинаковой вероятностью.) Затем для каждого из трех столбцов таблицы истинности случайно задается значение некоторого бита. И наконец, для каждого из столбцов, тогда и только тогда, когда соответствующий ему случайный бит равен 1, вычисляется его дополнение (при котором инвертируются все биты, составляющие данный столбец) так, как это показано на трех промежуточных таблицах. Окончательный результат представлен на рис. 6.2(c). Заметим, что полностью перетасованная таким образом таблица
Доказательства с наименьшим раскрытием 103
Рис. 6.2. Пример перетасовывания таблиц истинности
истинности может быть, тем не менее, безошибочно опознана как представляющая булеву конъюнкцию (при условии, что биты соответствующих операций дополнения столбцов, которые указываются внутри кружочков для отвечающих им цепей, заранее определены).
Дополнения при этом должны браться согласованно: биты всех столбцов таблиц истинности, соответствующие одной и той же цепи схемы, должны либо инвертироваться, либо оставаться теми же, что и были. Это достигается выбором битов дополнений случайно и независимо для каждой соответствующей цепи. (Для простоты мы никогда не инвертируем выход результирующего вентиля.) На рис. 6.3 на стр. 104 приведен результат некоторых случайных перестановок и дополнений столбцов в таблицах истинности для нашей исходной схемы, изображенной на рис. 6.1.
После того как с проверяемой схемой сделано то же самое, что в результате в качестве примера показало на рис. 6.3, Алиса принимает ее в качестве обязательства: для каждого бита табли-
104 Применения _______________________________________ Глава 6
А
0 1 1 г 1 1 1 1 1
0 0 0 0 0 1 ф. 0 1 0
1 0 1 1 0 0 0 0 1
1 1 1 0 1 1 0 0
(§
А
5
v
Ч5>-
А
| Ф
i?
Рис. 6.3. Схема с перетасованными таблицами истинности
цы истинности Алиса задается некоторым блобом, о котором она знает, как он, соответствующим образом, должен быть открыт. (В действительности для нее не обязательно задаваться битами дополнений, но они в тот момент должны оставаться в секрете.) Можно представлять себе, что Алиса изобразила рис. 6.3 на полу, но до того, как позволить Бобу взглянуть на него, заклеила все его биты непрозрачной липкой лентой. В этот момент процесс фазы «разрезания» для Алисы заканчивается и начинается фаза «выбора» для Боба. Он просит Алису убедить его в ее честности, предлагая дать ответ на выбранную им случайным образом одну из двух задач, задачу А или задачу В, которые заключаются в следующем:
Задача А. Алиса должна открыть все без исключения блобы, которые она только что приняла в качестве обязательств. Более того,- она должна также показать все биты допол-
Доказательства с наименьшим раскрытием 105
нений, которые использовались ею в процессе перетасовывания. Продолжая наше предыдущее образное представление, Алиса, для того чтобы продемонстрировать Бобу свой эквивалент схемы, вроде той, что изображена на рис. 6.3, должна отклеить все заклеенные ею места. Это позволяет Бобу проверить, что информация, которая была скрыта посредством блоба, соответствует правильным перестановкам и дополнениям таблицы истинности проверяемой булевой схемы.
