monitoring citizens actions, opinions, доходы и объединения.

Не ясно, не будет ли через 20 лет продажа системы с условным вручением ключей Турции или Китаю пох о-дить на продажу электрических дубинок Южной Африке в 1970 году или на строительство химического завода в Ираке в 1980 году. Даже хуже, легкое и незаметное подслушивание линий связи может искусить многие пр а-вительства, которые раньше, возможно, этим и не занимались, следить за корреспонденцией своих граждан . И нет гарантии, что либеральные демократии устоят перед подобным искушением .

Глава 5

Развитые протоколы

5.1 Доказательства с нулевым знанием

А вот другая история:

Алиса:

Боб:

"Я знаю пароль компьютера Федеральной Резервной Системы, компоненты секретного соуса МакДональдс и оде ржание 4-го тома Дональда Кнута".

"Нет, ты не знаешь".

Алиса: "Нет, я знаю".

Боб:

"Не знаешь".

Алиса: "Нет, знаю".

Боб: "Докажи". Алиса: "Хорошо, я скажу тебе". Она шепчет Бобу на ухо.

Боб: "Это интересно. Теперь я тоже это знаю и собираюсь рассказать это все Вашингтон Поет". Алиса: "Оооой".

К несчастью, обычно Алиса может доказать что-нибудь Бобу, только рассказав ему все. Но тогда он тоже получит все сведения. Затем Боб может выложить полученные сведения кому угодно, и Алиса ничего не сможет с этим поделать. (В литературе для описания этих протоколов часто используются различные персонажи . Пегги обычно доказывает, а Виктор проверяет. Именно эти имена появляются в используемых примерах вместо Ал и-сы и Боба.)

Используя однонаправленные функции, Пегги сможет провести доказательство с нулевым знанием [626]. Этот протокол доказывает Виктору, что у Пегги действительно есть информация, но не дает Виктору не мале й-шей возможности узнать, что это за информация .

Эти доказательства принимают форму интерактивного протокола. Виктор задает Пегги ряд вопросов. Если Пегги знает секрет, то она ответит на все вопросы правильно. Если секрет ей неизвестен, у нее есть некоторая вероятность - 50 процентов в следующих примерах - ответить правильно . После примерно 10 вопросов Виктор убедится, что Пегги знает секрет. Но ни один из вопросов или ответов не даст Виктору ни малейших сведений об информации Пегги, но докажет знание Пегги этой информации .

Базовый протокол с нулевым знанием

Жан-Жак Кискатер (Jean-Jacques Quisquater) и Луи Гилу (Louis Guillou) поясняют нулевое знание историей о пещере [1281]. У пещеры, показанной на 4-й, есть секрет. Тот, кто знает волшебные слова может открыть потайную дверь между C и D. Для всех остальных оба прохода ведут в тупик.

Рис. 5-1. Пещера нулевого знания

Пегги знает секрет пещеры. Она хочет доказать свое знание Виктору, но не хочет раскрывать волшебных слов. Вот как она убеждает его:

(1) Виктор находится в точке А.

(2) Пегги проходит весь путь по пещере, либо до точки C, либо до точки D.

(3) После того, как Пегги исчезнет в пещере, Виктор переходит в точку В.

(4) Виктор кричит Пегги, спрашивая ее либо о:

(a) или выйти из левого прохода

(b) выйти из правого прохода.

(5) Пегги исполняет его просьбу, при необходимости используя волшебные слова, чтобы отпереть дверь.

(6) Пегги и Виктор повторяют этапы (1) - (5) n раз.

Предположим, что у Виктора есть видеокамера, и он записывает все, что видит . Он записывает, как Пегги исчезает в пещере, записывает, как он сам кричит, указывая, где Пегги должна появиться, записывает как Пегги появляется. Он записывает все n тестов. Если он покажет эту видеозапись Кэрол, поверит ли она, что Пегги зн а-ет волшебные слова, отпирающие дверь? Нет. А что если Пегги и Виктор заранее договорились, что Виктор будет кричать, а Пегги будет делать вид, что она прошла весь путь. Тогда она будет каждый раз выходить из указанного Виктором места, не зная волшебных слов. Или они могли сделать по другому. Пегги входит в один из проходов и Виктор случайным образом выкрикивает свои просьбы . Если Виктор угадывает правильно, хорошо, если нет - они вырежут эту попытку из видеозаписи . В любом случае Виктор может получить видеозапись, показывающую в точности ту последовательность, которая получилась бы, если бы Пегги знала волше б-ные слова.

Этот опыт показывает две вещи. Во первых, Виктор не может убедить третью сторону в правильности док а-зательства. И во вторых, данный протокол является протоколом с нулевым знанием . Если Пегги не знает волшебных слов, то очевидно, что Виктор не узнает ничего из просмотра видеозаписи . Но так как нет способа отличить реальную видеозапись от подделанной, то Виктор не может ничего узнать из реального доказательства -это и есть нулевое знание.

Методика, используемая в этом протоколе, называется разрезать и выбрать из-за того, что она похож на классический протокол честного деления чего-либо :

(1) Алиса делит некую вещь пополам.

(2) Боб выбирает одну из половин себе.

(3) Алиса забирает оставшуюся половину.

В интересах Алисы честно разделить на этапе (1), потому что Боб выберет на этапе (2) ту половину, которая ему больше нравится. Майкл Рабин (Michael Rabin) первым использовал в криптографии технику "разрезать и выбрать" [1282]. Понятия интерактивного протокола и нулевого знания б1ли формализованы позже [626,

627].

Протокол "разрезать и выбрать" работает, потому что Пегги не может несколько раз подряд угадывать, отк уда Виктор попросит ее выйти. Если Пегги не знает секрета, он может выйти только из того прохода, в который она зашла. В каждом раундепротокола ее вероятность (иногда называемая аккредитацией) угадать, с какой стороны Виктор попросит ее выйти, составляет 50 процентов , поэтому ее вероятность обмануть Виктора также равна 50 процентам. Вероятность обмануть его в двух раундах составит 25 процентов , а во всех n раундах -один шанс из 2n. После 16 раундов у Пегги 1 шанс из 65536 обмануть Виктора. Виктор может уверенно предположить, что если все 16 доказательств Пегги правильны, то она действительно знает тайные слова, открыва ю-щие дверь между точками C и D. (Аналогия с пещерой несовершенна. Пегги может просто входить с одной стороны и выходить с другой, протокол "разрезать и выбрать" не нужен . Однако, он необходим с для нулевого знания с математической точки зрения.)

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

(1) Пегги использует свою информацию и случайное число для преобразования одной трудной проблемы в другую, изоморфную оригинальной проблеме . Затем она использует свою информацию и случайное число для решения новой трудной проблемы.

(2) Пегги вручает решение новой проблемы, используя схему вручения бита.

(3) Пегги раскрывает Виктору новый экземпляр проблемы. Виктор не может использовать эту новую пробл ему для получения информации о первоначальной проблеме или ее решении.

(4) Виктор просит Пегги либо

(a) доказать ему, что новая и старая проблема изоморфны (т.е., два различных решения для двух св я-занных проблем), либо

(b) открыть решение, полученное на этапе (2) и доказать, что это решение новой проблемы.