Так как Боб прекращает игру при первом же неправильном ответе, вероятность обмана при Ь реализациях протокола не превосходит . Представленный протокол реализует доказательство с нулевым знанием. Чтобы доказать, что Боб не получает никаких знаний в ходе. Рассмотрим вначале второй вопрос Боба В ответ на этот вопрос он получает граф, изоморфный графу С Но он сам мог строить сколько угодно изоморфных графов, и то, что присылает ему Алиса, это просто один из них. Случай с первым вопросом не столь очевиден. В ответ на первый вопрос Боб получает гамильтонов цикл в графе, изоморфном графу С На первый взгляд может показаться, что это дает Бобу какую. Однако это не так. Заметим, что если в б есть гамильтонов цикл, то при некоторой нумерации вершин существует . Криптографические протоколы изоморфный граф, который задается матрицей смежности вида . при такой нумерации гамильтонов цикл проходит через вершины в порядке возрастания номеров. Изменяя нумерацию вершин, Боб может получать из . Когда Алиса, отвечая на его первый вопрос, открывает гамильтонов цикл, Боб видит как раз одну из таких матриц. Таким образом, Боб не получает от Алисы никакой информации, которую он не мог бы получить сам. Возьмем в качестве основного граф . Его матрица смежности имеет вид . Алиса выбирает некоторую случайную нумерацию вершин, скажем, . Доказательства с нулевым знанием . В рамках данного примера просто припишем слева к каждому элементу матрицы выбираемую случайно с равными вероятностями цифру из множества . Криптографические протоколы Это объясняется тем, что, во. Если он просит доказать изоморфизм графов, то Алиса просто посылает ему кодированную матрицу Я и использованную нумерацию . Боб проверяет соответствие матрицы Я матрице . Из матрицы Я Боб получает граф Я . Затем он переставляет вершины графа . Если Боб просит показать ему гамильтонов цикл, то Алиса посылает ему соответствующий список . Каждый элемент содержит номера вершин и код ребра. Боб проверяет соответствие указанных в списке ребер матрице . Затем он убеждается, что указанный в списке путь проходит через все вершины графа по одному разу. Электронные деньги Во многих странах люди оплачивают покупки при помощи электронных карточек, заказывают авиабилеты через Интернет, покупают самые разнообразные товары в Интернет. Сведения о покупках накапливаются в магазинах и банках. Поэтому появилась новая проблема, иногда называемая . Суть проблемы состоит в том, что исчезает анонимность процесса покупки, т. информация о покупках любого человека может стать известной третьим лицам и использоваться против него. Например, сведения о покупке билета на поезд или самолет могут представлять интерес для преступников, информация о закупках алкогольных напитков политическим деятелем может быть использована против него его противниками и т. Поэтому возникла идея разработать такие схемы электронных платежей, которые сохраняли. Такие протоколы называются электронными или цифровыми деньгами . Некоторые схемы уже используются в реальной жизни. Описываемая ниже схема была предложена Д. Мы рассмотрим две . Вначале дадим более точную постановку задачи. Покупатель и магазин имеют соответствующие счета в банке, и покупатель хочет купить некоторый товар в магазине. Покупка осуществляется в виде трехступенчатого процесса. Наша цель — разработать такую схему, чтобы . была сохранена анонимность обычных денег. Банк имеет следующую информацию. Банк вычисляет число . Криптографические протоколы и формирует банкноту . Никто не может подделать подпись, так как число с секретно. Покупатель предъявляет банкноту . Магазин отправляет эту банкноту в банк для проверки. Прежде всего, банк проверяет правильность подписи . Но кроме этого банк хранит все номера возвратившихся к нему банкнот и проверяет, нет ли числа п в этом списке. Если п есть в списке, то платеж не принимается . Если же все проверки прошли успешно, то банк добавляет . Недостаток этой схемы — отсутствует анонимность. Банк, а также все, кто имеет доступ к открытым линиям связи, могут запомнить, какому покупателю соответствует число п, и тем самым выяснить, кто купил товар. Эта схема базируется на так называемой . Снова покупатель хочет купить товар. Затем он генерирует случайное число г, взаимно простое с . Банк вычисляет число . Покупатель находит число . мы получили подпись банка к п . Таким образом, покупатель имеет число п, которое никому не известно и никогда не передавалось по каналам связи, и подпись банка . Но теперь никто не знает, кому соответствует эта банкнота, т. она стала анонимной, как обычная бумажная банкнота. Действия магазина и банка после предъявления покупателем банкноты . Почему же данная схема плохая. Тогда он легко сможет изготовить фальшивую банкноту . Действительно, пз — . В одном варианте такой схемы используется некоторая односторонняя функция . Криптографические протоколы Банкнота теперь определяется как пара чисел . Покупатель генерирует п . Эта банкнота обладает всеми хорошими свойствами, как и во второй схеме, в то же время подделать такую банкноту невозможно, так как невозможно вычислить . Заметим, что при выборе односторонней функции нужно проявлять осторожность. Читатель может проверить, что банкноты, созданные с использованием такой функции, будут по. На практике в качестве . Все остальные действия магазина и банка остаются такими же, как и в ранее описанных схемах. Есть еще один, более простой, способ борьбы с мультипликативным свойством системы . Допустим, что длина модуля . Такой же может быть и длина числа п. Это фиксированное число может нести полезную информацию, такую, как номинал банкноты и наименование банка . Теперь банк при предъявлении ему банкноты будет обязательно проверять наличие фиксированного заголовка в параметре . Вероятность того, что при перемножении двух чисел по модулю . Поэтому получить фальшивую банкноту по формуле . Пусть в качестве секретных параметров банка выбраны числа Р .