8.2.2 Схемы Шаума

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

В обеих схемах банк вырабатывает два больших простых числа и и публикует их произведение , сохраняя множители в секрете (инициализация схемы электронной подписи RSA). Кроме того, выбирается и публикуется некоторая односторонняя функция . Устанавливается соглашение, согласно которому экспоненте, равной -му нечетному простому числу, соответствует номинал в , скажем, центов. Т. е., предъявитель пары является владельцем электронной банкноты достоинством в 1 цент. Если в этой паре вместо корня кубического присутствует корень 7-ой степени, то банкнота имеет достоинство 4 цента, а если 21-ой степени -- то 5 центов. Иными словами, для банкноты достоинством  центов необходим корень степени, равной произведению всех простых, соответствующих единицам в двоичном представлении числа .

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

В транзакции снятия со счета покупатель выбирает случайное значение и вычисляет . Ему нужно получить подпись банка на этой банкноте, т. е. вычислить . Но просто послать значение банку покупатель не может, поскольку для снятия денег со счета он должен идентифицировать себя. Поэтому, если банк получает , он в дальнейшем всегда узнает данную банкноту и неотслеживаемость будет потеряна. Решение проблемы состоит в использовании затемненной подписи: покупатель выбирает случайное значение , , вычисляет и посылает это значение банку. Множитель часто называют затемняющим множителем. Банк вычисляет значение и возвращает его покупателю. Покупатель легко "снимает" затемняющий множитель и получает подписанную банкноту .

Предположим, теперь, что покупатель желает заплатить продавцу 5 центов. Для этого он вычисляет , просто возводя полученную банкноту в 55-ую степень, и создает копилку, выбирая случайное значение и вычисляя . Здесь опять  -- затемняющий множитель. Транзакция платежа начинается с пересылки значений , , , а также суммы платежа (5 центов) продавцу. Продавец, в свою очередь, передает всю эту информацию банку. Банк легко проверяет, что пара представляет собой подлинную банкноту достоинством 5 центов. Он проверяет по специальному регистру, не была ли банкнота с номером потрачена ранее. Если нет, записывает в регистр вновь полученную банкноту и посылает продавцу уведомление о завершении транзакции платежа, а также "сдачу" 10 центов для покупателя, возвращаемую через копилку: .

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

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

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

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

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

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

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

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

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

Транзакция депозита в данной схеме ничем не отличается (с криптографической точки зрения) от транзакции платежа.

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

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

В литературе имеются и другие описания схем электронных платежей. Интересно отметить, что практически все они используют затемненную подпись, основанную на схеме электронной подписи RSA.