3.6. Поиграем в ``кубики''. Протоколы голосования

Next: 3.7. За пределами стандартных Up: 3. Криптографические протоколы Previous: 3.5. Еще раз о Contents: Содержание

3.6. Поиграем в ``кубики''. Протоколы голосования

``...всеобщее голосование бессмысленно.
...Вы, вероятно, согласитесь со мной, что гениальные люди встречаются редко, не правда ли? Но будем щедры и допустим, что во Франции их сейчас имеется человек пять. Прибавим, с такой же щедростью, двести высокоталантливых людей, тысячу других, тоже талантливых, каждый в своей области, и десять тысяч человек так или иначе выдающихся. Вот вам генеральный штаб в одиннадцать тысяч двести пять умов. За ним идет армия посредственности, за которой следует вся масса дурачья. А так как посредственность и дураки всегда составляют огромное большинство, то немыслимо представить, чтобы они могли избрать разумное правительство."

Г. де Мопассан. ``Обед и несколько мыслей''.

В этом разделе мы займемся бессмысленными вещами, а именно, обсудим, как помочь ``массе дурачья'' избрать ``неразумное правительство'', т.е. рассмотрим протоколы голосования.

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

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

Пусть в голосовании участвуют избирателей $V_1,\dots ,V_l$ , которые являются абонентами компьютерной сети и подают свои голоса в электронной форме. Предположим для простоты, что голосование имеет два исхода: ``за'' и ``против'', которые будут представляться как 1 и соответственно. Из всех возможных требований к протоколу голосования выделим пока два основных:

1) голосование должно быть тайным;

2) должна быть обеспечена правильность подсчета голосов.

Как уже отмечалось в предыдущем разделе, протоколы голосования можно рассматривать как частный случай протоколов конфиденциального вычисления. В начальный момент у каждого участника есть секретное значение $b_i\in \{ -1,1\}$ - его голос, - и требуется вычислить функцию $f(b_1\dots ,b_l)=\sum^l_{i=1}b_i$ . Протокол конфиденциального вычисления удовлетворяет двум указанным требованиям, если только доля нечестных участников не слишком велика. У такого решения есть одно замечательное достоинство - в протоколе участвуют только избиратели, т.е. не требуется никакого центрального органа, который пользовался бы доверием голосующих. Но есть и весьма серьезный недостаток. Протоколы конфиденциального вычисления настолько сложны (с точки зрения количества вычислений, выполняемых каждым участником, и количества пересылаемой информации), что уже при сравнительно небольших они практически невыполнимы.

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

Уже в этой простой схеме есть ``подводный камень''. Если каждый избиратель просто шифрует свой бит на ключе , то возможных криптограмм всего две и ни о какой анонимности голосов речи быть не может. Можно шифровать строку, которая состоит из бита , дополненного, например, справа случайной строкой. Это накладывает дополнительные требования на криптосистему: старший бит открытого текста должен быть трудным, т.е. задача его вычисления по криптограмме должна быть эквивалентна (в смысле полиномиальной сводимости) задаче вычисления всего открытого текста. Такие криптосистемы существуют, но лучше использовать криптосистему вероятностного шифрования (см. [19]), в ней криптограмма сообщения на ключе вычисляется с помощью рандомизированного алгоритма: , где - случайная строка. Это означает, что у каждого сообщения существует, вообще говоря, экспоненциально много криптограмм, вычисленных на одном и том же ключе. Но дешифрование при этом всегда однозначно! Криптосистемы вероятностного шифрования были введены в работе Гольдвассер и Микали [19], где при некоторых предположениях доказано существование криптосистем такого типа, обладающих так называемой семантической стойкостью. Это - своего рода аналог шенноновской абсолютной стойкости, но относительно противника, работающего за полиномиальное время.

Мы рассмотрим в качестве примера один из вариантов криптосистемы Эль-Гамаля [20], основанной на задаче дискретного логарифмирования. В обозначениях из раздела 3 пусть - подгруппа , порожденная . Для сообщения $m\in G_q$ выбирается $\alpha \in _RZ_q$ и вычисляется криптограмма , где $a=g^\alpha \nmod p$ , $b=y^\alpha m\nmod p$ . Получатель, знающий секретный ключ , вычисляет

$\begin{displaymath}b/a^x=y^\alpha m/(g^\alpha )^x=y^\alpha m/g^{x\alpha }=y^\alpha m/y^\alpha =m\pmod p.\end{displaymath}$

Вернемся к протоколу голосования. Пусть - еще один порождающий группы . Тогда для $b\in \{-1,1\}$ бюллетень вычисляется в виде $(g^\alpha, y^\alpha h^b)$ . После применения алгоритма дешифрования центр получит значение $h^b\nmod p$ , после чего бит можно извлечь, просто подставляя оба значения 1 и .

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

После этого центр вычисляет $z=\sum^l_{i=1}b_i$ и публикует итог голосования . Пусть $(g^{\alpha _i}, y^{\alpha _i}h^{b_i})$ - бюллетень избирателя . Поскольку все бюллетени находятся на табло, любой избиратель, а также всякий сторонний наблюдатель, может вычислить

$\begin{displaymath}(\prod^l_{i-1}g^{\alpha _i}\nmod p, \prod ^l_{i=1} y^ {\alpha _i}h^{b_i}\nmod p).\end{displaymath}$

Обозначим $A=\prod ^l_{i=1}g^{\alpha _i}\nmod p$ , $B=\prod ^l_{i=1}y^{\alpha _i}\nmod p$ . Если центр правильно подсчитал голоса, то должно выполняться равенство $h^z= \prod^l_{i=1}h^{b_i} \pmod p$ . Поэтому, если вторую из вычисленных выше величин поделить на , то должно получиться значение . Пусть $B'=(\prod ^l_{i=1}y^{\alpha_i}h^{b_i})/h^z \nmod p$ . Проблема в том, что проверяющий не знает значение и не может самостоятельно выяснить, верно ли, что . Но нетрудно проверить, что должно выполняться сравнение $B=A^x\pmod p$ . Поэтому проверяющий может потребовать от центра доказательство следующего факта: дискретный логарифм по основанию равен дискретному логарифму по основанию . Мы приводим предназначенный для этой цели протокол Шаума и Педерсена [21], цитируя его по работе [22].

Next: 3.7. За пределами стандартных Up: 3. Криптографические протоколы Previous: 3.5. Еще раз о Contents: Содержание