4.4.1. Электронные аукционы

Традиционной, классической формой аукциона является так на-зываемый аукцион первой цены (first-price auctionJ, когда продавец отдает товар предложившему за него наивысшую цену покупателю по этой цене. Различают три вида таких торгов: аукцион на повыше-ние («английский»), аукцион на понижение («голландский») и аукцион с запечатанными конвертами (когда покупатели подают ценовые предложения независимо друг от друга).

В первом случае («английский аукцион») аукционатор называет номер лота и исходную цену, которая примерно равна рыночной цене.

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

Две названные формы торгов можно отнести к интерактивным аукционам: здесь участники торгов знают ценовые предложения друг друга и стремятся их «побить», предлагая еще более высокую цену.

Возможна неинтерактивная форма аукциона (sealed-bid auction): все потенциальные покупатели одновременно, секретно и независимо друг от друга сообщают аукционатору свои цены, за которые они готовы приобрести лот (например, в запечатанных кон-вертах), а аукционатор определяет среди них максимальную. Лот достается тому, кто предложил наивысшую цену, после чего с поку-пателем подписывается контракт.

Менее привычная форма публичных торгов - аукционы второй цены (second-price). Здесь, как и в предыдущем случае, все покупа-тели одновременно, секретно и независимо друг от друга сообщают свои цены и аукционатор определяет среди них максимальную. Лот по-прежнему достается покупателю, предложившему за него наи-высшую цену, но он оплачивает покупку не по предложенной им самим цене, а по той цене, которая оказалась второй по величине среди всех цен, предложенных участниками торгов. Аукцион второй цены совмещает в себе достоинства «английского» и неинтерактивного аукционов.

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

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

Рассмотрим теперь криптографические схемы электронных аук-ционов. Пусть в аукционе участвует п покупателей, каждый из кото- 4. Криптографические протоколы в электронной коммерции и в документообороте 273

274 Запечников С. В. Криптографические протоколы и их применение

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

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

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

В схеме вводится коммутативная функция ценовых предложений (bid function), которая обозначается fx :G" G, определенная на

конечной абелевой группе :

1=1

Она вычисляется покупателями совместно для каждой цены Pj,j = l,k, используя аддитивные доли кода каждого ценового предложения (как это происходит, станет ясно в дальнейшем). Далее будем обозначать х+т - т-я аддитивная доля величины х. Пусть і є {1,2, индексы (порядковые номера) покупателей,

4. Криптографические протоколы в электронной коммерции и в документообороте 275

ує {1,2, ...,*}- индексы ценовых предложений. Все вычисления вы-полняются в конечной абелевой группе (<-?,+) с нейтральным эле-ментом 0. Группа (?,+} обычно выбирается как (Z2, или как

(М'.®)-

Каждый покупатель я, участвующий в торгах, выполняет ряд шагов (рис. 4.16 поясняет последовательность действий). Покупатель Покупатель Покупатель I 2 п 1. Создание кодов

2. Разделение кодов 7+1 7+2

ц + t\ + + к• = 5, if + К2 + ¦ + Г - 4 «Доска объявлешй» 3.Определение победителя публичных тоагов

Рис. 4.16. Выполнение протокола публичных торгов в схеме электронного аукциона B-share

1. Создание кодов. Для каждого j = l,k выбирается случайный ненулевой элемент группы Ynj, который депонируется у продавца (аукционатора). Для этого покупатель отправляет ему, например, где Н - криптографическая хеш-функция.

276 Запечников С. В. Криптографические протоколы и их применение

Разделение кодов:

для каждого і и для каждого j покупателем а формируется вели-

/1

чина К; по следующему правилу: ^b*! = Ya., если покупатель

/=і

а согласен заплатить дену pj} и = 0 в противном случае;

/=1

для каждого j покупатель а рассылает Ь*' всем остальным покупателям z, г^а;

покупатель а получает от всех остальных покупателей bta (для

каждого j, для всех і Фа), отправленные ими на предыдущем шаге протокола;

п

для каждого j величина bja = J^by" публикуется покупателем

/=і

а на «доске объявлений» (в открытом общедоступном спра-вочнике);

для каждого j, используя опубликованные bja, вычисляется величина в] = /, [ь]\ь]\...у;) = ¦

л=I

Определение победителя торгов. Если В.

у , считаем, что покупатель а выиграл аукцион. Цена продажи

лота при этом равна р ._t, где / = min[j: В} =0}. Она открыта и

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

Еще раз обратим внимание, что такая последовательность действий выполняется каждъш. из покупателей, участвующих в аукционе. Как видим, протокол выполняется в основном самими покупателя-ми- участие продавца (аукционатора) здесь очень ограниченно. Промежуточные суммы должны публиковаться одновременно. Этого можно добиться, используя один из методов депонирования секрета, например используя криптографическую хеш-функцию. Как следствие, покупатели могут прервать аукцион, если не будут в точности следовать протоколу, т. е. схема B-share не обладает свойст-вом робастности. Так, протокол может «повиснуть», если кто-то из участников не пришлет вовремя требуемые от него доли, поэтому «замолчавших» покупателей по прошествии некоторого времени не-обходимо исключать из числа участников протокола. Если кто-либо из покупателей произвел предписанные ему действия некорректно, это также может повлиять на правильность конечного результата. Кроме того, если с-1 покупателей, предложивших наивысшие цены, объединятся, то они смогут узнать с-е сверху ценовое предложение, т. е. полной конфиденциальности покупателей эта схема не обеспе-чивает. По этой причине для схемы электронного аукциона B-share необходимо предуЬмотреть еще и протокол арбитража, который в случае невозможности определить победителя торгов позволял бы «выслеживать» нечестного продавца (аукционатора) или нечестных покупателей (внесших в протокол некорректные данные либо всту-пивших в сговор между собой).

Протокол публичных торгов всегда завершается за три шага, описанных выше, что является безусловным его преимуществом перед «голландским аукционом», который завершается за конечное, но неопределенное число шагов. Сложность протокола для каждого участника оценивается следующим образом: число раундов - 0(1), количество пересылаемых сообщений - 0(п), объем передаваемых данных - 0(nk).

Примером схемы, удовлетворяющей более высоким требованиям безопасности, является схема электронного аукциона МB-share (F.

и

на случайный множитель М . — , не известный ни одному из

/=1

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

F* ={У :ie zj. Определим функцию ценового предложения /2: F" —» F следующим образом:

Все покупатели распределяют аддитивные доли своих X,-. Затем

^ ХГ

каждый из них вычисляет g 1 с величинами х. , полученными как

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

Л-Г-Па-резу льтат g на «доске объявлений». Когда все опублико-ванные величины перемножаются, это дает

П 8 ы > = f2(XvX2,...,Xn).

(1=1

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

Чтобы объединить покупателей в логическое кольцо, им всем необходимо присвоить порядковые номера. Для этого определяется функция s(i), значение которой дает для каждого участника і номер следующего за ним участника в кольце: s(i) = /+1, если iИтак, пусть іє {1,2, ...,л}- индексы (порядковые номера) покупателей, je{ 1,2,...,&} - индексы ценовых предложений, Ьпе є {1,2,...,&} - последовательность ценовых предложений участника <я. Все вычисления выполняются в конечном поле F, например в поле GF( 2').

Каждый покупатель а, участвующий в публичных торгах, вы-полняет ряд шагов (рис. 4.17 поясняет последовательность дейст-вий).

Покупатель 2

Покупатель п

і А

ы

1. Создание кодов

Т)

С

2. Разделение кодов 3. Передача по кольцу Ді х В21 х ... X К = д Д* X В2к х ... X Д* = А «Доска объявлений» і 4,Определение ! победителя публичных торгов

Рис. 4.17. Выполнение протокола публичных торгов в схеме электронного аукциона MB-share

Создание кодов и депонирование ценовых предложений:

для каждого j выбираются случайные элементы поля Yrl J,

в,

Д, = д

в,

в.

Д* = Д

'2 k

«Доска объявлений»

т*а Ф 0 и случайное число га.

ценовое предложение Ъ„ депонируется у продавца (аукционато- ра), для чего покупатель а пересылает ему \_Н[Ьа +гя),гп], где Н - криптографическая хеш-функция.

Разделение кодов:

для каждого і и для каждого j покупателем а формируется вели-

п

чина b*J по следующему правилу: Vb^ = Y., если Ьа> j,

П

и V btj = 0 в противном случае.

для каждого j величины b*J покупатель а рассылает b*j всем остальным покупателям і, і Ф а;

покупатель а получает от других покупателей Щ" (для каждого

у, для всех і Ф а), отправленные ими на предыдущем шаге протокола.

Передача по кольцу:

для всех j покупатель а вычисляет величину g1=1

и отправляет ее покупателю с номером s(a)-,

после получения г Bjj покупатель с номером а вычисляет

r_, Bjj = (rBtj)"*J . Если /¦>!, он посылает эту величину участнику s(a), в противном случае публикует на «доске объявле

ний» (в открытом общедоступном справочнике); для каждого j, используя опубликованные Bih вычисляются

Bj-fl*,-

1=1

Определение победителя торгов. Цена продажи лота равна , где f ~ min.{/: В. = о}. Она доступна всем участникам публичных торгов. Победивший покупатель проходит аутентификацию у продавца (аукционатора), пересылая ему га по защищенному каналу связи.

Передача данных по кольцу требует п дополнительных пересылок сообщений, поэтому число раундов протокола оценивается как <9(л), но общее количество сообщений по-прежнему оценивается как 0(п), а суммарных объем передаваемых данных 0(nk).

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

4. Криптографические протоколы в электронной колшерции и в докуліентообороте 281

телей можно представлять себе как единого покупателя, действующего на торгах через агентов - присвоим ему номер 2. Покажем, что покупатель 2 никаким образом не сможет узнать ценовое предложение покупателя 1. Предположим для определенности, что bxдля всех у. Для этого есть две возможности. Во-первых, покупатель 2 может попытаться извлечь , используя любую комбинацию известных ему величин: by, b2^, b^j, m2j,

„ [bn+bfj+bt\+bfi)num4 (b{} k ,¦ 1T

Bj ~ 8 ' '' u. g 1 J 1. Но это вычислительно не

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

i-bf] +bfj +і2+] +Д?7 )»|[ ,ш2J

вычислить значение величины gx 1 1 1 4 1 и сравнить его

с Bj. Но это невозможно, так как тх. неизвестно покупателю 2 и

не может быть получено им из известных ему величин.

Но и эта схема не идеальна, так как, кроме недостатков, свойственных предыдущей схеме (возможность «зависания» или состояния, когда нельзя определить победителя публичных торгов),, вероятна такая ситуация, когда выигравший аукцион покупатель так и не узнает об этом из-за злоумышленных действий других участников схемы.

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