Как читать эту книгу 11 страница

(2) Пегги посылает Н Виктору.

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

(a) доказать, что Н и G₁ изоморфны, либо

(b) доказать, что Н и G₂ изоморфны.

(4) Пегги исполняет его просьбу. Она либо:

(a) доказывает, что Н и G₁ изоморфны, не доказывая, что Н и G₂ изоморфны, либо

(b) доказывает, что Н и G₂ изоморфны, не доказывая, что Н и G₁ изоморфны.

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

Если Пегги не знает об изоморфизме между G₁ и G₂, она не сможет создать граф Н, изоморфный обоим графам. Она может создать либо граф, который изоморфен G₁, либо граф, который изоморфен G₂. Как и в предыдущем примере у нее только 50 шансов из 100 угадать, какое доказательство потребует от нее Виктор на этапе (3).

Этот протокол не дает Виктору никакой полезной информации, помогающей ему из ответов Пегги установить изоморфизм между G₁ и G₂. Так как Пегги для каждого нового раунда протокола генерирует новый граф Н, Виктор не сможет получить информацию независимо от того, из скольких раундов будет состоять их протокол. Он не сможет из ответов Пегги установить изоморфизм между G₁ и G₂.

В каждом раунде Виктор получает новое случайное преобразование Н, вместе с изоморфизмом между Н и G₁ или G₂. Виктор может также создать что-то подобное самостоятельно. Так как Виктор может создать имитацию протокола, это действительно доказательство с нулевым знанием.

Гамильтоновы циклы

Вариант этого примера был впервые представлен Мануэлем Блюмом (Manuel Blum) [196]. Пегги знает кружной, продолжительный путь вдоль линий графа, который проходит через каждую точку только один раз. Этот путь называется гамильтоновым циклом. Поиск гамильтонова цикла является другой тяжелой задачей. У Пегги есть эта информация - она, возможно, получила ее создав граф с конкретным гамильтоновым циклом - и она хочет доказать Виктору, что эта информация ей известна.

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

(1) Пегги случайным образом преобразовывает G. Она передвигает точки и изменяет их метки, создавая новый граф, H. Поскольку G и Hтопологически изоморфны (т.е., это один и тот же граф), если ей известен гамильтонов цикл G, то она легко может найти гамильтонов цикл H. Если она не сама создает H, определение изоморфизма между двумя графами будет являться другой сложной проблемой, решение которой также потребует веков компьютерного времени. Затем она шифрует H, получая H'. (Должно использоваться вероятностное шифрование каждой строчки H, то есть, шифрованный 0 или шифрованная 1 для каждой линии H.)

(2) Пегги передает Виктору копию H.

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

(a) доказать ему, что Н' - это зашифрованная изоморфная копия G, либо

(b) показать ему гамильтонов цикл для Н.

(4) Пегги исполняет его просьбу. Она либо:

(a) доказывает, что Н' - это зашифрованная изоморфная копия G, раскрывая преобразования и расшифровывая все, не показывая гамильтонов цикл для G или Н, либо

(b) показывает гамильтонов цикл для Н, расшифровывая только те строки, которые образуют гамильтонов цикл, не доказывая, что Н и G топологически изоморфны.

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

Если Пегги не обманывает, она сможет предъявить Виктору одно из доказательств на этапе (3). Однако, если гамильтонов цикл для G ей неизвестен, она не сможет создать зашифрованный граф H', который удовлетворяет обоим доказательствам. Лучшее, что она может сделать - это создать или граф, изоморфный G, или граф с таким же числом точек и линий и правильным гамильтоновым циклом. Хотя ее шансы угадать, какое доказательство потребует Виктор на этапе (3), составляют 50 процентов, Виктор может повторить протокол достаточное число раз, убеждаясь, что Пегги знает гамильтонов цикл для G.

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

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

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

(2) Пегги вручает решение n новых трудных проблем.

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

(4) Для каждой новой трудной проблемы Виктор просит Пегги либо

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

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

(5) Пегги исполняет его просьбу для каждой новой проблемы.

К несчастью, все не так просто. Этот протокол, в отличие от предыдущего, не обладает такими же свойствами нулевого знания. На этапе (4) Виктор может потребовать, чтобы доказательство было представлено в виде значения однонаправленной хэш-функции всех значений, врученных на первом этапе, делая невозможным имитацию записи протокола. Это тоже нулевое знание, но другого рода. На практике оно представляется безопасным, но никто не знает, как это доказать. Мы действительно знаем только то, что при определенных условиях определенные протоколы для определенных проблем могут быть выполнены параллельно без потери свойства нулевого знания [247, 106, 546, 616].

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

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

Для неинтерактивных доказательств с нулевым знанием был придуман ряд протоколов [477, 198, 478, 197], которые не требуют непосредственного взаимодействия. Пегги может опубликовать их и, таким образом, доказать свое знание всем, у кого найдется время это проверить

Базовый протокол похож на параллельное доказательство с нулевым знанием, но место Виктора занимает однонаправленная хэш-функция:

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

(2) Пегги вручает решение n новых трудных проблем.

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

(4) Пегги берет n битов, полученных на этапе (3). По очереди для каждой n-ой трудной проблемы она берет n‑ый бит и

(a) если бит равен 0, доказывает, что старая и новая проблемы изоморфны, либо

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

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

(6) Виктор, Кэрол и все остальные заинтересованные лица проверяют, что этапы (1)-(5) выполнены правильно.

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

Эта схема работает, потому что однонаправленная хэш-функция действует как беспристрастный генератор случайных битов. Чтобы мошенничать, Пегги нужно уметь предсказывать результат однонаправленной хэш-функции. (Помните, если решение трудной проблемы ей неизвестно, она может сделать на этапе (4) либо (a), либо (b), но не оба действия одновременно.) Если она каким-то образом узнает, выполнение какого действия потребует от нее однонаправленная хэш-функция, то она сможет смошенничать. Однако, Пегги не сможет заставить однонаправленную хэш-функцию выдать определенный бит или догадаться, какой бит будет получен. Однонаправленная хэш-функция по сути является заменителем Виктора в случайном выборе одного из двух доказательств на этапе (4).

В неинтерактивном протоколе должно быть гораздо больше итераций в последовательности запрос/ответ. Пегги, а не Виктор, отбирает трудные проблемы с помощью случайных чисел. Она может подбирать различные проблемы, следовательно, и различные векторы вручения, до тех пор, пока хэш-функция не выдаст что-то, нужное Пегги. В интерактивном протоколе 10 итераций - вероятность мошенничества Пегги составит 1 шанс из 2¹⁰ (1 из 1024) - может быть достаточно. Однако, для неинтерактивных доказательств с нулевым знанием этого не хватит. Помните, что Мэллори всегда может выполнить на этапе (4) либо (a), либо (b). Он может, выполняя этапы (1)-(3), попытаться догадаться, что его попросят сделать, и посмотреть, правильно ли его предположение. Если нет, он попробует снова и снова. Сделать 1024 предположения на компьютере нетрудно. Для предотвращения такого вскрытия грубым взломом для неинтерактивных протоколов нужно 64 или даже 128 итераций.

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

Общие замечания

Блюм (Blum) доказал, что любая математическая теорема может быть преобразована в граф, такой, что доказательство теоремы будет эквивалентно доказательству существования гамильтонова цикла для этого графа. В общем виде то, что для любого NP-полного утверждения есть доказательство с нулевым знанием, использующее однонаправленные функции и, следовательно, хорошие алгоритмы шифрования, доказано в [620]. Любое математическое доказательство может быть преобразовано в доказательство с нулевым знанием. Используя эту методику, исследователь может доказать миру, что ему известно доказательство конкретной теоремы, не раскрывая самого решения. Блюм мог опубликовать свои результаты, не раскрывая их.

Также существуют доказательства с минимальным раскрытием [590]. Для доказательства с минимальным раскрытием выполняются следующие свойства:

1. Пегги не может обмануть Виктора. Если Пегги не знает доказательства, ее шансы убедить Виктора в том, что доказательство ей известно, пренебрежимо малы.

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]. Много чегобыло написано по этому вопросу.

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). Даже если Боб заполучит документ со своей подписью после окончания протокола, он не сможет доказать (себе или кому-то другому), что он подписал его в этом конкретном протоколе. Он знает, что его подпись правильна. Он может, как и любой другой, проверить свою подпись. Однако, у него нет никакой возможности связать подписанный документ и любую информацию, полученную при выполнении протокола. Если он подписал, используя этот протокол, миллион документов, у него не будет способа узнать когда какой документ он подписал. Полностью слепые подписи обладают следующими свойствами:

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

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

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

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

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

Однако, существует способ, с помощью которого Боб может узнать, что он подписывает, вместе с тем сохраняя полезные свойства слепых подписей. Центральным моментом этого протокола является техника "разрезать и выбрать". Рассмотрим следующий пример. Множество людей каждый день въезжают в некую страну, и Департамент иммиграции хочет удостовериться, что они не ввозят кокаин. Служащие могут обыскивать каждого, но вместо этого используется вероятностное решение - обыскивается каждый десятый въезжающий. Подвергается досмотру имущество одного человека из десяти, остальные девять пропускаются беспрепятственно. Постоянные контрабандисты в большинстве случаев проскакивают незамеченными, но с вероятностью 10 процентов их ловят. И если судебная система работает эффективно, наказание за единственную поимку на месте преступления более чем перевешивает выгоды девяти удачных попыток.

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

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

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

В следующем сценарии действует группа агентов контрразведки. Их личности засекречены, даже само Управление контрразведки не знает, кто они такие. Директора Управления хочет выдать каждому агенту подписанный документ следующего содержания: "Податель этого подписанного документа, (вставьте имя, под которым действует агент), обладает полной дипломатической неприкосновенностью". У каждого из агентов есть свой список псевдонимов, поэтому Управление не может просто раздать подписанные документы. Агенты не хотят передавать свои псевдонимы в Управление, так как враг мог вскрыть компьютер Управления. С другой стороны, Управление не хочет слепо подписывать документы, предоставленные агентом. Хитрый агент может представить сообщение, подобное следующему: "Агент (имя) вышел в отставку, и ему назначена ежегодная пенсия в миллион долларов. Подписано, Президент". В этом случае могут быть полезны слепые подписи.

Предположим, что у каждого агента по 10 псевдонимов, выбранных ими самими и больше никому неизвестных. Предположим также, что агентам все равно, под каким именем они получат дипломатическую неприкосновенность. Также предположим, компьютер управления называется Agency's Large Intelligent Computing Engine (Большая Интеллектуальная Вычислительная Машина Управления), или ALICE, а нашим конкретным агентом является Bogota Operations Branch (Сектор операций в Боготе): BOB.

(1) BOB готовит nдокументов, каждый из которых использует различный псевдоним, дающих ему дипломатическую неприкосновенность.

(2) BOB маскирует каждый из документов отличным маскирующим множителем.

(3) BOB отправляет nдокументов ALICE.

(4) ALICE случайным образом выбирает n-1 документ и просит BOB'а прислать маскирующий множитель для каждого из выбранных документов.

(5) BOB посылает ALICE соответствующие маскирующие множители.

(6) ALICE открывает (т.е., удаляет маскирующий множитель) n-1 документ и убеждается в том, что они корректны - и не являются разрешением на выплату пенсии.

(7) ALICE подписывает оставшийся документ и посылает его BOB'у.

(8) Агент удаляет маскирующий множитель и читает свой новый псевдоним: "Малиновая полоса." Подписанный документ дает ему дипломатическую неприкосновенность под этим именем.

Этот протокол надежно защищен от мошенничества BOB'а. Чтобы смошенничать, он должен точно угадать, какой документ ALICE не будет проверять. Вероятность этого - 1 шанс из n - не слишком велика. ALICE знает это и чувствует себя уверенно, подписывая документ, который она не сможет проверить. Для этого документа рассматриваемый протокол полностью совпадает с предыдущим протоколом полностью слепой подписи, сохраняя все свойства анонимности.