Протокол электронного голосования: мой вариант

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

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

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

Что же мы хотим получить на выходе? Я сформулировал следующие требования:

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

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

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

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

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

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

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

Избиратель:

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

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

Для каждого гражданина хранится следующая информация:

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

Так же в репозитории хранятся:

$inline$d_{государственный}$inline$ — публичный ключ государства;
$inline$d_{избиркома}$inline$ — публичный ключ избиркома.

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

$inline$e_{государственный}$inline$ — приватный ключ государства.

Избирком:

$inline$e_{избиркома}$inline$ — приватный ключ избиркома.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где $inline$c$inline$ — выбор кандидата.

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

3. Проверка

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

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

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

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

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

• $inline$i$inline$ есть в базе $inline$i$inline$ и $inline$K$inline$;
• подпись $inline$E_{e_{Large личный}}(i + m)$inline$ валидна;
• $inline$d_{голосования}$inline$ совпадает с хранящимся в $inline$K$inline$;
• $inline$e_{проверочный}$inline$ совпадает с хранящимся в $inline$K$inline$.

Предотвращаются следующие атаки:

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

Результаты

Недостатки протокола:

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

Также, возможно, этап проверки можно упростить и сделать более анонимным, используя доказательства с нулевым разглашением ^[7]. К сожалению, я пока не знаю, как это сделать и можно ли.

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

Автор: AndrewRo

Источник ^[8]