Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Книги
 Обсудить в форуме  Добавить новое сообщение
Next: 3.7. За пределами стандартных Up: 3. Криптографические протоколы Previous: 3.5. Еще раз о Contents: Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

\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}

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

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

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


Протокол Шаума и Педерсена

  • Доказывающий выбирает $ k\in _RZ_q$, вычисляет $ (\beta , \gamma)=(g^k\nmod p, A^k\nmod p)$ и посылает $ (\beta ,\gamma)$ проверяющему.

  • Проверяющий выбирает запрос $ e\in _RZ_q$ и посылает $ e$ доказывающему.

  • Доказывающий вычисляет $ s=(k+ex)\nmod q$ и посылает $ s$ проверяющему.

  • Проверяющий убеждается, что $ g^s=\beta y^e\nmod p$ и $ A^s=\gamma B^e\nmod p$, и принимает доказательство. В противном случае, если хотя бы одно из этих сравнений не выполняется, - отвергает.


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

    В принципе центр может доказать утверждение $ B'=A\pmod p$ каждому желающему. Неудобство в том, что протокол интерактивный. Но используя тот же прием, которым схема аутентификации Шнорра преобразуется в схему электронной подписи (см. раздел 3), можно и этот протокол сделать неинтерактивным. В таком случае центр может просто опубликовать неинтерактивное доказательство вместе с итогом $ z$.

    Конечно, предположение о том, что все избиратели доверяют одному центру подсчета голосов, весьма далеко от реальности. Можно создать $ n$ центров $ C_1,\dots ,C_n$. Тогда предположение о том, что по крайней мере $ t$ центров из $ n$ честные, где, например, $ t\geq 2n/3$, выглядит более реалистичным.

    В этом случае центры совместно выбирают и публикуют три случайных порождающих $ g$, $ y$ и $ h$ группы $ G_q$. Бюллетень избирателя $ V_i$ формируется так же, как и в предыдущем варианте: $ (g^{\alpha _i}, y^{\alpha _i}h^{b_i})$. Но теперь центры не в состоянии сами дешифровать эту криптограмму. Вместо этого каждый из них вычисляет $ (\prod ^l_{i=1}g^{\alpha _i}, \prod ^l_{i=1}y^{\alpha _i}h^{b_i})$. Избиратель $ V_i$ с помощью описанной в предыдущем разделе схемы проверяемого разделения секрета создает доли $ \alpha _{i_1},\dots ,\alpha _{i_n}$ секретного значения $ \alpha _i$ и передает долю $ \alpha _{i_j}$ центру $ C_j$. Далее, выполняя вычисления над долями (см. раздел 5), центры вычисляют $ \delta =\sum ^l_{i=1}\alpha _i\nmod p$. Если при этом хотя бы $ t$ центров честные, то остальные не смогут восстановить ни одно из значений $ \alpha _i$. Полученный результат $ \delta$ проверяется: должно выполняться сравнение $ g^\delta =\prod ^l_{i=1}g^{\alpha _i}\nmod p$. Если оно выполнено, то значение $ \delta$ публикуется, и этого значения достаточно для вычисления итога голосования. В самом деле, $ (\prod ^l_{i=1}y^{\alpha _i}h^{b_i})/y^\delta=\prod ^l_{i=1}h^{b_i}\pmod p$. Правда, для того чтобы получить итог $ z$, необходимо вычислить дискретный логарифм полученной величины. Но поскольку абсолютное значение $ z$ невелико (заведомо не превосходит количества избирателей $ l$) это можно сделать простым перебором.

    В этой схеме возникает новая проблема - необходимо обеспечить протокол, с помощью которого центры совместно выбирают порождающие $ g$, $ y$ и $ h$, причем так, что ни один из них не является известной степенью другого. Эту проблему можно решить следующим способом. Пусть $ G$ - вероятностный алгоритм, который генерирует три случайных порождающих. Его можно рассматривать как детерминированный алгоритм, который получает на входе помимо чисел $ p$ и $ q$ еще и случайную строку $ r$ требуемой длины. В разделе 4 был описан протокол подбрасывания монеты, который очевидным образом обобщается на случай $ n$ участников. С помощью такого обобщенного протокола центры могут по биту сгенерировать строку $ r$ (существуют и более эффективные схемы). Если хотя бы один из центров честный, то $ r$ - случайная строка. По окончании выполнения протокола центры публикуют $ r$, $ g$, $ y$ и $ h$. Поскольку алгоритм $ G$ предполагается общеизвестным, всякий желающий может проверить, что $ g$, $ y$ и $ h$ получены с помощью строки $ r$.

    Все проблемы решены? Отнюдь! Если в случае одного центра последний расшифровывал все бюллетени и проверял их правильность, отбрасывая недействительные, то в случае $ n$ центров нечестный избиратель может попытаться с помощью недействительного бюллетеня сорвать выборы или исказить их итог. Эту проблему можно решить, если потребовать, чтобы вместе с бюллетенем каждый избиратель публиковал доказательство, что бюллетень построен правильно. Другими словами, требуется протокол, с помощью которого для данного бюллетеня $ (A_i, B_i)$ избиратель $ V_i$ доказывал, что он знает $ \alpha _i\in Z_q$ и $ b_i\in \{ -1,1\}$ такие, что $ A_i=g^{\alpha _i}\nmod p$, $ B_i=y^{\alpha _i}h^{b_i}\nmod p$. При этом протокол не должен давать проверяющему никакой полезной для него информации о значениях $ \alpha _i$ и $ b_i$. Пример такого протокола дан в работе [22]; мы его не воспроизводим здесь ввиду громоздкости.

    Теперь, наконец, все? Опять нет! ...Впрочем, поставим на этом точку. Надеемся, что читатель уже убедился в том, что протоколы голосования - нетривиальный объект и всевозможные его технические аспекты можно обсуждать еще очень долго. К тому же мы рассматривали только два основных требования к протоколам голосования - анонимность и правильность подсчета голосов. А ведь существуют и другие. Причем новые требования могут возникать уже в процессе анализа протоколов голосования, когда обнаруживается, что последние обладают некоторыми неожиданными свойствами, которых нет в ныне общепринятых неэлектронных системах выборов. Например, при использовании описанной выше конструкции бюллетеня избиратель $ V_i$ знает значения $ \alpha _i$ и $ b_i$, которые он впоследствии может использовать для доказательства, что голосовал данным определенным образом (например, ``за'', а не ``против''). Это создает возможности покупки голосов и требует разработки соответствующей криптографической защиты.

    Дальнейшие подробности протоколов голосования см. в работах [22], [23], из которых заимствованы изложенные выше идеи построения таких протоколов.

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

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

    Проект осуществляется при поддержке:
     Геологического факультета МГУ,
    РФФИ
    		    
    TopList Rambler's Top100