На Хабре уже публиковался ряд статей о электронных выборах (раз, два, три), однако я не нашёл проработанного и отвечающего основным требованиям протокола. Так что встречайте: мой вариант протокола электронного голосования.
Схема получилась довольно несложной, так что весьма вероятно, что я изобрёл велосипед.
Требования к системе
Что же мы хотим получить на выходе? Я сформулировал следующие требования:
- Возможность независимого контроля;
- Стойкость к подтасовкам, со стороны избиркома, избирателей и третьих лиц
- Невозможность узнать, как проголосовал конкретный избиратель
Tl;dr: краткое описание протокола
- Избиратель регистрируется в избиркоме, предоставляя свои личные данные, маскированные ключ голосования и ключ проверки. Избирком подписывает маскированный ключ голосования;
- Избиратель демаскирует его и получает подписанный ключ голосования, создаёт на его основе анонимный голос и публикует его;
- Каждому голосу подбирается проверяющий из числа избирателей. Владелец голоса отсылает свои личные данные проверяющему с помощью его публичного ключа. Проверяющий проверяет, что голос соответствует реальному человеку.
Подробное описание протокола
В протоколе я использовал всего 2 криптографических примитива: ассиметричное шифрование и алгоритм слепой подписи. Естественно, операции шифрования и маскировки должны быть коммутативны друг относительно друга.
Примечание: операция хеширования при подписывании, если она требуется, будет опускаться.
– ключ дешифрования;
– маскирующий множитель;
– шифрование ключом k;
– дешифрование ключом k;
– маскировка множителем m;
– демаскировка множителем m;
– информация о человеке;
– выбор;
– контракт;
– голос;
– информация для проверки
0. Исходные данные
Избиратель:
— ключ шифрования (закрытый) личной ЭЦП избирателя;
, — ключи шифрования и дешифрования. Создаются избирателем для конкретного голосования;
— маскирующий множитель. Создаётся избирателем для конкретного голосования;
, — пара ключей для этапа проверки. Создаётся избирателем для конкретного голосования.
Публичный репозиторий личных данных:
Для каждого гражданина хранится следующая информация:
— информация об избирателе: ФИО, год рождения, адрес прописка и т. д.; — публичный ключ личной ЭЦП;
— государственная подпись, удостоверяющая верность данных.
Так же в репозитории хранятся:
— публичный ключ государства;
— публичный ключ избиркома.
Государство:
— приватный ключ государства.
Избирком:
— приватный ключ избиркома.
Примечание: я использовал допущение, что на момент начала голосования информация в репозитории верна: каждому человеку взаимно однозначно соответствует ключ ЭЦП, там нет «мёртвых душ». Механизмы проверки этой информации я рассматривать не буду: мне кажется, они должны быть скорее административными, чем математическими. Также информация предполагается неизменяемой в течение всего голосования.
1. Регистрация
Каждый избиратель предъявляет свои данные избиркому. Он проверяет, что избиратель ещё не зарегистрирован и имеет избирательное право. После проверки комиссия вместе с избирателем создаёт то, что я буду далее называть контрактом.
Контракт содержит следующие данные:
— идентификационные данные избирателя
— замаскированный секретным множителем избирателя ключ дешифрования для голосования
— замаскированный секретным множителем избирателя ключ шифрования для проверки
— замаскированный секретным множителем избирателя ключ дешифрования для голосования, подписанный избиркомом
Эта информация подписывается как избиркомом, так и избирателем:
Все контракты публикуется избиркомом.
На данном этапе предотвращаются следующие атаки:
- Избирком откажется публиковать контракт. В таком случае, избиратель сможет доказать его существование, т.к. он подписан избиркомом;
- Избиратель попытается зарегистрироваться ещё раз. Избирком может доказать, что избиратель уже регистрировался с помощью его подписи;
- Избирком зарегистрирует несуществующих людей. В таком случае любой наблюдатель сможет доказать это, показав, что из данных нет в репозитории личных данных;
- Избирком не может зарегистрировать реальных людей без их присутствия, т.к. не обладает их приватным ключом
2. Голосование
Избиратель демаскирует подписанный ключ для голосования:
И создаёт не связанный с его личностью голос:
где — выбор кандидата.
Избиратель анонимно отправляет голос в избирком. Избирком публикует его в открытом доступе и возвращает в качестве доказательства приёма .
3. Проверка
К сожалению, на прошлом этапе избирком мог создать сколько угодно голосов, не связанных с реальными личностями, поэтому необходима проверка каждого голоса. Кому поручить проверку? Я считаю, что лучше всего обратиться к принципам демархии и поручить проверку случайному избирателю. Можно придумать бесконечное количество схем распределения пар проверяющий-проверяемый на множестве голосов, но мне кажется оптимальным следующий: разбить множество на пары и назначить их проверяющими друг для друга. Таким образом разгласивший информацию проверяющий может быть привлечён к ответственности проверяемым. Какая бы схема не использовалась, алгоритм её формирования должен быть опубликован до начала регистрации, и зависеть от ключа, неизвестного до окончания регистрации. Например, ключ можно генерировать из курсов валют, или публично и совместно кандидатами (например, с помощью лототрона). Если проигнорировать это условие, избирком сможет после окончания регистрации найти и добавить в список такое множество фальшивых голосов, что все они или большинство их будет проверяющими друг для друга.
Итак, ключ сгенерирован и опубликован. Теперь каждый избиратель должен найти своего проверяющего, получить из базы голосов его публичный проверочный ключ , сгенерировать проверочную информацию
и анонимно отправить её в избирком. Избирком публикует её в открытом доступе и возвращает в качестве доказательства приёма .
Проверяющий находит проверяемого в базе по , дешифрует с помощью своего , с помощью демаскирует и и проверяет что:
- есть в базе и ;
- подпись валидна;
- совпадает с хранящимся в ;
- совпадает с хранящимся в .
Предотвращаются следующие атаки:
- В случае, если проверяемый не предоставляет , его голос не учитывается;
- Если проверяемый предоставляет ложную информацию — проверяющий сможет доказать подлог, опубликовав свой ;
- Проверяющий не может опубликовать личные данные проверяемого, т.к. проверяемый так же имеет данные проверяющего и сможет привлечь его к ответственности;
- Избирком не может создать голоса, не связанные с реальной личностью;
- Проверяемый не мог подменить ключи, заявленные в контракте;
- Избиратель не может проголосовать дважды, т.к. имеет на руках только один подписанный избиркомом ключ;
- Избирком не может подменить , т.к. не обладает .
Результаты
Недостатки протокола:
- К сожалению, полной анонимности достичь не удалось: один случайный избиратель узнает, за кого вы проголосовали;
- Протокол не защищает от покупки голоса: избиратель может доказать, что голосовал именно так, как заявлял;
- Протокол неудобен для использования для не имеющих доступа к интернету людей: минимум 2 раза требует подключения к интернету (вероятно, в избирательном участке). Более того, избирательный участок может отследить голос и деанонимизировать избирателя. Вероятно, можно решить первую проблему, разрешив избирателю отказаться от роли проверяющего и добавив признак этого в контракт и голос. Недостающие проверки будут распределены между оставшимися избирателями;
- Протокол не защищает от следующей проблемы: избирком может просто отказаться принимать «неправильный» голос. В качестве решения можно использовать независимую площадку (например, соцсеть), приравняв публикацию голоса в ней к отсылке его в избирком.
Также, возможно, этап проверки можно упростить и сделать более анонимным, используя доказательства с нулевым разглашением. К сожалению, я пока не знаю, как это сделать и можно ли.
Если вы знаете, пишите в комментариях. Также пишите, если знаете, как улучшить протокол, нашли ошибку или уязвимость, и иную конструктивную критику.
Комментарии (52)
RidgeA
11.08.2017 10:57почему столь важное событие, легитимность которого столь необходимо защитить, использует механизмы защиты многовековой давности? Особенно это странно, учитывая то, что схему для голосования, пусть и далеко не идеальную, но значительно лучшую, чем текущая, может придумать даже человек, разбирающийся в криптографии на начальном уровне.
Cui prodest
ploop
11.08.2017 11:02Протокол не защищает от покупки голоса: избиратель может доказать, что голосовал именно так, как заявлял;
Покупка, давление, что угодно. В текущем «многовековом» протоколе пункт 3 требований выполняется, тут — нет.AndrewRo Автор
11.08.2017 11:55В текущем «многовековом» протоколе пункт 3 требований выполняется
С какой это стати? У избиркома есть данные о каждом избирателе — за кого он голосовал.
ivan386
11.08.2017 12:05Каким образом?
AndrewRo Автор
11.08.2017 12:18Я почему-то думал, что бюллетени имеют номер. Был не прав, пункт 3 выполняется.
AndrewRo Автор
11.08.2017 14:23Кстати, то, что бюллетени формально анонимны, не значит, что система неуязвима. При желании, можно использовать, например, принтерную стеганографию для деанонимизации избирателя.
fedorro
11.08.2017 11:07— Как голосующему узнать общие результаты голосования?
— Как проверить что они достоверные?
— Как убедится в том что реализация механизма подсчета результатов не содержит подтасовки?
Ну проверил ты что человек проголосовал как-то, а потом выходят оглашать результаты и говорят нужные цифры, даже не считая голоса, например.AndrewRo Автор
11.08.2017 11:49Все выборы с находятся в открытом виде. Каждый может посчитать их самостоятельно.
sena
11.08.2017 11:46-4Голосование голосованию рознь. Конечно, есть множество областей, где можно и нужно внедрять электронное голосование. Но в критических вопросах вроде выборов государственной власти, при условии наличия заинтересованных и влиятельных сил, располагающими большими средствами и широкими возможностями, полагаться на алгоритмы с недоказанной строго математической сложностью взлома (к коим относятся асимметричные), в лучшем случае означает поставить под сомнение результаты выборов. В худшем — отдать результаты в чужие и скорее всего недобросовестные руки.
AndrewRo Автор
11.08.2017 12:05Довольно странное замечание. Конечно, лучше было бы иметь алгоритмы с доказанной криптостойкостью. Но в практическом смысле разница небольшая. В текущий момент для них хотя бы неизвестны атаки, когда атаки на абстрактного "товарища Чурова" известны уже тысячи лет.
rumkin
11.08.2017 14:06Здесь лучше использовать децентрализованную систему на сети доверия, где каждый участник и голосующий и избирком в одном.
svcoder
11.08.2017 18:39Все это красиво, но не реально. Достаточно ужесточить наказание за вброс и повторное голосование до 10 лет тюрьмы, а не как у нас штраф 200-300 тыс рублей и поверьте, никому в голову не придет мухлевать.
rumkin
11.08.2017 19:52На эту тему Михаил Барщевский хорошо высказался: суть не в размере наказания, а в его неотвратимости. Какой толк в самых жестоких законах, когда никого не наказывают в случае их нарушения?
porutchik
11.08.2017 20:47> Избиратель регистрируется в избиркоме, предоставляя свои личные данные
Что мешает зарегистрироваться по 10 раз в 10 избиркомах и проголосовать за нужного кандидата?AndrewRo Автор
11.08.2017 22:17Единая база избиркома, регистрация по месту жительства. Даже если этого не заметят в избиркоме — это будет видно в открытой базе контрактов.
NoRegrets
11.08.2017 21:40Далеко не все получают ключи для голосования — просто так их не выдать, нужно что бы избиратель пришел и получил. Избирком генерирует 10-30 млн. «мертвых душ», так что бы не выйти за предел численности голосующего населения и заруливает любые выборы.
Gorthauer87
11.08.2017 22:31+1Кажется здесь нужен блокчейн в качестве базы данных. Можно на эфире смарт контракт создать.
А против социальной инженерии ни один алгоритм не поможет.AndrewRo Автор
11.08.2017 22:40А при чём здесь социальная инженерия?
Gorthauer87
11.08.2017 22:41Подкуп избирателей. Угрозы, манипуляции, ложь. Можно управлять исходом выборов без прямых подтасовок
Ivan22
14.08.2017 12:09если люди согласны продать свой голос, то бессмысленно этому противостоять криптографей.
Gorthauer87
14.08.2017 12:37Мне больше нравится идея с ICO, она была в плане шутки высказана, но не такая уж и глупая.
Избирком выпускает токены, люди их просто покупают, а дальше ими же и голосуют. А дальше с помощью этих же токенов уже влияют на те или иные решения выигравшего кандидата. Вроде бы конечно государство превращается в большое акционерное общество, но кажется мне, что это не так уж и плохо.
CyaN
14.08.2017 17:211. А как проверить, что голосовал именно тот человек? Как сопоставить живого человека и ключ?
2. Как проверить, что человек проголосовал добровольно, и никто рядом с ним не стоял во время голосования с автоматом? Т.е. что оно было действительно тайным и добровольным?
3. Как отфильтровать после голосования тех, кого заставили проголосовать, от тех, кто во время очередного обострения волшебные таблетки от галюцинаций и голосов в голове принять забыл?
4. Как гарантировать отсутствие заразы на клиентском терминале (комп, телефон, умные часы, etc), которая «проголосует» как надо? (допустим, в варианте, когда избиратель забыл проголосовать?
5. Проверка правильности подсчета в случае теракта в датацентре.AndrewRo Автор
14.08.2017 17:381) Дешифровать проверочную информацию I, зашифрованную вашим ключом, получить оттуда маскирующий множитель m и информацию о человеке i, демаскировать dголосования в контракте этого человека (контракт находим по i), проверить, что он соответствует тому, который находится в его голосе V.
2, 3) Административными методами.
4) Стандартные методы ИБ + опенсорсное ПО для голосования. Также можно сделать отдельное устройсво для голосования, которое не выполняет никаких других функций.
5) В случае теракта (да и без него) по-хорошему, избиратель должен проверить, что его голос содержится в базе, и если он от туда пропал — послать его ещё раз.
CyaN
14.08.2017 18:081. Я про другое. Как проверить, что кнопки нажимал именно Вася Пупкин, а не его жена, сосед,… Ну или злоумышленник, укравший ключ и выдающий себя за Васю?
2,3 это как? К каждому столбу мента по поставишь.
4. Я как раз про клиентское устройство. И тут, увы, оба возможных решения плохие:
4а: как в сберовском приложении: если обнаружены признаки небезопасности, операции невозможны. Т.е. избирателю отказывается в праве голоса. Что противоречит принципам демократии.
4б. отдельное устройство. А значит, отдельные деньги на гаджет, который более ни на что не пригоден. И кто может гарантировать, что там нет заложенных государством бэкдоров? Как известно, в миллиардах строк кода легко прячутся десятилетиями любые баги, несмотря на открытость исходников.
Резюмируя, проблема организации электронного голосования не имеет никакого отношения к ИТ, криптографии, и т.п… Вообще никакого. По одной простой причине — из системы невозможно исключить слабое звено в лице избирателя.
Следствие: в демократическом обществе 100%-но электронного голосования быть не может, если все члены общества не знают друг друга в лицо и 100%-но доверяют друг другу.AndrewRo Автор
14.08.2017 18:211) Административными методами.
2, 3) Так же, как раскрываются любые другие преступления. Следствие, улики, свидетели, суд.
4а) Надуманная проблема. Устраните небезопасность и голосуйте.
4б) Можно выдавать его за счёт государства. Гарантируется возможностью проверить прошивку и сниффингом трафика. Баги != бэкдоры.
Резюмируя, проблема организации электронного голосования не имеет никакого отношения к ИТ, криптографии, и т.п… Вообще никакого. По одной простой причине — из системы невозможно исключить слабое звено в лице избирателя.
Да, а ещё системы электронного голосования не решают проблемы перенаселения в Китае, поиска воды на Марсе и испорченных продуктов в супермаркете. Или, может, каждая система должна решать только относящиеся к ней проблемы?
Ivan22
В моем «дивном новом мире» пункт 3 требований не нужен. После чего собственно и механизмы упрощаются на порядок.
guai
То же самое собирался написать. Этим страхом, мол, а вдруг придёт к власти еще один Гитлер и всех перевешает, кто против него проголосовал, — и создают себе теневое пространство для всяких махинаций.
mayorovp
Это правило нужно не из-за страха, а чтобы нельзя было покупать голоса избирателей.
AndrewRo Автор
Вообще-то, анонимность и невозможность раскрыть свой голос — это несколько разные вещи.
guai
Зато спасает от административного ресурса, когда даже платить не надо, напишут, что надо.
Вообще, даже не очень понятно, почему брать деньги за голос — плохо. Я же могу из любых соображений решать, почему не из финансового сиюминутного? «Морда его не нравится» — нормальная причина, а «мне его конкурент денег дал» — нет?
Кроме того, мне сложно представить тут хорошую стратегию траты средств. Часть народу уже за меня, им платить — пустая трата денег, и так бы проголосовали. Значит надо искать тех, кто сомневается, но бабки им помогут осознать мою крутость. Как их найти? И как при этом их купить, но не растерять голоса тех, кого я посчитал и так лояльными, денег им не дал, а они обиделись, что я такой жлоб, и переметнулись?
Вряд ли это выгоднее, чем просто толкать популистские речи по ящику. Ну тк аудитория одна, остальные избиратели или много запросят за голос или вообще откажутся. А голоса у нас эквивалентные.
AndrewRo Автор
А как вам причина "мне его конкурент обещал сломать ноги, если я проголосую за него?"
Основная причина, по которой необходима анонимность — исключение давления, например, в госучреждениях, с обещанием выставить на мороз тех, кто проголосовал не за правящую партию.
guai
Уже более похоже на то, чего стоит опасаться.
Но сразу тянет на судебное разбирательство.
И есть сомнения, что в нормальных странах со стабильным демократическим механизмом такое прокатит. Это ж скандал.
AndrewRo Автор
В этом и плюс криптографии — её работоспособность не зависит от демократичности страны.
guai
криптография обычно сама по себе ничего не гарантирует, максимум достоверно передаёт информацию.
в данном случае, если я не доверяю избиркому, то криптография меня не убедит. он мог ту информацию выкинуть, другую нарисовать.
убедят открытые данные: вот на альтернативном сайте люди так же расшарили информацию, кто как голосовал, и там 20% за кандидата, а избирком насчитал 146.
и лучше бы иметь возможность изъявлять поддержку партии или человеку не раз в несколько лет, а в любое время — это был бы годный источник статистики по настроениям в обществе. просто в какие-то моменты фиксировать.
не так много негативных последствий отсутствия анонимности я ожидаю от такой системы. больше шума и скандалов — не смертельно.
ivan386
Вот это дело. Будет мгновенная обратная связь. Можно ещё и отзывы писать чтоб было понятно за что.
AndrewRo Автор
Вы статью-то прочитали? Если да, расскажите, пожалуйста, что именно в этой схеме вас не убеждает.
guai
Я-то может и разберусь в криптографии, а большинство населения — нет.
Для них это какая-то магия, которую никак не проверишь.
А публичные данные можно проверить, хотя бы в экселе по своему району.