§> й ф

•<5>-

Рис. 6.4. Демонстрация существовалия выполнимого присвалвалия

3) Если Алиса знает некоторое выполнимое присваивание для Ф, и если она в соответствии с данным присваиванием неукоснительно следует своей части протокола, то в ходе его она не предоставит Бобу никакой информации, которая могла бы помочь ему определить ни это конкретное, ни какое-то другое выполнимое присваивание (ил1 хотя бы какую-то частичную информацию о нем). Все это остается справедливым даже тогда, когда Боб произвольно отклоняется от поведения, предписанного ему протоколом.

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

чтобы принять блобы в качестве обязательства. В таком случае Бобу может быть доступна некоторая информация, которую он не в состоянии получить .самостоятельно, хотя она и не будет иметь отношения к выполнимому присваиванию. Иными словами, наш протокол - это протокол с минимальным раскрытием, но он может и не быть протоколом с «нулевым знанием» в терминологии [199].

Интуитивно ясно, что некий протокол будет протоколом с нулевым знанием, если третье требование, которому он должен удовлетворять, усилить до такого, согласно которому Боб в ходе протокола не может выяснить вообше ничего, кроме того, что Алисе известно выполнимое присваивание. Точнее, Боб должен быть в состоянии воспроизвести полностью свой диалог с Алисой фактически без какого бы то ни было разговора с ней. За формальным определением такого протокола обращайтесь к [199].

Однако и наш протокол будет протоколом с нулевым знанием, если в нем свойство 4, определяющее блоб (см. § 2), усилить так, чтобы быть уверенным, что Боб не извлечет ничего из того процесса, согласно которому Алиса принимает блобы в качестве обязательств, а также что Боб получит только биты, определяющиеся ходом того процесса, в соответствии с которым Алиса открывает ему некоторые из них. Следуя технике доказательства Шафи Гольдвассер, Сильвио Микэли и Чарльза Ракова из [199], будем говорить, что блобы являются моделируемыми, если, в дополнение к свойствам 1, 2 и 3, они удовлетворяют свойству

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

Заметим, что все реализации блобов, описанные в § 2, являются моделируемыми.

Если в теоретико-информационном смысле невозможно различить блобы, которые используются Алисой для того, чтобы принять их в качестве обязательства О, и блобы, которые используются для того, чтобы принять их в качестве обязательства 1,

и если эти блобы являются моделируемыми, то описанный выше интерактивный протокол для выполнимости булевых выражений становится совершенным протоколом с нулевыми знаниями в терминологии [196]. Это достигается, например, если он использует в качестве блобов те, что основаны на сложности задачи дискретного логарифмирования, и являются первыми из тех, что описаны в § 2. Заметим, что такие блобы не соответствуют модели [199], так как бесконечные вычислительные ресурсы доказывающего могут помочь ему смошенничать, что объясняет, почему результат Фортноу [177] в этом случае становится неприменимым. (Здесь хотелось бы обратить ваше внимание на то, что совершенный интерактивный протокол с нулевыми знаниями для задачи о выполнимости в [79] определен некорректно.)

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

Предположим для простоты, что блобы - это битовые строки и что Алиса задается некоторым блобом, показывая его явно. Рассмотрим следующую стратегию для Боба: после получения от Алисы блобов, которые соответствуют всем к схемам со случайно переставленными строками и инвертированными столбцами таблиц истинности, он объединяет эти блобы вместе (конкатенируя их в одну строку) и использует полученный результат в качестве аргумента некоторой однонаправленной функции. Затем он использует первые к битов значения этой функции для определения к проверочных вопросов, которые будет ей задавать. Даже если проведение этого модифицированного протокола с Алисой и не помогает Бобу узнать что-либо о ее секрете, сама запись его может помочь ему убедить кого-нибудь еще в существовании этого секрета, поскольку Боб почти наверняка не сможет воспроизвести такую запись каким-то другим способом (даже если блобы являются моделируемыми). Это приводит к любопытному феномену: запись параллельной версии протокола может не содержать никакой информации о действительном