Наблюдение за выборами в различных странах, осложнёнными различными скандалами вокруг подтасовок, каждый раз заставляет задуматься: почему столь важное событие, легитимность которого столь необходимо защитить, использует механизмы защиты многовековой давности? Особенно это странно, учитывая то, что схему для голосования, пусть и далеко не идеальную, но значительно лучшую, чем текущая, может придумать даже человек, разбирающийся в криптографии на начальном уровне. Так уж совпало, что я отношу себя именно к таким людям, поэтому я подумал: почему бы не попробовать?
На Хабре уже публиковался ряд статей о электронных выборах (раз, два, три), однако я не нашёл проработанного и отвечающего основным требованиям протокола. Так что встречайте: мой вариант протокола электронного голосования.
Что же мы хотим получить на выходе? Я сформулировал следующие требования:
В протоколе я использовал всего 2 криптографических примитива: ассиметричное шифрование и алгоритм слепой подписи. Естественно, операции шифрования и маскировки должны быть коммутативны друг относительно друга.
Примечание: операция хеширования при подписывании, если она требуется, будет опускаться.
Для каждого гражданина хранится следующая информация:
Так же в репозитории хранятся:
— приватный ключ государства.
— приватный ключ избиркома.
Примечание: я использовал допущение, что на момент начала голосования информация в репозитории верна: каждому человеку взаимно однозначно соответствует ключ ЭЦП, там нет «мёртвых душ». Механизмы проверки этой информации я рассматривать не буду: мне кажется, они должны быть скорее административными, чем математическими. Также информация предполагается неизменяемой в течение всего голосования.
Каждый избиратель предъявляет свои данные избиркому. Он проверяет, что избиратель ещё не зарегистрирован и имеет избирательное право. После проверки комиссия вместе с избирателем создаёт то, что я буду далее называть контрактом.
Контракт содержит следующие данные:
Все контракты публикуется избиркомом.
На данном этапе предотвращаются следующие атаки:
Избиратель демаскирует подписанный ключ для голосования:
И создаёт не связанный с его личностью голос:
где — выбор кандидата.
Избиратель анонимно отправляет голос в избирком. Избирком публикует его в открытом доступе и возвращает в качестве доказательства приёма .
К сожалению, на прошлом этапе избирком мог создать сколько угодно голосов, не связанных с реальными личностями, поэтому необходима проверка каждого голоса. Кому поручить проверку? Я считаю, что лучше всего обратиться к принципам демархии и поручить проверку случайному избирателю. Можно придумать бесконечное количество схем распределения пар проверяющий-проверяемый на множестве голосов, но мне кажется оптимальным следующий: разбить множество на пары и назначить их проверяющими друг для друга. Таким образом разгласивший информацию проверяющий может быть привлечён к ответственности проверяемым. Какая бы схема не использовалась, алгоритм её формирования должен быть опубликован до начала регистрации, и зависеть от ключа, неизвестного до окончания регистрации. Например, ключ можно генерировать из курсов валют, или публично и совместно кандидатами (например, с помощью лототрона). Если проигнорировать это условие, избирком сможет после окончания регистрации найти и добавить в список такое множество фальшивых голосов, что все они или большинство их будет проверяющими друг для друга.
Итак, ключ сгенерирован и опубликован. Теперь каждый избиратель должен найти своего проверяющего, получить из базы голосов его публичный проверочный ключ , сгенерировать проверочную информацию
и анонимно отправить её в избирком. Избирком публикует её в открытом доступе и возвращает в качестве доказательства приёма .
Проверяющий находит проверяемого в базе по , дешифрует с помощью своего , с помощью демаскирует и и проверяет что:
Предотвращаются следующие атаки:
Недостатки протокола:
Также, возможно, этап проверки можно упростить и сделать более анонимным, используя доказательства с нулевым разглашением. К сожалению, я пока не знаю, как это сделать и можно ли.
Если вы знаете, пишите в комментариях. Также пишите, если знаете, как улучшить протокол, нашли ошибку или уязвимость, и иную конструктивную критику.
На Хабре уже публиковался ряд статей о электронных выборах (раз, два, три), однако я не нашёл проработанного и отвечающего основным требованиям протокола. Так что встречайте: мой вариант протокола электронного голосования.
Дисклеймер
Автор не является профессионалом в криптографии и математике, поэтому указанная схема не претендует на безошибочность или глубокую проработанность.
Схема получилась довольно несложной, так что весьма вероятно, что я изобрёл велосипед.
Схема получилась довольно несложной, так что весьма вероятно, что я изобрёл велосипед.
Требования к системе
Что же мы хотим получить на выходе? Я сформулировал следующие требования:
- Возможность независимого контроля;
- Стойкость к подтасовкам, со стороны избиркома, избирателей и третьих лиц
- Невозможность узнать, как проголосовал конкретный избиратель
Tl;dr: краткое описание протокола
- Избиратель регистрируется в избиркоме, предоставляя свои личные данные, маскированные ключ голосования и ключ проверки. Избирком подписывает маскированный ключ голосования;
- Избиратель демаскирует его и получает подписанный ключ голосования, создаёт на его основе анонимный голос и публикует его;
- Каждому голосу подбирается проверяющий из числа избирателей. Владелец голоса отсылает свои личные данные проверяющему с помощью его публичного ключа. Проверяющий проверяет, что голос соответствует реальному человеку.
Подробное описание протокола
В протоколе я использовал всего 2 криптографических примитива: ассиметричное шифрование и алгоритм слепой подписи. Естественно, операции шифрования и маскировки должны быть коммутативны друг относительно друга.
Примечание: операция хеширования при подписывании, если она требуется, будет опускаться.
Список обозначений
— ключ шифрования;
– ключ дешифрования;
– маскирующий множитель;
– шифрование ключом k;
– дешифрование ключом k;
– маскировка множителем m;
– демаскировка множителем m;
– информация о человеке;
– выбор;
– контракт;
– голос;
– информация для проверки
– ключ дешифрования;
– маскирующий множитель;
– шифрование ключом k;
– дешифрование ключом k;
– маскировка множителем m;
– демаскировка множителем m;
– информация о человеке;
– выбор;
– контракт;
– голос;
– информация для проверки
0. Исходные данные
Избиратель:
— ключ шифрования (закрытый) личной ЭЦП избирателя;
, — ключи шифрования и дешифрования. Создаются избирателем для конкретного голосования;
— маскирующий множитель. Создаётся избирателем для конкретного голосования;
, — пара ключей для этапа проверки. Создаётся избирателем для конкретного голосования.
Публичный репозиторий личных данных:
Для каждого гражданина хранится следующая информация:
— информация об избирателе: ФИО, год рождения, адрес прописка и т. д.; — публичный ключ личной ЭЦП;
— государственная подпись, удостоверяющая верность данных.
Так же в репозитории хранятся:
— публичный ключ государства;
— публичный ключ избиркома.
Государство:
— приватный ключ государства.
Избирком:
— приватный ключ избиркома.
Примечание: я использовал допущение, что на момент начала голосования информация в репозитории верна: каждому человеку взаимно однозначно соответствует ключ ЭЦП, там нет «мёртвых душ». Механизмы проверки этой информации я рассматривать не буду: мне кажется, они должны быть скорее административными, чем математическими. Также информация предполагается неизменяемой в течение всего голосования.
1. Регистрация
Каждый избиратель предъявляет свои данные избиркому. Он проверяет, что избиратель ещё не зарегистрирован и имеет избирательное право. После проверки комиссия вместе с избирателем создаёт то, что я буду далее называть контрактом.
Контракт содержит следующие данные:
— идентификационные данные избирателя
— замаскированный секретным множителем избирателя ключ дешифрования для голосования
— замаскированный секретным множителем избирателя ключ шифрования для проверки
— замаскированный секретным множителем избирателя ключ дешифрования для голосования, подписанный избиркомом
Эта информация подписывается как избиркомом, так и избирателем:
Все контракты публикуется избиркомом.
На данном этапе предотвращаются следующие атаки:
- Избирком откажется публиковать контракт. В таком случае, избиратель сможет доказать его существование, т.к. он подписан избиркомом;
- Избиратель попытается зарегистрироваться ещё раз. Избирком может доказать, что избиратель уже регистрировался с помощью его подписи;
- Избирком зарегистрирует несуществующих людей. В таком случае любой наблюдатель сможет доказать это, показав, что из данных нет в репозитории личных данных;
- Избирком не может зарегистрировать реальных людей без их присутствия, т.к. не обладает их приватным ключом
2. Голосование
Избиратель демаскирует подписанный ключ для голосования:
И создаёт не связанный с его личностью голос:
где — выбор кандидата.
Избиратель анонимно отправляет голос в избирком. Избирком публикует его в открытом доступе и возвращает в качестве доказательства приёма .
3. Проверка
К сожалению, на прошлом этапе избирком мог создать сколько угодно голосов, не связанных с реальными личностями, поэтому необходима проверка каждого голоса. Кому поручить проверку? Я считаю, что лучше всего обратиться к принципам демархии и поручить проверку случайному избирателю. Можно придумать бесконечное количество схем распределения пар проверяющий-проверяемый на множестве голосов, но мне кажется оптимальным следующий: разбить множество на пары и назначить их проверяющими друг для друга. Таким образом разгласивший информацию проверяющий может быть привлечён к ответственности проверяемым. Какая бы схема не использовалась, алгоритм её формирования должен быть опубликован до начала регистрации, и зависеть от ключа, неизвестного до окончания регистрации. Например, ключ можно генерировать из курсов валют, или публично и совместно кандидатами (например, с помощью лототрона). Если проигнорировать это условие, избирком сможет после окончания регистрации найти и добавить в список такое множество фальшивых голосов, что все они или большинство их будет проверяющими друг для друга.
Итак, ключ сгенерирован и опубликован. Теперь каждый избиратель должен найти своего проверяющего, получить из базы голосов его публичный проверочный ключ , сгенерировать проверочную информацию
и анонимно отправить её в избирком. Избирком публикует её в открытом доступе и возвращает в качестве доказательства приёма .
Проверяющий находит проверяемого в базе по , дешифрует с помощью своего , с помощью демаскирует и и проверяет что:
- есть в базе и ;
- подпись валидна;
- совпадает с хранящимся в ;
- совпадает с хранящимся в .
Предотвращаются следующие атаки:
- В случае, если проверяемый не предоставляет , его голос не учитывается;
- Если проверяемый предоставляет ложную информацию — проверяющий сможет доказать подлог, опубликовав свой ;
- Проверяющий не может опубликовать личные данные проверяемого, т.к. проверяемый так же имеет данные проверяющего и сможет привлечь его к ответственности;
- Избирком не может создать голоса, не связанные с реальной личностью;
- Проверяемый не мог подменить ключи, заявленные в контракте;
- Избиратель не может проголосовать дважды, т.к. имеет на руках только один подписанный избиркомом ключ;
- Избирком не может подменить , т.к. не обладает .
Результаты
Недостатки протокола:
- К сожалению, полной анонимности достичь не удалось: один случайный избиратель узнает, за кого вы проголосовали;
- Протокол не защищает от покупки голоса: избиратель может доказать, что голосовал именно так, как заявлял;
- Протокол неудобен для использования для не имеющих доступа к интернету людей: минимум 2 раза требует подключения к интернету (вероятно, в избирательном участке). Более того, избирательный участок может отследить голос и деанонимизировать избирателя. Вероятно, можно решить первую проблему, разрешив избирателю отказаться от роли проверяющего и добавив признак этого в контракт и голос. Недостающие проверки будут распределены между оставшимися избирателями;
- Протокол не защищает от следующей проблемы: избирком может просто отказаться принимать «неправильный» голос. В качестве решения можно использовать независимую площадку (например, соцсеть), приравняв публикацию голоса в ней к отсылке его в избирком.
Также, возможно, этап проверки можно упростить и сделать более анонимным, используя доказательства с нулевым разглашением. К сожалению, я пока не знаю, как это сделать и можно ли.
Если вы знаете, пишите в комментариях. Также пишите, если знаете, как улучшить протокол, нашли ошибку или уязвимость, и иную конструктивную критику.