том, что доказательство ей известно, пренебрежимо малы.

2. Виктор не может обмануть Пегги. Он не получает ни малейшего намека на доказательство кроме того факта, что доказательство известно Пегги. В частности, Виктор не может продемонстрировать доказ а-тельство никому другому, не доказав все сам с самого начала.

у доказательств с нулевым знанием есть дополнительное условие :

3. Виктор не узнает от Пегги ничего такого, чего он не смог бы узнать и самостоятельно кроме того фа к-та, что доказательство известно Пегги.

Существует заметная математическая разница между доказательствами с минимальным раскрытием и док а-зательствами с нулевым знанием. Это различие находится вне рамок данной книги, но более искушенные чит а-тели могут проштудировать другую литературу. Понятия изложены в in [626, 619, 622]. Дальнейшая проработка этих идей, основанная на различных математических предположениях, выполнена в [240, 319, 239].

Существуют различные типы доказательств с нулевым знанием :

- Совершенное. Существует имитатор, который создает стенограммы, полностью соответствующие реал ь-ным стенограммам (примеры с гамильтоновым ци клом и изоморфизмом графов).

- Статистическое. Существует имитатор, который создает стенограммы, полностью соответствующие р е-альным стенограммам, кроме фиксированного числа исключений.

- Вычислительное. Существует имитатор, который создает стенограммы, неотличимые от реальных.

- Неиспользующее. Имитатора может и не быть, но мы можем доказать, что Виктор не узнает никакой информации из доказательства (параллельный пример)

Годы тяжелой работы, как теоретической, так и прикладной, присели к появлению доказательств с мин и-мальным раскрытием и нулевым знанием. Майк Берместер (Mike Burmester) и Иво Десмедт изобрели широковещательно интерактивное доказательство, где владелец секрета может широковещательно передавать большой группе контролеров интерактивное доказательство с нулевым знанием [280]. Криптографы доказали, что все, что может быть доказано с помощью интерактивного доказательства, может быть доказано и с помощью инт е-рактивного доказательства с нулевым знанием [753, 137].

Хорошей обзорной статьей по данной теме является [548]. Дополнительные математические подробности,

варианты, протоколы и приложения ищите в [590, 619, 240, 319, 620, 113,241, 152, 8, 660, 238, 591, 617, 510,

592, 214, 104, 216, 832, 97, 939, 622, 482, 615, 618, 215, 476, 71]. Много чего б1ло написано по этому вопросу.

5.2 Использование доказательства с нулевым знанием для идентификации

В реальном мире для доказательств подлинности часто используются физические символы: паспорта, вод и-тельские права, кредитные карточки и т.д. Эти символы содержат что-то, связывающее их с конкретным чел о-веком: обычно фотографию или подпись, но с той же вероятностью это может быть отпечаток пальца, снимок сетчатки глаза или рентгеновский снимок челюсти . Как было бы здорово делать что-то подобное цифровым образом?

Использовать доказательства с нулевым знанием для доказательства идентичности было впервые предлож е-но Уриелем Файгом (Uriel Feige), Амосом Фиатом (Amos Fiat) и Ади Шамиром [566, 567]. Закрытый ключ Алисы становится функцией ее "идентичности" . Используя доказательство с нулевым знанием, она доказывает, что она знает свой закрытый ключ и, таким образом, свою идентичность . Соответствующие алгоритмы можно найти в разделе 23.11 .

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

Проблема гроссмейстера

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

Карпов, играя белыми, делает свой ход первым . Алиса записывает ход и идет в комнату к Каспарову. Играя белыми, она делает тот же ход на доске Каспарова. Каспаров делает свой первый ход черными. Алиса запис ы-вает ход, идет в комнату к Карпову и делает тот же ход. Это продолжается, пока она не выигрывает одну из партий, проигрывая другую, или обе партии кончаются вничью .

На самом деле Каспаров играет с Карповым, а Алиса просто посредник, повторяющий ходы одного грос с-

мейстера на доске другого. Однако, если Карпов и Каспаров не знают о присутствии друг друга, каждый из них будет поражен игрой Алисы.

Этот способ мошенничества может быть использовать против доказательства личности с нулевым знанием [485, 120]. Когда Алиса доказывает свою личность Мэллори, Мэллори может одновременно доказать Бобу, что он-то и есть Алиса.

Обман, выполненный мафией

Обсуждая свой протокол идентификации с нулевым знанием, Ади Шамир сказал [1424]: "Я могу ходить в принадлежащий мафии магазин хоть миллион раз подряд, а они все еще не смогут выдать себя за меня ."

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

Когда Алиса поела и собралась платить и доказывать свою личность Бобу, Боб подает сигнал Кэрол, что п о-ра начинать. Кэрол выбирает бриллианты подороже и собирается доказывать свою личность Дэйву . Теперь, пока Алиса доказывает свою личность Бобу, тот подает сигнал Кэрол, и та выполняет тот же протокол с Дэйвом. Когда Дэйв задает вопрос по протоколу, Кэрол сообщает этот вопрос Бобу, а Боб задает его Алисе . Когда Алиса отвечает, Боб передает правильный ответ Кэрол. По сути, Алиса просто доказывает свою личность Дэйву, а Боб и Кэрол просто, находясь внутри протокола, передают сообщения туда-сюда . Когда протокол завершается, Алиса доказала свою личность Дэйву и заплатила за дорогие бриллианты (с которыми Кэрол теперь и исчезнет).

Обман, выполненный террористами

Если Алиса хочет объединиться с Кэрол, то они также могут провести Дэйва. В этом протоколе Кэрол - и з-вестная террористка. Алиса помогает ей въехать в страну. Дэйв - офицер-пограничник, Алиса и Кэрол общаются по тайному радиоканалу.

Когда Дэйв задает Кэрол вопросы в соответствии по протоколу с нулевым знанием, Кэрол передает их Ал и-се, которая и отвечает на вопросы. Кэрол повторяет эти ответы Дэйву. Carol recites these answers to Dave. По сути, Свою личность Дэйву доказывает Алиса, а Кэрол выступает в роли линии связи . Когда протокол завершается, Дэйв считает, что Кэрол - это Алиса, и разрешает ей въехать в страну . Спустя три дня Кэрол всплывает у правительственного здания вместе с микроавтобусом, набитом взрывчаткой .

Предлагаемые решения

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

Тотас Бот (Thomas Both) и Иво Десмедт предложили другое решение, использующее точные часы [148]. Если каждый этап протокола должен происходить в заданное время, у мошенников не останется времени для о б-мена информацией. В случае с проблемой гроссмейстера это соответствует предложению ограничить время о б-думывания хода одной минутой - у Алисы не останется времени бегать из комнаты в комнату . В истории с мафией у Боб и Кэрол не хватит времени передавать друг другу ответы и вопросы .

Обман с несколькими личностями

Существуют и другие способы злоупотребить доказательствами идентичности с нулевым знанием, также рассматриваемые в [485, 120]. В ряде реализаций проверка при регистрации человеком своего ключа не прои з-водится. Следовательно, у Алисы может быть несколько закрытых ключей и, таким образом, несколько личн остей. Это может здорово помочь ей, если она захочет мошенничать с налогами . Алиса также может совершить преступление и скрыться. В первых, она создает несколько личностей, одна из которых не используется . Затем, она использует эту личность для совершения преступления так, чтобы свидетель идентифицировал ее как эту личность. Затем, она немедленно прекращает пользоваться этой личностью . Свидетель знает личность преступника, но Алиса никогда больше не будет использовать эту личность - ее невозможно проследить .

Для защиты от этого нужны механизмы, обеспечивающие, чтобы у каждого человека была только одна ли ч-ность. В [120] авторами предлагается причудливая идея защищенных от воровства детей, которые не могут быть клонированы, и у которых есть уникальный номер, являющийся частью их генетического кода . Они также предложили присваивать каждому ребенку личность при рождении . (Действительно, родителям придется сде-

лать это, так как иначе ребенок может быть украден .) Этим тоже легко злоупотребить - родители могут создать для родившегося ребенка несколько личностей . В конце концов, уникальность личности основана на доверии .

Прокат паспортов

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

Кэрол получает не только плату за свою личность, но и идеальное алиби. Она совершает преступление, пока Алиса находится в Заире. "Кэрол" доказала свою личность в Заире, как она могла совершить преступление д ома?

Конечно, развязаны руки и у Алисы. Она может совершить преступление либо перед отъездом, либо сразу же после возвращения, около дома Кэрол. Сначала она покажет, что она - Кэрол (имея закрытый ключ Кэрол, ей не составит труда сделать это), затем она совершит преступление и убежит. Полиция будет искать Кэрол . Кэрол будет утверждать, что сдала свою личность напрокат Алисе, но кто поверит в такую невероятную ист о-рию?

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

Доказательство членства

Алиса хочет доказать Бобу, что она является членом суперсекретной организации, но не хочет раскрывать свою личность. Эта проблема, близкая проблеме доказательства личности, но отличающаяся от нее, была из учена в [887, 906, 907, 1201, 1445]. Ряд решений связан с проблемой групповых подписей (см. раздел 4.6).

5.3 Слепые подписи

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

Мы можем пожелать, чтобы люди подписывали документы, даже не зная их содержания . Существуют способы, когда подписывающий может не точно, но почти знать, что он подписывает. Но все по порядку.

Полностью слепые подписи

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

(1) Алиса берет документ и умножает его на случайное число. Это случайное число называется маскирующим множителем.

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

(3) Боб подписывает замаскированный документ.

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

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

Может ли боб смошенничать? Может ли он получить какую-нибудь информацию о том, что пописывает? Если множитель осторожности действительно случаен и делает замаскированный документ действительно сл у-чайным, то нет. Замаскированный документ, подписываемый Бобом на этапе, (2) ничем не похож на ориг и-нальный документ Алисы. Замаскированный документ с подписью Боба на нем на этапе (3) ничем не похож на подписанный документ этапа (4). Даже если Боб заполучит документ со своей подписью после окончания пр о-токола, он не сможет доказать (себе или кому-то другому), что он подписал его в этом конкретном протоколе . Он знает, что его подпись правильна. Он может, как и любой другой, проверить свою подпись . Однако, у него нет никакой возможности связать подписанный документ и любую информацию, полученную при выполнении протокола. Если он подписал, используя этот протокол, миллион документов, у него не будет способа узнать когда какой документ он подписал. Полностью слепые подписи обладают следующими свойствами: