В этой статье мы рассмотрим, как устроено дистанционное электронное голосование. Рассказ разбит на три части: в первой части наглядно объясняются основные идеи ДЭГ и отличие от обычного голосования. Во второй части описана работа электронного голосования, но некоторые подробности опущены. В третьей части содержится полное описание, со всеми деталями.

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

Обычно к системам электронного голосования предъявляют следующие основные требования:

Избирательное право: голосовать могут только избиратели, имеющие на это право
Тайна голосования: никто не имеет возможности узнать чужой голос
Честность: результат голосования подведён без обмана
Наблюдение: возможно проверить результат голосования и убедиться в его честности

Часть 1: Простое описание ДЭГ

В ДЭГ используются механизмы, которые отличаются от обычного голосования. В этом разделе мы рассмотрим гипотетический вариант голосования, которое использует те же идеи, что и ДЭГ, но проводится не в электронной, а в обычной форме.

Подтверждение избирательного права

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

В новом голосовании всё происходит точно так же.

Тайна голосования

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

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

Голосование

Чтобы обеспечить честность голосования, вместо бумажных бюллетеней введём специальные электронные сейфы. Внутри сейфа находятся кнопки голосования за кандидатов. При голосовании вы нажимаете кнопку и закрываете сейф. После этого сейф невозможно открыть. Затем вы разрисовываете сейф (максимально разнообразно, чтобы даже художнику сложно было подделать ваш рисунок) и несёте сдавать (напомню, что вам не обязательно сдавать сейф лично, поэтому тайна голосования не нарушается).

При приёме на сейфе выбивают номер, а вам выдают квитанцию с этим номером (он понадобится при проверке). Вы фотографируете разрисованный сейф вместе с квитанцией. Вам набивают временную татуировку о том, что вы уже голосовали, а ваш сейф доставляют на склад сейфов, где за ним можно следить по камерам.

Подведение итогов

Каким образом подсчитать голоса, если сейфы невозможно открыть? Для этого каждом сейфе есть разъёмы. Если несколько сейфов соединить проводом с компьютером, то компьютер покажет сумму голосов за каждого кандидата.

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

Наблюдение

В процессе все смотрят по камерам, что на складе никто не мухлюет
После окончания голосования любой желающий допускается к сейфам
Каждый может проверить, что его голос учтён, найдя сейф со своим номером
Проверив картинку, можно убедиться, что это именно его сейф
Каждый может соединить сейфы проводами со своим компьютером и проверить подсчёт результатов

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

Часть 2: Описание протокола ДЭГ

В этом разделе разберём как работает ДЭГ, опустив только подробности реализации криптографических схем. Представим, что нам поступил заказ на разработку системы электронного голосования.

Участники истории:

Избиратель – человек, голосующий на выборах
Система – система электронного голосования, её мы и должны разработать
Заказчик – следит за выполнением требований и выдвигает новые
Наблюдатель – проверяет честность проведения голосования

Первый вариант

Недолго думая, мы выдаём простой первый вариант:

Избиратель заходит на госуслуги и ставит галочку
Голос сохраняется в Системе
В конце голоса суммируются и выдаётся результат

Заказчик: Что вы мне показываете? Система не удовлетворяет ни одному требованию! Бюллетени не анонимные, их можно подделать или просто не учитывать, а правильность подсчёта проверить невозможно. Более того, голоса передаются в открытом виде!

Целостность: шифрование и подпись бюллетеня

Получив нагоняй от заказчика, приступаем к исправлению Системы. Начнём с шифрования и защиты бюллетеней от подделки. Для этого Избиратель и Система используют криптосистему с открытым ключом, которая позволяет шифровать и подписывать сообщения.

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

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

Заказчик: Уже лучше, но Избиратель не может убедиться, что его голос учтён. Система может без последствий выбросить голоса Избирателей, которые ей не нравятся.

Учёт бюллетеней: квитанция, блокчейн

Вносим улучшения. Все бюллетени будем хранить в открытом реестре. Когда Избиратель проголосовал, ему выдаётся квитанция с номером бюллетеня в Системе. Теперь Избиратель может проверить, что его бюллетень учтён. Для надёжности (и потому что модно-молодёжно) организуем реестр в виде блокчейна.

Заказчик: Теперь Избиратель может убедиться, что его бюллетень не потерялся, но голоса по-прежнему не анонимные. Системе известно, как проголосовал каждый Избиратель.

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

Чтобы решить проблему анонимности, разделим Систему на две части: в первой Избиратель будет подтверждать своё право голосовать, а во второй – заполнять бюллетень. При этом во вторую часть Избиратель заходит анонимно: не нужно снова заходить в госуслуги, можно сменить ip-адрес или зайти через vpn.

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

Заказчик: Между двумя частями системы есть общий признак Избирателя – его публичный ключ. Голосование по-прежнему не анонимное.

Анонимность: слепая подпись

Проблема в том, что, с одной стороны, Система должна подтвердить право Избирателя голосовать (подписать его публичный ключ). С другой стороны, она не должна узнать, какому Избирателю какой ключ принадлежит. Эту проблему решим с помощью криптографического протокола слепой подписи.

Слепая подпись – разновидность эцп, особенность которой в том, что подписывающая сторона не знает какое именно сообщение она подписывает

Теперь вместо обычной подписи Система будет подписывать публичный ключ Избирателя вслепую, что решает проблему анонимности Избирателя.

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

Списки избирателей

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

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

Зашифрованные бюллетени

Новое требование создаёт три принципиальные проблемы. Нужно, не расшифровывая бюллетени:

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

Первую проблему решим с помощью доказательств с нулевым разглашением. Этот протокол позволяет убедиться в выбранном свойстве зашифрованного сообщения без раскрытия самого сообщения.

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

Третью проблему решим с помощью так называемого “частичного расшифрования” – это криптографическое доказательство с нулевым разглашением, которое позволяет убедиться, что расшифрованный текст действительно является результатом процедуры расшифрования с использованием указанных ключей.

Заказчик: Неплохо. Но есть ещё одно требование: должно быть невозможно подвести промежуточные итоги до окончания голосования.

Невозможность подведения промежуточных итогов

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

Заказчик: Хорошо. Теперь опишите процедуру наблюдения.

Наблюдение

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

Наблюдатель в процессе голосования:

Мониторит технические характеристиками реестра
Мониторит события, которые регистрируются в Системе
Периодически сохраняет текущее состояние реестра на своих носителях

Наблюдатель после подведения итогов:

Проверяет количество бюллетеней и списки избирателей
Проверяет уникальность каждого бюллетеня
Проверяет корректность слепой подписи Системы на ключах Избирателей
Проверяет подпись Избирателя на каждом бюллетене
Проверяет доказательство корректности каждого бюллетеня
Проверяет доказательство корректности частичных расшифрований
Вычисляет результаты голосования и сравнивает их с опубликованными

Заказчик: Всё отлично! 💰💰💰

Часть 3: Описание криптографического протокола ДЭГ

В этом разделе подробно описан протокол ДЭГ и используемые криптографические решения.

Используемые криптографические схемы

Схема подписи:

# Генерация ключей 
S.KeyGen() = (private, public) 

# Формирование подписи
S.Sign(private, message) = sign

# Проверка подписи
S.Verify(public, message, sign) = true|false

Схема коммитмента (обязательств):

# Генерация ключа
C.KeyGen() = key

# Формирование коммитмента
# value - скрываемое значение
# key - ключ
C.Cmt(value, key) = com

# Проверка коммитмента
C.Open(value, com, key) = true|false

Схема слепой подписи:

# Генерация ключей
BS.KeyGen() = (private, public)

# Интерактивный протокол подписи вслепую
# Sign - функция действий подписывающего
# User - функция действий пользователя
(BS.Sign(private, public), BS.User(public, message)) = sign

# Проверка подписи
BS.Verify(public, message, sign) = true|false

Схема разделения секрета:

# Разделение секрета 
SS.Share(secret, n, t) = (s1,...,sn)

# Восстановление секрета 
SS.Combine((s1,..,st)) = secret

Специальная система шифрования:

# Генерация ключей 
SE.KeyGen() = (private_part, public_part)

# Агрегирование ключа
SE.KeyAgg(public_part1, public_part2) = key

# Шифрование 
# (m1,...,mn) - открытый текст
# parameters - свойства корректности шифрования
# (c1,...,cn) - зашифрованный текст
# d - доказательство корректности шифрования
SE.Enc(pubic, (m1,...,mn), parameters) = (c1,...,cn), d

# Проверка корректности шифрования
SE.VerifyEnc(public, (c1,...,cn), d, parameters) = true|false

# Гомоморфное сложение 
# (c1,....,cn) - сумма шифротекстов
SE.Add((c11,...,c1n), (c21,...,c2n)) = (c1,....,cn)

# Частичное расшифрование 
# (k1,...,kn) - результат частичного расшифрования
# p - доказательство, что при расшифровке использовались private_part и public_part
SE.DecPart(private_part, public_part, (c1,...,cn)) = (k1,...,kn), p

# Проверка корректности частичного расшифрования 
SE.VerifyDecPart(public_part, (c1,...,cn), p) = true|false

# Агрегирование результатов
SE.DecAgg(public_part1, public_part2, (c1,...,cn), (k11,...,k1n), (k21,...,k2n)) = (m1,...,mn)

Формирование списка избирателей

Система генерирует ключ коммитмента:
$K_{com} = C.KeyGen()$

Система формирует коммитмент для каждого избирателя из списка:
$com_{СНИЛС} = C.Cmt(СНИЛС, K_{com})$

Система публикует список коммитментов.

Инициализация системы

Система генерирует ключи для слепой подписи:
$$(sk_{blind}, pk_{blind}) = BS.KeyGen()$$

Система генерирует две пары ключей шифрования:
$$(sk, pk) = SE.KeyGen()$$
$$(sk_{div}, pk_{div}) = SE.KeyGen()$$

Система генерирует ключ шифрования бюллетеней:
$$pkey = SE.KeyAgg(pk, pk_{div})$$

Секретный ключ $sk_{div}$ публично разделяется с помощью схемы Шамира:
$$(s_1, …, s_m) = SS.Share(sk_{div}, m, k)$$

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

Получение бюллетеня

Избиратель обращается е сервису Аутентификации (заходит в госуслуги через ЕСИА)

Система проверяет, что Избиратель есть в списках и ещё не получал бюллетень

Избиратель генерирует пару ключей:
$$(sk_{izb}, pk_{izb})$$

Система вслепую подписывает публичный ключ Избирателя:
$$\sigma_{blind} = (BS.Sign(sk_{blind}, pk_{blind}), BS.User(pk_{blind}, pk_{izb}))$$

Система генерирует коммитмент получения бюллетеня: $com_{pas} = C.Cmt(СНИЛС, Паспорт, K_{com})$

Система публикует коммитмент

Голосование

Избиратель анонимно получает бюллетень голосования. Бюллетень состоит из битов $(m_1,…,m_n)$, где 1 означает “за”.

Избиратель голосует и шифрует бюллетень:
$$(c_1,…,c_n), d = SE.Enc(pkey, (m_1,…,m_n), (min, max))$$

Результат $d$ позволяет без расшифрования проверить, что бюллетень заполнен корректно, а именно:

каждый $m_i$ – это 0 или 1
всего выбрано не менее $min$ и не более $max$ вариантов

Избиратель формирует транзакцию: $$tx = (c_1,…,c_n), d, pk_{izb}, \sigma_{blind}$$

Избиратель подписывает транзакцию:
$$\sigma = S.Sign(sk_{izb}, tx)$$

Избиратель отправляет транзакцию $tx$ и подпись $\sigma$ в Систему.

Система проверяет:

что Избиратель ещё не голосовал: уникальность $pk_{izb}$
слепую подпись ключа избирателя: $BS.Verify(pk, pk_{izb}, \sigma_{blind})$
подпись транзакции: $S.Verify(pk_{izb}, tx, \sigma)$
корректность транзакции $SE.VerifyEnc(pkey,(c_1,…,c_n), d, (min, max) )$

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

Подведение итогов голосования

Система складывает все зашифрованные бюллетени:
$$(c_1,…,c_n) = SE.Add((c_{1}^{1}, … c_{n}^{1}), (c_{1}^{2}, … c_{n}^{2}), …)$$

Система вычисляет первое частичное расшифрование и доказательство корректности: $$(k_1, p_{1}) = SE.DecPart(sk, pk, (c_1,…,c_n))$$

Члены комиссии восстанавливают разделённый ключ: $$sk_{div} = SS.Combine(s_1,…,s_m)$$

Система вычисляет второе частичное расшифрование и доказательство корректности: $$(k_2, p_{2}) = SE.DecPart(sk_{div}, pk_{div}, (c_1,…,c_n))$$

Система подсчитывает голоса за каждого кандидата:
$$result = (r_1,…,r_n) = SE.DecAgg(pk, pk_{div}, (c_1,…,c_n), k_1, k_2)$$

Наблюдение и аудит

Наблюдатель проверяет:

Списки бюллетеней
Уникальность каждой транзакции
Корректность слепой подписи Системы на ключах Избирателей с помощью $BS.Verify()$
Подпись Избирателя на бюллетене c помощью $S.Verify()$
Корректность бюллетеней с помощью $SE.VerifyEnc()$
Складывает бюллетени с помощью $SE.Add()$
Проверяет доказательство корректности частичных расшифрований с помощью $SE.VerifyDecPart()$
Вычисляет результаты голосования с помощью $SE.DecAgg()$ и сверяет его с опубликованным

Заключение

Система сделана очень интересно и применяет множество криптографических систем. Выполняются все свойства, предъявляемые к системам голосования и много сверх того. На мой взгляд, это самая развитая система электронного голосования на данный момент. Для примера, в Эстонии система голосования обеспечивает анонимность пользователя тем, что данные стирает независимое лицо, никакой технической защиты, аналогичной слепой подписи в ДЭГ, там просто нет.

В то же время для полноты картины отмечу некоторые недостатки системы ДЭГ:

Нет защиты от принуждения к голосованию. У избирателя могут взломать аккаунт и украсть телефон. Избиратель может голосовать под пристальным взглядом начальника. Избиратель может продать доступ к аккаунту и т. д. Во всех этих случаях его голос будет учтён наравне с остальными.

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

Код очень сложный и проверить его полностью очень сложно
Создаёт дополнительные риски безопасности, если уязвимость найдут злоумышленники

Моё мнение такое:

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

Для наблюдения нужно обладать специальными знаниями и готовиться заранее. Если в обычно голосовании наблюдать может любой и долгое обучение не требуется, то для наблюдения за электронным требуется квалификация. Хотя ЦИК и предоставляет программы для наблюдения, навыки написания простых скриптов и анализа данных необходимы для эффективного наблюдения.

Для участия в ДЭГ требуется регистрироваться заранее. Это даже не проблема, а скорее неудобство для избирателя. Но это сделано не просто так, а чтобы, в том числе, избиратель не мог проголосовать дважды: электронно и лично.

Материалы

Заседание экспертов по технологиям ДЭГ (19.07.2023):
https://vybory.gov.ru/#documents_and_articles

Материалы Экспертного совета по технологиям ДЭГ (19.07.2023):
https://www.youtube.com/watch?v=BsIXmhmrMPU

Требования к системам электронного голосования#

Часть 1: Простое описание ДЭГ#

Подтверждение избирательного права#

Тайна голосования#

Голосование#

Подведение итогов#

Наблюдение#

Часть 2: Описание протокола ДЭГ#

Первый вариант#

Целостность: шифрование и подпись бюллетеня#

Учёт бюллетеней: квитанция, блокчейн#

Анонимность: разделение получения бюллетеня и голосования#

Анонимность: слепая подпись#

Списки избирателей#

Зашифрованные бюллетени#

Невозможность подведения промежуточных итогов#

Наблюдение#

Часть 3: Описание криптографического протокола ДЭГ#

Используемые криптографические схемы#

Формирование списка избирателей#

Инициализация системы#

Получение бюллетеня#

Голосование#

Подведение итогов голосования#

Наблюдение и аудит#

Заключение#

Материалы#

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

Часть 1: Простое описание ДЭГ

Подтверждение избирательного права

Тайна голосования

Голосование

Подведение итогов

Наблюдение

Часть 2: Описание протокола ДЭГ

Первый вариант

Целостность: шифрование и подпись бюллетеня

Учёт бюллетеней: квитанция, блокчейн

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

Анонимность: слепая подпись

Списки избирателей

Зашифрованные бюллетени

Невозможность подведения промежуточных итогов

Наблюдение

Часть 3: Описание криптографического протокола ДЭГ

Используемые криптографические схемы

Формирование списка избирателей

Инициализация системы

Получение бюллетеня

Голосование

Подведение итогов голосования

Наблюдение и аудит

Заключение

Материалы