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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ректны - и не являются разрешением на выплату пенсии

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

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

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

Существует трюк, который еще больше уменьшает вероятность мошенничества ВОВа. На этапе (4) ALICE случайным образом выбирает n/2 документов для проверки, и ВОВ присылает ей соответствующий маскирующие множители на этапе (5). На этапе (7) ALICE перемножает все непроверенные документы и подписывает получившийся мегадокумент. На этапе (8) ВОВ удаляет все маскировочные множители. Подпись ALICE будет правильной, только если ею подписано произведение n/2 идентичных документов. Чтобы смошенничать, ВОВу нужно точно угадать, какое подмножество документов будет проверять ALICE. Вероятность этого гораздо ниже, чем вероятность угадать единственный документ, который ALICE не проверяла.

ВОВ может смошенничать по другому. Он может создать два различных документа, один из которых ALICE согласна подписать, а другой - нет. Затем он может попытаться найти два различных маскирующих множителя, которые преобразуют указанные документы к одинаковому виду. Таким образом, если ALICE захочет проверить документ, ВОВ передаст ей маскирующий множитель, преобразующий документ к невинному виду . Если ALICE не захочет просмотреть документ и подпишет его , он применит тот маскирующий множитель, который преобразует замаскированный подписанный документ в документ, являющийся целью мошенничества . Хотя теоретически это и возможно, математика конкретных алгоритмов делает пренебрежимо малой вероятность для ВОВа найти такую пару. Действительно, она может быть столь низкой, как и вероятность Боба создать необх о-димую подпись под произвольным документом самостоятельно . Этот вопрос обсуждается ниже в разделе 23.12.

Патенты. Владельцем патентов на ряд особенностей слепых подписей является Чаум ( Chaum) (см. 4-й).

Табл. 5-1. Патенты Чаума на слепые подписи

5.4 Личностная криптография с открытыми ключами

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

Эту проблему решают личностные криптосистемы, иногда называемые системами с Неинтерактивным ра з-делением ключей (Non-Interactive Key Sharing, NIKS) [1422]. Открытый ключ Боба основывается на его имени и сетевом адресе (телефонном номере, почтовом адресе или чем-то подобном). В обычной криптографии с открытыми ключами Алисе нужен подписанный сертификат, связывающий личность Боба и его открытый ключ . В личностной криптографии открытый ключ Боба и есть его личность. Это действительно свежая идея является почти совершенной для почтовой системы - Если Алиса знает адрес Боба, она может безопасно посылать ему почту, что делает криптографию прозрачной, насколько это вообще возможно .

Система основана на выдаче Трентом ключей пользователям в зависимости от их личности . Если закрытый