Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
Задача В. Алиса открывает только блобы, которые соответствуют одной строке в каждой таблице истинности. Строки, которые должны открываться, будут в точности такими же, как те, что обведены на рис. 6.1, но, возможно, с новым расположением, которое определяется перестановкой строк. По-прежнему, как бы продолжая наше образное представление, Алиса должна выборочно отклеить кусочки липкой ленты, чтобы показать Бобу часть схемы, которая соответствует той, что изображена на рис. 6.4 на стр. 106. Это предоставляет ему возможность проверить согласованность каждой цепи и то, что значением выхода всей проверяемой схемы действительно является 1.
Для того чтобы можно было доказать корректность приведенного протокола, должны удовлетворяться три требования. В предположении, что выполнены только те четыре свойства, которыми определяются блобы (см.§ 2), в [78] доказано, что за исключением, возможным, разве что, с экспоненциально малой вероятностью, справедливо следующее:
1) Алиса может довести до конца свою часть протокола при условии, что она знает выполнимое присваивание для Ф. (Конечно, никакой протокол не сможет заставить Боба удостовериться в честности Алисы, даже если та сообщит ему выполнимое присваивание в явном виде, поскольку он всегда может отказаться ее слушать.)
2) Если Алиса не знает выполнимого присваивания для Ф, то к каким бы уловкам во время протокола она не прибегала, чтобы убедить Боба в своей правоте, Боб всегда сможет уличить ее в мошенничестве.
106 Применения
Глава 6
Рис. 6.4. Демонстрация существования выполнимого присваивания
3) Если Алиса знает некоторое выполнимое присваивание для Ф, и если она в соответствии с данным присваиванием неукоснительно следует своей части протокола, то в ходе его она не предоставит Бобу никакой информации, которая могла бы помочь ему определить ни это конкретное, ни какое-то другое выполнимое присваивание (или хотя бы какую-то частичную информацию о нем). Все это остается справедливым даже тогда, когда Боб произвольно отклоняется от поведения, предписанного ему протоколом.
Несмотря на то, что в нашем протоколе третье требование удовлетворяется, из этого, вообще говоря, не следует, что Боб не может получить какую-нибудь дополнительную информацию, кроме того факта, что Алиса действительно знает выполнимое присваивание для Ф. Например, возможно, что только Алиса владеет технологией и знаниями, которые необходимы для того,
S3
Доказательства с наименьшим раскрытие^ 107
чтобы принять блобы в качестве обязательства. В таком случае Бобу может быть доступна некоторая информация, которую он не в состоянии получить „самостоятельно, хотя она и не будет иметь отношения к выполнимому присваиванию. Иными словами, наш протокол — это протокол с минимальным раскрытием, но он может и не быть протоколом с «нулевым знанием» в терминологии [199].
Интуитивно ясно, что некий протокол будет протоколом с нулевым знанием, если третье требование, которому он должен удовлетворять, усилить до такого, согласно которому Боб в ходе протокола не может выяснить вообще ничего, кроме того, что Алисе известно выполнимое присваивание. Точнее, Боб должен быть в состоянии воспроизвести полностью свой диалог с Алисой фактически без какого бы то ни было разговора с ней. За формальным определением такого протокола обращайтесь к [199].
Однако и наш протокол будет протоколом с нулевым знанием, если в нем свойство 4, определяющее блоб (см. § 2), усилить так, чтобы быть уверенным, что Боб не извлечет ничего из того процесса, согласно которому Алиса принимает блобы в качестве обязательств, а также что Боб получит только биты, определяющиеся ходом того процесса, в соответствии с которым Алиса открывает ему некоторые из них. Следуя технике доказательства Шафи Гольдвассер, Сильвио Микэли и Чарльза Ракова из [199], будем говорить, что блобы являются моделируемыми, если, в дополнение к свойствам 1, 2 и 3, они удовлетворяют свойству
4') Боб может смоделировать то, что должно быть обеспечено им в результате процесса принятия Алисой в качестве обязательств блобов, которые она может открыть как 0, и блобов, которые она может открыть как 1. Боб в состоянии также смоделировать процесс, посредством которого Алиса будет открывать блобы, принятые ею в качестве обязательств.
Заметим, что все реализации блобов, описанные в § 2, являются моделируемыми.
Если в теоретико-информационном смысле невозможно различить блобы, которые используются Алисой для того, чтобы принять их в качестве обязательства 0, и блобы, которые используются для того, чтобы принять их в качестве обязательства 1,
108 Применения
Глава 6
и если эти блобы являются моделируемыми, то описанный выше интерактивный протокол для выполнимости булевых выражений становится совершенным протоколом с нулевыми знаниями в терминологии [196]. Это достигается, например, если он использует в качестве блобов те, что основаны на сложности задачи дискретного логарифмирования, и являются первыми из тех, что описаны в § 2. Заметим, что такие блобы не соответствуют модели [199], так как бесконечные вычислительные ресурсы доказывающего могут помочь ему смошенничать, что объясняет, почему результат Фортноу [177] в этом случае становится неприменимым. (Здесь хотелось бы обратить ваше внимание на то, что совершенный интерактивный протокол с нулевыми знаниями для задачи о выполнимости в [79] определен некорректно.)
