5.1 Доказательства с нулевым знанием
А вот другая история:
Алиса: "Я знаю пароль компьютера Федеральной Резервной Системы, компоненты секретного соуса Макдональдс и оде р-жание 4-го тома Дональда Кнута".
Боб: "Нет, ты не знаешь".
Алиса: "Нет, я знаю".
Боб: "Не знаешь".
Алиса: "Нет, знаю".
Боб: "Докажи".
Алиса: "Хорошо, я скажу тебе". Она шепчет Бобу на ухо.
Боб: "Это интересно. Теперь я тоже это знаю и собираюсь рассказать это все Вашингтон Пост".
Алиса: "Оооой".
К несчастью, обычно Алиса может доказать что-нибудь Бобу, только рассказав ему все. Но тогда он тоже получит все сведения. Затем Боб может выложить полученные сведения кому угодно, и Алиса ничего не сможет с этим поделать. (В литературе для описания этих протоколов часто используются различные персонажи . Пегги обычно доказывает, а Виктор проверяет. Именно эти имена появляются в используемых примерах вместо Ал и-сы и Боба.)
Используя однонаправленные функции, Пегги сможет провести доказательство с нулевым знанием[626]. Этот протокол доказывает Виктору, что у Пегги действительно есть информация, но не дает Виктору не мале й-шей возможности узнать, что это за информация.
Эти доказательства принимают форму интерактивного протокола. Виктор задает Пегги ряд вопросов. Если Пегги знает секрет, то она ответит на все вопросы правильно. Если секрет ей неизвестен, у нее есть некоторая вероятность - 50 процентов в следующих примерах - ответить правильно . После примерно 10 вопросов Виктор убедится, что Пегги знает секрет. Но ни один из вопросов или ответов не даст Виктору ни малейших сведений об информации Пегги, но докажет знание Пегги этой информации .
Базовый протокол с нулевым знанием
Жан-Жак Кискатер (Jean-Jacques Quisquater) и Луи Гилу (Louis Guillou) поясняют нулевое знание историей о пещере [1281]. У пещеры, показанной на 4-й, есть секрет. Тот, кто знает волшебные слова может открыть потайную дверь между С и D. Для всех остальных оба прохода ведут в тупик.
| А | |||||
| B | |||||
| C D | |||||