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

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

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

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


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

  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)


  1. Ivan22
    11.08.2017 10:52

    В моем «дивном новом мире» пункт 3 требований не нужен. После чего собственно и механизмы упрощаются на порядок.


    1. guai
      11.08.2017 14:10

      То же самое собирался написать. Этим страхом, мол, а вдруг придёт к власти еще один Гитлер и всех перевешает, кто против него проголосовал, — и создают себе теневое пространство для всяких махинаций.


      1. mayorovp
        11.08.2017 15:31

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


        1. AndrewRo Автор
          11.08.2017 15:54

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


        1. guai
          11.08.2017 17:39

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

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

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

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


          1. AndrewRo Автор
            11.08.2017 17:46

            «Морда его не нравится» — нормальная причина, а «мне его конкурент денег дал» — нет?

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


            1. guai
              11.08.2017 18:48

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


              1. AndrewRo Автор
                11.08.2017 22:15
                +1

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


                1. guai
                  11.08.2017 22:45

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

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

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

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

                  не так много негативных последствий отсутствия анонимности я ожидаю от такой системы. больше шума и скандалов — не смертельно.


                  1. ivan386
                    11.08.2017 23:03

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

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


                  1. AndrewRo Автор
                    11.08.2017 23:55

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


                    1. guai
                      14.08.2017 11:34

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


  1. RidgeA
    11.08.2017 10:57

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


    Cui prodest


  1. ploop
    11.08.2017 11:02

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

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


    1. AndrewRo Автор
      11.08.2017 11:44

      Если покупатель в сговоре с избиркомом — не защищает.


      1. ploop
        11.08.2017 12:15

        Защищает до тех пор, пока вы голосуете в кабинке без свидетелей.


        1. AndrewRo Автор
          11.08.2017 12:23

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


          1. ploop
            11.08.2017 13:52

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


            1. AndrewRo Автор
              11.08.2017 13:58
              +1

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


          1. Zolg
            13.08.2017 16:12

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


            1. AndrewRo Автор
              14.08.2017 12:29

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


    1. AndrewRo Автор
      11.08.2017 11:55

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

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


      1. ivan386
        11.08.2017 12:05

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


        1. AndrewRo Автор
          11.08.2017 12:18

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


        1. AndrewRo Автор
          11.08.2017 14:23

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


      1. ploop
        11.08.2017 12:14

        С чего вдруг? Только данные по явке.


  1. fedorro
    11.08.2017 11:07

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

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


    1. AndrewRo Автор
      11.08.2017 11:49

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


  1. sena
    11.08.2017 11:46
    -4

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


    1. AndrewRo Автор
      11.08.2017 12:05

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


  1. rumkin
    11.08.2017 14:06

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


  1. svcoder
    11.08.2017 18:39

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


    1. rumkin
      11.08.2017 19:52

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


    1. AndrewRo Автор
      11.08.2017 22:15
      +1

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


  1. porutchik
    11.08.2017 20:47

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

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


    1. AndrewRo Автор
      11.08.2017 22:17

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


  1. NoRegrets
    11.08.2017 21:40

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


    1. AndrewRo Автор
      11.08.2017 22:17

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


      1. NoRegrets
        12.08.2017 01:19
        +1

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


        1. AndrewRo Автор
          14.08.2017 12:30

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


  1. Gorthauer87
    11.08.2017 22:31
    +1

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


    1. AndrewRo Автор
      11.08.2017 22:40

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


      1. Gorthauer87
        11.08.2017 22:41

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


        1. Ivan22
          14.08.2017 12:09

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


  1. Gorthauer87
    14.08.2017 12:37

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


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


    1. CyaN
      14.08.2017 18:09
      +1

      Кто больше купил, у того больше голосов? :)


  1. CyaN
    14.08.2017 17:21

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


    1. AndrewRo Автор
      14.08.2017 17:38

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


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


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


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


      1. CyaN
        14.08.2017 18:08

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

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


        1. AndrewRo Автор
          14.08.2017 18:21

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


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

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


          1. CyaN
            14.08.2017 18:24

            In code we trust :)