[Из песочницы] Протокол электронного голосования: мой вариант

Habrahabr

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

На Хабре уже публиковался ряд статей о электронных выборах (раз, два, три), однако я не нашёл проработанного и отвечающего основным требованиям протокола. Так что встречайте: мой вариант протокола электронного голосования.

Дисклеймер
Автор не является профессионалом в криптографии и математике, поэтому указанная схема не претендует на безошибочность или глубокую проработанность. Схема получилась довольно несложной, так что весьма вероятно, что я изобрёл велосипед.

Требования к системе

Что же мы хотим получить на выходе? Я сформулировал следующие требования:
  1. Возможность независимого контроля;
  2. Стойкость к подтасовкам, со стороны избиркома, избирателей и третьих лиц
  3. Невозможность узнать, как проголосовал конкретный избиратель

Tl;dr: краткое описание протокола

  1. Избиратель регистрируется в избиркоме, предоставляя свои личные данные, маскированные ключ голосования и ключ проверки. Избирком подписывает маскированный ключ голосования;
  2. Избиратель демаскирует его и получает подписанный ключ голосования, создаёт на его основе анонимный голос и публикует его;
  3. Каждому голосу подбирается проверяющий из числа избирателей. Владелец голоса отсылает свои личные данные проверяющему с помощью его публичного ключа. Проверяющий проверяет, что голос соответствует реальному человеку.

Подробное описание протокола

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

Примечание: операция хеширования при подписывании, если она требуется, будет опускаться.

Список обозначений
$e$ — ключ шифрования;
$d$ – ключ дешифрования;
$m$ – маскирующий множитель;
$E_k$ – шифрование ключом k;
$D_k$ – дешифрование ключом k;
$M_m$ – маскировка множителем m;
$N_m$ – демаскировка множителем m;

$i$ – информация о человеке;
$c$ – выбор;
$K$ – контракт;
$V$ – голос;
$I$ – информация для проверки

0. Исходные данные

Избиратель:

$e_{личный}$ — ключ шифрования (закрытый) личной ЭЦП избирателя; $e_{голосования}$, $d_{голосования}$ — ключи шифрования и дешифрования. Создаются избирателем для конкретного голосования; $m$ — маскирующий множитель. Создаётся избирателем для конкретного голосования; $e_{проверочный}$, $d_{проверочный}$ — пара ключей для этапа проверки. Создаётся избирателем для конкретного голосования.

Публичный репозиторий личных данных:

Для каждого гражданина хранится следующая информация:
$i$информация об избирателе: ФИО, год рождения, адрес прописка и т. д.;$d_{личный}$ — публичный ключ личной ЭЦП; $E_{e_{\Large государственный}}(i + d_{личный}))$ — государственная подпись, удостоверяющая верность данных.
Так же в репозитории хранятся:
$d_{государственный}$ — публичный ключ государства; $d_{избиркома}$ — публичный ключ избиркома.

Государство:

$e_{государственный}$

— приватный ключ государства.

Избирком:

$e_{избиркома}$

— приватный ключ избиркома.

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

1. Регистрация

Каждый избиратель предъявляет свои данные избиркому. Он проверяет, что избиратель ещё не зарегистрирован и имеет избирательное право. После проверки комиссия вместе с избирателем создаёт то, что я буду далее называть контрактом.

Контракт содержит следующие данные:

$i$ — идентификационные данные избирателя $M_m(d_{голосования})$ — замаскированный секретным множителем избирателя ключ дешифрования для голосования $M_m(e_{проверочный})$ — замаскированный секретным множителем избирателя ключ шифрования для проверки $E_{е_{\Large избиркома}}(M_m(d_{голосования}))$ — замаскированный секретным множителем избирателя ключ дешифрования для голосования, подписанный избиркомом

$K_1 = i + M_m(d_{голосования}) + M_m(e_{проверочный}) + E_{е_{\Large избиркома}}(M_m(d_{голосования}))$

Эта информация подписывается как избиркомом, так и избирателем:

$K = K_1 + E_{e_{\Large личный}}(K_1) + E_{e_{\Large избиркома}}(K_1)$

Все контракты публикуется избиркомом.

На данном этапе предотвращаются следующие атаки:

  • Избирком откажется публиковать контракт. В таком случае, избиратель сможет доказать его существование, т.к. он подписан избиркомом;
  • Избиратель попытается зарегистрироваться ещё раз. Избирком может доказать, что избиратель уже регистрировался с помощью его подписи;
  • Избирком зарегистрирует несуществующих людей. В таком случае любой наблюдатель сможет доказать это, показав, что из данных нет в репозитории личных данных;
  • Избирком не может зарегистрировать реальных людей без их присутствия, т.к. не обладает их приватным ключом $e_{личный}$

2. Голосование

Избиратель демаскирует подписанный ключ для голосования:

$N_m(E_{е_{избиркома}}(M_m(d_{голосования}))) = E_{е_{\Large избиркома}}(d_{голосования})$

И создаёт не связанный с его личностью голос:

$V = d_{голосования} + E_{е_{\Large избиркома}}(d_{голосования}) + e_{проверочный} + с + E_{е_{\Large голосования}}(с)$

где

$c$

— выбор кандидата.

Избиратель анонимно отправляет голос в избирком. Избирком публикует его в открытом доступе и возвращает в качестве доказательства приёма $E_{е_{\Large избиркома}}(V)$.

3. Проверка

К сожалению, на прошлом этапе избирком мог создать сколько угодно голосов, не связанных с реальными личностями, поэтому необходима проверка каждого голоса. Кому поручить проверку? Я считаю, что лучше всего обратиться к принципам демархии и поручить проверку случайному избирателю. Можно придумать бесконечное количество схем распределения пар проверяющий-проверяемый на множестве голосов, но мне кажется оптимальным следующий: разбить множество на пары и назначить их проверяющими друг для друга. Таким образом разгласивший информацию проверяющий может быть привлечён к ответственности проверяемым. Какая бы схема не использовалась, алгоритм её формирования должен быть опубликован до начала регистрации, и зависеть от ключа, неизвестного до окончания регистрации. Например, ключ можно генерировать из курсов валют, или публично и совместно кандидатами (например, с помощью лототрона). Если проигнорировать это условие, избирком сможет после окончания регистрации найти и добавить в список такое множество фальшивых голосов, что все они или большинство их будет проверяющими друг для друга.

Итак, ключ сгенерирован и опубликован. Теперь каждый избиратель должен найти своего проверяющего, получить из базы голосов его публичный проверочный ключ $e_{проверочный}$, сгенерировать проверочную информацию

$I = V + E_{е_{\Large проверочный\ проверяющего}}(i + m + E_{e_{\Large личный}}(i + m))$

и анонимно отправить её в избирком. Избирком публикует её в открытом доступе и возвращает в качестве доказательства приёма

$E_{е_{\Large избиркома}}(I)$

.

Проверяющий находит $I$ проверяемого в базе по $V$, дешифрует $E_{е_{\Large проверочный}}(i + m + E_{e_{\Large личный}}(i + m))$ с помощью своего $d_{проверочный}$, с помощью $m$ демаскирует $M_m(d_{голосования})$ и $M_m(e_{проверочный})$ и проверяет что:

  • $i$ есть в базе $i$ и $K$;
  • подпись $E_{e_{\Large личный}}(i + m)$ валидна;
  • $d_{голосования}$ совпадает с хранящимся в $K$;
  • $e_{проверочный}$ совпадает с хранящимся в $K$.
Предотвращаются следующие атаки:
  • В случае, если проверяемый не предоставляет $I$, его голос не учитывается;
  • Если проверяемый предоставляет ложную информацию — проверяющий сможет доказать подлог, опубликовав свой $d_{проверочный}$;
  • Проверяющий не может опубликовать личные данные проверяемого, т.к. проверяемый так же имеет данные проверяющего и сможет привлечь его к ответственности;
  • Избирком не может создать голоса, не связанные с реальной личностью;
  • Проверяемый не мог подменить ключи, заявленные в контракте;
  • Избиратель не может проголосовать дважды, т.к. имеет на руках только один подписанный избиркомом ключ;
  • Избирком не может подменить $c$, т.к. не обладает $e_{голосования}$.

Результаты

Недостатки протокола:
  • К сожалению, полной анонимности достичь не удалось: один случайный избиратель узнает, за кого вы проголосовали;
  • Протокол не защищает от покупки голоса: избиратель может доказать, что голосовал именно так, как заявлял;
  • Протокол неудобен для использования для не имеющих доступа к интернету людей: минимум 2 раза требует подключения к интернету (вероятно, в избирательном участке). Более того, избирательный участок может отследить голос и деанонимизировать избирателя. Вероятно, можно решить первую проблему, разрешив избирателю отказаться от роли проверяющего и добавив признак этого в контракт и голос. Недостающие проверки будут распределены между оставшимися избирателями;
  • Протокол не защищает от следующей проблемы: избирком может просто отказаться принимать «неправильный» голос. В качестве решения можно использовать независимую площадку (например, соцсеть), приравняв публикацию голоса в ней к отсылке его в избирком.
Также, возможно, этап проверки можно упростить и сделать более анонимным, используя доказательства с нулевым разглашением. К сожалению, я пока не знаю, как это сделать и можно ли.

Если вы знаете, пишите в комментариях. Также пишите, если знаете, как улучшить протокол, нашли ошибку или уязвимость, и иную конструктивную критику.