44 44 44

Рис. 6.2. Пример перетасовывания таблиц истинности

истинности может быть, тем не менее, безошибочно опознана как представляюшая булеву конъюнкцию (при условии, что биты со-ответствуюнщх операций дополнения столбцов, которые указываются внутри кружочков для отвечаюнщх им цепей, заранее определены).

Дополнения при этом должны браться согласованно: биты всех столбцов таблиц истинности, соответствуюнще одной и той же цепи схемы, должны либо инвертироваться, либо оставаться теми же, что и были. Это достигается выбором битов дополнений случайно и независимо для каждой соответствуюшей цепи. (Для простоты мы никогда не инвертируем выход результируго-шего вентиля.) Па рис. 6.3 на стр. 104 приведен результат некоторых случайных перестановок и дополнений столбцов в таблицах истинности для нашей исходной схемы, изображенной на рис. 6.1.

После того как с проверяемой схемой сделано то же самое, что в результате в качестве примера показано на рис. 6.3, Алиса принимает ее в качестве обязательства: для каждого бита табли-

Рис. 6.3. Схема с перетасованными таблицами истинности

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

Задача А. Алиса должна открыть все без исключения блобы, которые она только что приняла в качестве обязательств. Более того,- она должна также показать все биты допол-

нений, которые использовались ею в процессе перетасовывания. Продолжая наше предыдущее образное представление, Алиса, для того чтобы продемонстрировать Бобу свой эквивалент схемы, вроде той, что изображена на рис. 6.3, должна отклеить все заклеенные ею места. Это позволяет Бобу проверить, что информация, которая была скрыта посредством блоба, соответствует правильным перестановкам и дополнениям таблицы истинности проверяемой булевой схемы.

Задача В. Алиса открывает только блобы, которые соответствуют одной строке в каждой таблице истинности. Строки, которые должны открываться, будут в точности такими же, как те, что обведены на рис. 6.1, но, возможно, с новым расположением, которое определяется перестановкой строк. По-прежнему, как бы продолжая наше образное представление, Алиса должна выборочно отклеить кусочки липкой ленты, чтобы показать Бобу часть схемы, которая соответствует той, что изображена на рис. 6.4 на стр. 106. Это предоставляет ему возможность проверить согласованность каждой цепи и то, что значением выхода всей проверяемой схемы действительно является 1.

Для того чтобы можно было доказать корректность приведенного протокола, должны удовлетворяться три требования. В предположении, что выполнены только те четыре свойства, которыми определяются блобы (см.§ 2), в [78] доказано, что за исключением, возможным, разве что, с экспоненциально малой вероятностью, справедливо следующее:

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

2) Если Алиса не знает выполнимого присваивания для Ф, то к каким бы уловкам во время протокола она не прибегала, чтобы убедить Боба в своей правоте. Боб всегда сможет уличить ее в мошенничестве.