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

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

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

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

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


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

  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 раза требует подключения к интернету (вероятно, в избирательном участке). Более того, избирательный участок может отследить голос и деанонимизировать избирателя. Вероятно, можно решить первую проблему, разрешив избирателю отказаться от роли проверяющего и добавив признак этого в контракт и голос. Недостающие проверки будут распределены между оставшимися избирателями;
  • Протокол не защищает от следующей проблемы: избирком может просто отказаться принимать «неправильный» голос. В качестве решения можно использовать независимую площадку (например, соцсеть), приравняв публикацию голоса в ней к отсылке его в избирком.

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

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

Подробнее
Реклама
Комментарии 52
  • 0
    В моем «дивном новом мире» пункт 3 требований не нужен. После чего собственно и механизмы упрощаются на порядок.
    • 0
      То же самое собирался написать. Этим страхом, мол, а вдруг придёт к власти еще один Гитлер и всех перевешает, кто против него проголосовал, — и создают себе теневое пространство для всяких махинаций.
      • 0

        Это правило нужно не из-за страха, а чтобы нельзя было покупать голоса избирателей.

        • 0

          Вообще-то, анонимность и невозможность раскрыть свой голос — это несколько разные вещи.

          • 0
            Зато спасает от административного ресурса, когда даже платить не надо, напишут, что надо.

            Вообще, даже не очень понятно, почему брать деньги за голос — плохо. Я же могу из любых соображений решать, почему не из финансового сиюминутного? «Морда его не нравится» — нормальная причина, а «мне его конкурент денег дал» — нет?

            Кроме того, мне сложно представить тут хорошую стратегию траты средств. Часть народу уже за меня, им платить — пустая трата денег, и так бы проголосовали. Значит надо искать тех, кто сомневается, но бабки им помогут осознать мою крутость. Как их найти? И как при этом их купить, но не растерять голоса тех, кого я посчитал и так лояльными, денег им не дал, а они обиделись, что я такой жлоб, и переметнулись?

            Вряд ли это выгоднее, чем просто толкать популистские речи по ящику. Ну тк аудитория одна, остальные избиратели или много запросят за голос или вообще откажутся. А голоса у нас эквивалентные.
            • 0
              «Морда его не нравится» — нормальная причина, а «мне его конкурент денег дал» — нет?

              А как вам причина "мне его конкурент обещал сломать ноги, если я проголосую за него?"
              Основная причина, по которой необходима анонимность — исключение давления, например, в госучреждениях, с обещанием выставить на мороз тех, кто проголосовал не за правящую партию.

              • 0
                Уже более похоже на то, чего стоит опасаться.
                Но сразу тянет на судебное разбирательство.
                И есть сомнения, что в нормальных странах со стабильным демократическим механизмом такое прокатит. Это ж скандал.
                • +1

                  В этом и плюс криптографии — её работоспособность не зависит от демократичности страны.

                  • 0
                    криптография обычно сама по себе ничего не гарантирует, максимум достоверно передаёт информацию.

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

                    убедят открытые данные: вот на альтернативном сайте люди так же расшарили информацию, кто как голосовал, и там 20% за кандидата, а избирком насчитал 146.

                    и лучше бы иметь возможность изъявлять поддержку партии или человеку не раз в несколько лет, а в любое время — это был бы годный источник статистики по настроениям в обществе. просто в какие-то моменты фиксировать.

                    не так много негативных последствий отсутствия анонимности я ожидаю от такой системы. больше шума и скандалов — не смертельно.
                    • 0
                      и лучше бы иметь возможность изъявлять поддержку партии или человеку не раз в несколько лет, а в любое время — это был бы годный источник статистики по настроениям в обществе. просто в какие-то моменты фиксировать.

                      Вот это дело. Будет мгновенная обратная связь. Можно ещё и отзывы писать чтоб было понятно за что.

                      • 0

                        Вы статью-то прочитали? Если да, расскажите, пожалуйста, что именно в этой схеме вас не убеждает.

                        • 0
                          Я-то может и разберусь в криптографии, а большинство населения — нет.
                          Для них это какая-то магия, которую никак не проверишь.
                          А публичные данные можно проверить, хотя бы в экселе по своему району.
                      • 0
                        Еще как зависит. Любая криптография ломается терморектальным криптоанализом, вне зависимости от длины ключа и стойкости алгоритма шифрования. И если ТК можно практиковать в какой-либо стране (например, США), пускай и в лайт-версии в виде полиграфа с перебором символов, то ее и будут практиковать. В странах демократических, например, в Швейцарии, или европейских карликах, да, будет работать.
          • 0
            почему столь важное событие, легитимность которого столь необходимо защитить, использует механизмы защиты многовековой давности? Особенно это странно, учитывая то, что схему для голосования, пусть и далеко не идеальную, но значительно лучшую, чем текущая, может придумать даже человек, разбирающийся в криптографии на начальном уровне.


            Cui prodest
            • 0
              Протокол не защищает от покупки голоса: избиратель может доказать, что голосовал именно так, как заявлял;

              Покупка, давление, что угодно. В текущем «многовековом» протоколе пункт 3 требований выполняется, тут — нет.
              • 0
                Если покупатель в сговоре с избиркомом — не защищает.
                • 0
                  Защищает до тех пор, пока вы голосуете в кабинке без свидетелей.
                  • 0

                    Кто мешает избирателю сделать фотографию бюллетеня со своим паспортом в кабинке без свидетелей и предъявить её покупателю?

                    • 0
                      Это уже не «без свидетелей»
                      • +1

                        И тем не менее, возможность есть

                      • 0
                        нитка/карандаш/фотошоп
                        • 0

                          1,2) Потребовать обязательно ручкой
                          3) Массовым не станет

                  • 0
                    В текущем «многовековом» протоколе пункт 3 требований выполняется

                    С какой это стати? У избиркома есть данные о каждом избирателе — за кого он голосовал.

                    • 0

                      Каким образом?

                      • 0

                        Я почему-то думал, что бюллетени имеют номер. Был не прав, пункт 3 выполняется.

                        • 0

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

                        • 0
                          С чего вдруг? Только данные по явке.
                      • 0
                        — Как голосующему узнать общие результаты голосования?
                        — Как проверить что они достоверные?
                        — Как убедится в том что реализация механизма подсчета результатов не содержит подтасовки?

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

                          Все выборы с находятся в открытом виде. Каждый может посчитать их самостоятельно.

                        • –4
                          Голосование голосованию рознь. Конечно, есть множество областей, где можно и нужно внедрять электронное голосование. Но в критических вопросах вроде выборов государственной власти, при условии наличия заинтересованных и влиятельных сил, располагающими большими средствами и широкими возможностями, полагаться на алгоритмы с недоказанной строго математической сложностью взлома (к коим относятся асимметричные), в лучшем случае означает поставить под сомнение результаты выборов. В худшем — отдать результаты в чужие и скорее всего недобросовестные руки.
                          • 0

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

                          • 0

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

                            • 0
                              Все это красиво, но не реально. Достаточно ужесточить наказание за вброс и повторное голосование до 10 лет тюрьмы, а не как у нас штраф 200-300 тыс рублей и поверьте, никому в голову не придет мухлевать.
                              • 0

                                На эту тему Михаил Барщевский хорошо высказался: суть не в размере наказания, а в его неотвратимости. Какой толк в самых жестоких законах, когда никого не наказывают в случае их нарушения?

                                • +1

                                  Китай тоже так подумал про коррупцию. Не помогло.

                                • 0
                                  > Избиратель регистрируется в избиркоме, предоставляя свои личные данные

                                  Что мешает зарегистрироваться по 10 раз в 10 избиркомах и проголосовать за нужного кандидата?
                                  • 0

                                    Единая база избиркома, регистрация по месту жительства. Даже если этого не заметят в избиркоме — это будет видно в открытой базе контрактов.

                                  • 0
                                    Далеко не все получают ключи для голосования — просто так их не выдать, нужно что бы избиратель пришел и получил. Избирком генерирует 10-30 млн. «мертвых душ», так что бы не выйти за предел численности голосующего населения и заруливает любые выборы.
                                    • 0

                                      Скажите честно: вы статью-то читали?

                                      • +1
                                        Читал. Пусть я буду проверяющим одной из учетки. Как убедится, что эта запись Иванов И.И. из села Иванова, в 3 тыс км от меня, 1950 года рождения, не принадлежит «мертвой душе»?
                                        • 0

                                          Посмотреть в открытой базе цифровых подписей

                                    • +1

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

                                      • 0

                                        А при чём здесь социальная инженерия?

                                        • 0

                                          Подкуп избирателей. Угрозы, манипуляции, ложь. Можно управлять исходом выборов без прямых подтасовок

                                          • 0
                                            если люди согласны продать свой голос, то бессмысленно этому противостоять криптографей.
                                      • 0

                                        Мне больше нравится идея с ICO, она была в плане шутки высказана, но не такая уж и глупая.


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

                                        • +1
                                          Кто больше купил, у того больше голосов? :)
                                        • 0
                                          1. А как проверить, что голосовал именно тот человек? Как сопоставить живого человека и ключ?
                                          2. Как проверить, что человек проголосовал добровольно, и никто рядом с ним не стоял во время голосования с автоматом? Т.е. что оно было действительно тайным и добровольным?
                                          3. Как отфильтровать после голосования тех, кого заставили проголосовать, от тех, кто во время очередного обострения волшебные таблетки от галюцинаций и голосов в голове принять забыл?
                                          4. Как гарантировать отсутствие заразы на клиентском терминале (комп, телефон, умные часы, etc), которая «проголосует» как надо? (допустим, в варианте, когда избиратель забыл проголосовать?
                                          5. Проверка правильности подсчета в случае теракта в датацентре.
                                          • 0

                                            1) Дешифровать проверочную информацию I, зашифрованную вашим ключом, получить оттуда маскирующий множитель m и информацию о человеке i, демаскировать dголосования в контракте этого человека (контракт находим по i), проверить, что он соответствует тому, который находится в его голосе V.


                                            2, 3) Административными методами.


                                            4) Стандартные методы ИБ + опенсорсное ПО для голосования. Также можно сделать отдельное устройсво для голосования, которое не выполняет никаких других функций.


                                            5) В случае теракта (да и без него) по-хорошему, избиратель должен проверить, что его голос содержится в базе, и если он от туда пропал — послать его ещё раз.

                                            • 0
                                              1. Я про другое. Как проверить, что кнопки нажимал именно Вася Пупкин, а не его жена, сосед,… Ну или злоумышленник, укравший ключ и выдающий себя за Васю?
                                              2,3 это как? К каждому столбу мента по поставишь.
                                              4. Я как раз про клиентское устройство. И тут, увы, оба возможных решения плохие:
                                              4а: как в сберовском приложении: если обнаружены признаки небезопасности, операции невозможны. Т.е. избирателю отказывается в праве голоса. Что противоречит принципам демократии.
                                              4б. отдельное устройство. А значит, отдельные деньги на гаджет, который более ни на что не пригоден. И кто может гарантировать, что там нет заложенных государством бэкдоров? Как известно, в миллиардах строк кода легко прячутся десятилетиями любые баги, несмотря на открытость исходников.

                                              Резюмируя, проблема организации электронного голосования не имеет никакого отношения к ИТ, криптографии, и т.п… Вообще никакого. По одной простой причине — из системы невозможно исключить слабое звено в лице избирателя.
                                              Следствие: в демократическом обществе 100%-но электронного голосования быть не может, если все члены общества не знают друг друга в лицо и 100%-но доверяют друг другу.
                                              • 0

                                                1) Административными методами.
                                                2, 3) Так же, как раскрываются любые другие преступления. Следствие, улики, свидетели, суд.
                                                4а) Надуманная проблема. Устраните небезопасность и голосуйте.
                                                4б) Можно выдавать его за счёт государства. Гарантируется возможностью проверить прошивку и сниффингом трафика. Баги != бэкдоры.


                                                Резюмируя, проблема организации электронного голосования не имеет никакого отношения к ИТ, криптографии, и т.п… Вообще никакого. По одной простой причине — из системы невозможно исключить слабое звено в лице избирателя.

                                                Да, а ещё системы электронного голосования не решают проблемы перенаселения в Китае, поиска воды на Марсе и испорченных продуктов в супермаркете. Или, может, каждая система должна решать только относящиеся к ней проблемы?

                                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.