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

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

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

Протокол №4

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

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

(1) Алиса готовит n анонимных денежных чеков на заданную сумму.

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

На каждом чеке есть также n пар битовых строк идентификации, I1, 12, 1„. (Именно так, n различных пар на каждом чеке.) Каждая из этих пар генерируется следующим образом: Алиса создает строку, содержащую ее имя, адрес и прочие сведения, требуемые банком . Затем она делит эту строку на две части, используя протокол деления секрета (см. раздел 3.6) и вручает каждую часть, используя протокол вручения битов.

Например, I37 состоит из двух частей: I37 и I37 . Каждая часть представляет собой пакет врученных битов, который Алису могут попросить открыть, и чье открытое содержание может быть мгновенно пров е-рено. Любая пара (например, I37 и I37 , но не I37 и I38 ), раскрывает личность Алисы. Каждый из

чеков выглядит следующим образом: Сумма

Уникальная строка: X

Строки идентификации:I1 = (I1 , I1 )

12 = (12 l , 12 r )

(2)Алиса маскирует все n чеков с помощью протокола слепой подписи и относит чеки в банк.

(3)Банк просит Алису снять маскировку с n-1 денежных чеков и убеждается, что все они правильно офор м-лены. Банк проверяет сумму, уникальную строку и просит Алису раскрыть все строки идентификации.

(4)Если банк удовлетворен, не обнаружив попыток мошенничества, он подписывает оставшийся замаскир о-ванный денежный чек. Банк возвращает замаскированный чек Алисе и списывает сумму с ее счета.

(5)Алиса снимает маскировку с чека и тратит его у продавца.

(6)Продавец проверяет банковскую подпись, убеждаясь в законности денежного чека .

(7)Продавец случайным образом просит Алису раскрыть либо левые, либо правые половины всех строк идентификации на чеке. По сути, продавец выдает Алисе случайную n-битовую строку-селектор, b1, b2,

bn. Левую или правую половину I откроет Алиса, зависит от значения bb 0 или 1.

(8)Алиса выполняет это.

(9)Продавец относит денежный чек в банк.

(10)Банк проверяет свою подпись и по своей базе данных убеждается, что денежный чек с такой уникальной строкой ранее не депонировался. Если это так, банк начисляет указанную сумму на счет продавца и запи-

сывает уникальную строку в базу данных.

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

Это весьма интересный протокол, поэтому посмотрим на него с разных сторон .

Может ли Алиса смошенничать? Ее электронные деньги представляют собой просто строку битов, которую она легко может скопировать. Потратить их в первый раз - не проблема, она просто выполнит протокол, и все пройдет без проблем. Продавец выдаст ей на этапе (7) случайную п-битовую строку-селектор, и Алиса откроет либо левую, либо правую половину каждой I на этапе (8). На этапе (10) банк запишет все эти данные вместе с уникальной строкой денежного чека.

Когда она попытается использовать те же электронные деньги второй раз, продавец (тот же или иной) выдаст ей на этапе (7) другую случайную я-битовую строку-селектор. Алиса должна выполнить этап (8), ее отказ немедленно встревожит продавца. Теперь, когда продавец приносит деньги в банк на этапе (10) , банк немедленно заметит, что денежный чек с этой уникальной строкой уже был депонирован . Банк сравнивает открытые половины строк идентификации. Вероятность совпадения двух случайных строк-селекторов составляет один шанс из 2n, этого не случится до следующего оледенения. Теперь банк находит пару, первая половина которой была открыта в первый раз, а вторая - во второй, выполняет над этими половинами операцию XOR и извлекает имя Алисы. Так банк узнает, кто попытался воспользоваться чеком дважды .

Что этот протокол не мешает Алисе мошенничать, но ее мошенничество почти наверняка будет обнаружено . Смошенничав, Алиса не сможет сохранить в тайне свою личность . Она не может изменить ни уникальную строку, ни какую-нибудь из строк идентификации, иначе испортится банковская подпись, и продавец немедле н-но заметит это на этапе (6).

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

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

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

А как насчет банка? Может ли он вычислить, что денежный чек, полученный от продавца, это и есть тот с а-мый чек, который был подписан для Алисы ? На этапах (2)-(5) Алиса защищена протоколом слепой подписи . Банк не сможет связать Алису и чек, даже если он полностью сохраняет запись каждой транзакции . Более того, даже объединившись, банк и продавец не смогут установить личность Алисы . Алиса может пройтись по магазину и, оставаясь полностью анонимной, купить то, что ей надо .

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

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

Электронные наличные и идеальное приведение

У электронных наличных есть и своя темная сторона . Иногда людям не нужно так много секретности . Смотрите, как Алиса совершает идеальное преступление [1575]:

(1) Алиса крадет ребенка.

(2)Алиса готовит 10000 анонимных денежных чеков по $1000 (или другое количество чеков нужного ей до с-тоинства).

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

(a)Все 10000 денежных чеков должны быть подписаны банком.

(b)Результаты должны быть опубликованы в газете.

(4)Власти соглашаются.

(5)Алиса покупает газету, снимает маскировку с денежных чеков и начинает тратить их . Не смогут найти ее, проследив за денежными чеками .

(6)Алиса освобождает ребенка.

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

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

Реальные электронные наличные

Голландская компания, DigiCash, владеет большей частью патентов в области электронных наличных и ре а-лизовала протоколы электронных наличных в работающих продуктах owns. Если вы заинтересовались этим, обратитесь в DigiCash BV, Kruislaan 419, 1098 VA Amsterdam, Nethe rlands.

Другие протоколы электронных наличных

Существуют и другие протоколы электронных наличных, см. [707, 1554, 734, 1633, 973]. Ряд из них использует весьма изощренную математику. Различные протоколы электронных наличных можно разделить на ра з-личные категории. Диалоговые системы требуют, чтобы продавец связывался с банком при каждой продаже, что очень похоже на сегодняшний протокол для кредитных карточек . Если возникает какая-нибудь проблема, банк не принимает наличные, и Алиса не может смошенничать.

Автономные системы, подобные протоколу №4, не требуют соединения между продавцом и банком до окончания транзакции между продавцом и покупателем . Эти системы не помешают Алисе мошенничать, но вместо этого обнаружат ее мошенничество . Протокол №4 обнаруживает мошенничество Алисы, раскрывая ее личность при попытке мошенничать . Алиса знает о последствиях и, поэтому, не мошенничает .

Другой путь состоит в создании специальной интеллектуальной карты (см. Раздел 24.13), содержащей з а-щищенную микросхему, называемую наблюдателем [332, 341, 387]. Микросхема-наблюдатель хранит мини-базу данных всех частей электронных наличных, потраченных этой интеллектуальной платой. Если Алиса п о-пытается скопировать какие-то электронные наличные и потратить их дважды, внедренная микросхема-наблюдатель обнаружила бы такую попытку и не разрешила транзакцию. Так как микросхема-наблюдатель защищена от вмешательства извне, Алиса не сможет стереть мини-базу данных без разрушения интеллектуал ь-ной карты. Наличные деньги могут оборачиваться в экономике, когда они, наконец будут депонированы, банк может проверить наличные и определить мошенника, если произошел обман.

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

Двумя отличными совершенно отличающимися друг от друга автономными протоколами электронных м о-нет являются [225, 226, 227] и [563, 564, 565]. Также можно предложить система NetCash (Сетевые наличные) с более слабыми свойствами [1048, 1049]. Другой новой системой является [289].

В [1211] Тацуаки Окамото (Tatsuaki Okamoto) и Казуо Охта (Kazuo Ohta) перечислили шесть свойств идеальной системы электронных наличных:

1.Независимость. Безопасность электронных наличных не зависит от местонахождения . Наличные могут быть переданы по компьютерным сетям .

2.Безопасность. Электронные наличные нельзя скопировать и повторно использовать .

3.Тайна личности (Неотслеживаемость). Тайна личности пользователя защищена, связь между пользо-