Протоколы тайного голосования

В связи с бурным развитием компьютерных сетей возникает естественное «оцифровывание» различных областей жизни, например, возникновение электронных валют. Аналогичным образом появилось цифровое голосование, основной инструмент электронной демократии. Долгое время механические средства служили в голосованиях заменой обыкновенным бюллетеням или отвечали только за автоматический подсчёт бумажных бюллетеней. Основную работу по проверке голосующих и учёту голосов проводили другие люди. При такой системе отсутствовала надобность в описанных ниже протоколах. Однако, в последние годы, благодаря развитию интернета, голосования становятся полностью автоматизированными. У удалённого голосования много плюсов. Предполагается, что они удобнее для конечных пользователей, ведь люди могут голосовать не выходя из дома, от этого повышается активность избирателей. Поддержание электронного голосования обходится дешевле: вместо постоянной печати бюллетеней достаточно однократно разработать систему[5][6]. Кроме того, из предположения, что никто не может вмешиваться в программу на устройстве для голосования, вытекает что электронное голосование менее подвержено коррупции, влиянию административного давления и человеческого фактора[5][7][8].

Однако, при этом возникает ряд специфических проблем, препятствующих честности выборов. Например, при электронных выборах в Нидерландах и во Франции возникли сомнения в истинности результатов, полученных с помощью машин[3]. Дистанционно намного сложнее авторизовать избирателя или удостовериться, что на ход голосования никто не повлиял. С другой стороны, интернет предоставляет больше возможностей для проверки рядовыми избирателями, правильно ли учтён голос. В настоящее время электронные голосования полностью легальны или частично применимы во многих странах мира[9]. Так как в них вовлекается всё больше людей, усиливается необходимость в более безопасных и эффективных методах их проведения, для чего и призваны специальные криптографические протоколы.

Ключевым элементом регламентации электронного голосования является закрепление его возможности в конституции государства. Такие статьи имеют конституции США, Швейцарии, Эстонии, Великобритании и некоторых других стран[10]. Есть группа стран, в которую входят, например, Финляндия, Германия и Россия[11], которые имеют опыт в проведении подобных выборов, но ещё не ввели их полную регламентацию в законодательство. Разумеется, это не единственное бюрократическое препятствие. Также требуются спецификации на технику, с помощью которой голосование проводится, способы проверки честности результатов, протоколы в случае срыва голосования, и создание самой технической базы. На основе этих параметров можно вычислить индекс готовности страны к введению цифрового голосования (и конкретного его протокола)[12].

Первой страной, которая реализовала легальные общенациональные выборы через интернет, стала Эстония[13], за ней последовали Нидерланды и Швейцария. В России протоколы тайного электронного голосования применялись пока что только на экспериментальном уровне (например, на форуме Селигер-2009), но в ЦИК была высказана инициатива о развитии электронного голосования, в частности, в интересах граждан РФ за рубежом[14].

Как бы то ни было, ни в одном законодательстве не закреплён сам протокол голосования. Так сделано по многим причинам, начиная от оставшегося недоверия к электронным методам голосования, заканчивая более лёгким переходом с текущего способа проведения на более эффективный. Прогресс техники позволил задуматься о голосовании через интернет только около 20 лет назад^{[прояснить]}, поэтому данный раздел криптографии всё ещё развивается. По нему нет общепризнанных книг, и ни один протокол ещё не получил подавляющую поддержку специалистов[5]. Проблема осложняется тем, что организации, обладающие опытом внедрения этих систем, предпочитают не публиковать подробные отчёты, описывающие систему, и проблемы, возникшие при её введении.

Сейчас для простых опросов или голосований внутри малых групп применяется тривиальный алгоритм. В случае, когда агент, подсчитывающий голоса, не имеет особой причины вести махинации, этот протокол является оптимальным вариантом. На выборах государственного уровня наиболее распространены модификации протокола Фудзиоки — Окамото — Оты[13][15]. Именно он показал наилучшие результаты на экспериментальных выборах и создал положительный международный прецедент надёжного проведения выборов через интернет. Для него и некоторых его модификаций существуют доступные для использования частными лицами программы и электронные средства голосования[16]. Кроме того многие научные статьи, описывающие новые протоколы тайного голосования, берут за основу именно его. Возможно, благодаря развитию техники и понижению цены на высокопроизводительные системы в ближайшем будущем появятся прецеденты использования протокола Хэ — Су[17]. Хотя он уже имеет свои модификации, на практике этот протокол был применён только в студенческих экспериментальных выборах[18]. То же самое можно сказать и про протокол ANDOS. Хотя авторы многих статей утверждают, что его можно эффективно реализовать, были только прецеденты его использования на местных выборах[19]. Остальные протоколы представлены как переходные от простых к сложным или возможные модификации для достижения дополнительных целей.

Шаг 1. А выкладывает списки возможных избирателей.

Шаг 2. Пользователи, в числе которых и E, сообщают о желании участвовать в голосовании.

Шаг 3. А выкладывает списки легитимных избирателей.

Шаги 1-3 обязательны. Основная цель — определение и объявление числа активных участников n. Хотя некоторые из них могут не участвовать, а некоторые - и вовсе не существовать («мёртвые души», злонамеренно внесённые A), возможность манипулирования голосованием у A заметно снижена. В дальнейшем эти шаги будут считаться за один шаг «утвердить списки».

Шаг 4. А создаёт открытый и закрытый ключ ${\displaystyle a_{\text{public}}}$ и ${\displaystyle a_{\text{private}}}$ и выкладывает в общий доступ ${\displaystyle a_{\text{public}}}$. Кто угодно может зашифровать сообщение при помощи ${\displaystyle a_{\text{public}}}$, но расшифровать его сможет только А.

Шаг 5. E

• создаёт собственные публичный и приватный ключи ЭЦП ${\displaystyle e_{\text{public}}}$ и ${\displaystyle e_{\text{private}}}$, затем публикует открытый ключ. Кто угодно может проверить документ E, но подписать его — только сам избиратель. Этот шаг пропускается, если A уже знает электронные подписи избирателей (например, они были сгенерированы при регистрации в системе).
• формирует сообщение B, где тем или иным способом выражает свою волю
• подписывает сообщение личным закрытым ключом ${\displaystyle e_{\text{private}}}$
• шифрует сообщение открытым ключом ${\displaystyle a_{\text{public}}}$
• отправляет шифрованное сообщение A

Шаг 6. A

• собирает сообщения
• расшифровывает их при помощи лежащего в открытом доступе ${\displaystyle e_{\text{public}}}$
• подсчитывает их и публикует результаты

Этот протокол чрезвычайно прост, тем не менее, его достаточно, чтобы защититься от внешнего вмешательства, подделки голосов и дискредитации легитимных избирателей. Однако голосующим приходится абсолютно доверять A, ведь его работа никем не контролируется. С одной стороны, E может предоставить злоумышленнику-покупателю голосов доказательство, как он проголосовал, а с другой — не может проверить, что A правильно учёл или даже получил его бюллетень. Поэтому тривиальный метод применим только в сообществах, где все доверяют друг другу и агентству, отвечающему за подсчёт голосов[20].

Шаг 1. V

• создаёт набор опознавательных меток ${\displaystyle t_{i}}$ и утверждает список возможных избирателей
• отправляет по защищённому каналу по одной метке каждому голосующему
• отправляет A весь набор меток без информации о том, какая метка кому принадлежит

Шаг 2. E

• генерирует ${\displaystyle e_{\text{public}}}$, ${\displaystyle e_{\text{private}}}$ (для цифровой подписи) и ${\displaystyle e_{\text{secret}}}$ (для того, чтобы ни A, ни посторонний злоумышленник не мог до нужного времени узнать содержимое бюллетеня)
• ${\displaystyle e_{\text{public}}}$ публикуется
• формирует сообщение B с выбранным решением
• подписывает его ${\displaystyle e_{\text{private}}}$
• прикладывает к нему полученный ${\displaystyle t_{i}}$
• шифрует при помощи ${\displaystyle e_{\text{secret}}}$
• снова прикладывает к шифротексту ${\displaystyle t_{i}}$
• отправляет шифротекст ${\displaystyle {\big \{}t_{i},\operatorname {encrypt} {\big (}e_{\text{secret}},\{t_{i},\operatorname {sign} (e_{\text{private}},B)\}{\big )}{\big \}}}$ на рассмотрение в A

Шаг 3. A

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

Шаг 4. Опубликованный файл служит сигналом E отправить секретный ключ ${\displaystyle e_{\text{secret}}}$

Шаг 5. A

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

Благодаря выкладыванию в общий доступ полученного файла на шаге 3, A не может впоследствии отрицать получение сообщения от E. При помощи пары шифр — бюллетень каждый избиратель может проверить, правильно ли был учтён его голос, что устраняет проблему с недостатком контроля над A. Однако такой подход лишь частично решает проблему необходимости абсолютного доверия к агентству. В случае, если A и V удаётся сговориться, A может манипулировать голосованием. Если агентству известно, кто скрывается под каким опознавательным тегом, оно может специально не принимать сообщения от некоторых избирателей. Кроме того, присутствует проблема «мёртвых душ». Если V внесёт в список заведомо несуществующих избирателей, то A сможет фальсифицировать бюллетени от них[26].

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

Шаг 1. V утверждает списки легитимных избирателей

Шаг 2. E

• создаёт ${\displaystyle e_{\text{public}}}$, ${\displaystyle e_{\text{private}}}$ (для цифровой подписи) и ${\displaystyle e_{\text{secret}}}$ (для того, чтобы ни A, ни посторонний злоумышленник не мог до нужного времени узнать содержимое бюллетеня)
• подготавливает сообщение B с выбранным решением
• шифрует его ${\displaystyle e_{\text{secret}}}$
• накладывает слой ослепляющего шифрования
• подписывает его ${\displaystyle e_{\text{private}}}$
• отправляет V ${\displaystyle \operatorname {blind} {\Big (}\operatorname {sign} (e_{\text{private}},\operatorname {encrypt} (e_{\text{secret}},B){\big )}{\Big )}}$

Шаг 3. V

• создаёт ${\displaystyle v_{\text{public}}}$ и ${\displaystyle v_{\text{private}}}$, публичный ключ выкладывается в общий доступ
• удостоверяется, что бюллетень действительный и принадлежит легитимному и не голосовавшему избирателю
• подписывает его ${\displaystyle v_{\text{private}}}$
• возвращает его E

Шаг 4. E снимает с бюллетени слой маскирующего шифрования (в силу коммутативности остаётся ${\displaystyle \operatorname {sign} {\Big (}v_{\text{private}},\operatorname {sign} {\big (}e_{\text{private}},\operatorname {encrypt} (e_{\text{secret}},B){\big )}{\Big )}}$) и отправляет её A

Шаг 5. A

• проверяет подписи E и V
• помещает всё ещё зашифрованную ${\displaystyle e_{\text{secret}}}$ бюллетень в специальный список, который будет опубликован после того как все избиратели проголосуют или по истечении заранее оговорённого срока

Шаг 6. После того как список появляется в открытом доступе, E высылает A ${\displaystyle e_{\text{secret}}}$

Шаг 7. A

• расшифровывает сообщение
• подсчитывает результаты

Лорри Кранор и Рон Ситрон (англ. Lorrie Faith Cranor, Ron K. Cytron) в 1996 предложили модификацию протокола Фудзиоки — Окамото — Оты под названием Sensus[28]. Отличие заключается в шагах 5—6. После того, как A получило зашифрованное сообщение от E, оно не только добавляет его в публикуемый список, а вдобавок отправляет подписанный бюллетень обратно избирателю в качестве квитанции. Таким образом E не нужно ждать, пока проголосуют все остальные, и он может закончить голосование за один сеанс. Это не только удобно для конечного пользователя, но ещё и предоставляет дополнительного доказательство, что E участвовал в выборах. Кроме того, в Sensus регламентированы дополнительные вспомогательные модули, упрощающие и автоматизирующие ход голосования.

Теперь даже если агентствам удастся сговориться, A не сможет опознать избирателей до того, как получит ключ. Хотя оно всё ещё имеет возможность не принимать сообщения, отпадает возможность игнорировать сообщения конкретно от «неугодных» избирателей. Остаётся лишь проблема подачи голосов за избирателей, не пришедших на выборы. Кроме того, чтобы позволить избирателю переголосовать, в том числе и из-за технической ошибки, необходим дополнительный модуль.

На данный момент протокол Фудзиоки — Окамото — Оты (а также его модификации, включая и Sensus) является одним из самых проверенных протоколов дистанционного электронного голосования. Именно его вариация была применена на электронных выборах в Эстонии[13][15]. Другая модификация протокола Фудзиоки — Окамото — Оты была использована для проведения выборов в органы самоуправления среди студентов Принстонского университета[29]. Модули Sensus были написаны под системой UNIX с использованием криптографической библиотеки RSAREF[30], так что любой может ими воспользоваться.

Шаг 1. V

• утверждает списки легитимных избирателей
• создаёт ${\displaystyle v_{\text{public}}}$ и ${\displaystyle v_{\text{private}}}$ (используются для асимметричного шифрования)
• ${\displaystyle v_{\text{public}}}$ выкладывается в свободный доступ

Шаг 2. E

• создаёт ${\displaystyle e_{\text{public}}}$ и ${\displaystyle e_{\text{private}}}$ (используются для подписей)
• вычисляет хеш-функцию от публичного ключа: ${\displaystyle \operatorname {h} (e_{\text{public}})}$
• накладывает слой маскирующего шифрования на ${\displaystyle \operatorname {h} (e_{\text{public}})}$. Так как шифруется только хеш от ключа, а не длинное сообщение, можно выбрать какой-нибудь простой способ. Например, E может сгенерировать случайное число ${\displaystyle x}$ и вычислить ${\displaystyle f=\operatorname {encrypt} (v_{\text{public}},x)\operatorname {h} (e_{\text{public}})}$
• отправляет ${\displaystyle f}$ V

Шаг 3. V

• проверяет легитимность избирателя
• дешифрует ${\displaystyle f}$: ${\displaystyle g=\operatorname {decrypt} {\big (}v_{\text{private}},\operatorname {encrypt} (v_{\text{public}},x)\operatorname {h} (e_{\text{public}}){\big )}=x\operatorname {decrypt} {\big (}v_{\text{private}},\operatorname {h} (e_{\text{public}}){\big )}}$. Часть ${\displaystyle e_{\text{public}}^{\text{signed}}=\operatorname {decrypt} {\big (}v_{\text{private}},\operatorname {h} (e_{\text{public}}){\big )}}$ считается подписанным ключом
• отправляет ${\displaystyle g}$ E

Шаг 4. E

• снимает слой ослепляющего шифрования (умножает на обратный элемент ${\displaystyle x}$) и получает подписанный ключ ${\displaystyle e_{\text{public}}^{\text{signed}}}$
• проверяет подлинность подписи регистратора: выполняется ли ${\displaystyle \operatorname {encrypt} {\Big (}v_{\text{public}},\operatorname {decrypt} {\big (}v_{\text{private}},\operatorname {h} (e_{\text{public}}){\big )}{\Big )}=\operatorname {h} (e_{\text{public}})}$
• отправляет A пару ${\displaystyle {\big \{}e_{\text{public}},e_{\text{public}}^{\text{signed}}{\big \}}}$

Шаг 5. A

• как и E проверяет подлинность подписи регистратора
• проверяет, совпадает ли хеш-функция от ${\displaystyle e_{\text{public}}}$ в паре с той, что хранится в ${\displaystyle e_{\text{public}}^{\text{signed}}}$
• добавляет ${\displaystyle e_{\text{public}}}$ в список авторизированных ключей и сообщает об этом E

Шаг 6. E

• создаёт ${\displaystyle e_{\text{secret}}}$ (используется для шифровки бюллетеней, чтобы ни A ни внешний злоумышленник до нужного времени не мог узнать содержимое бюллетеня)
• подготавливает сообщение B с выбранным решением
• отправляет A набор ${\displaystyle {\Big \{}e_{\text{public}},\operatorname {encrypt} {\Big (}e_{\text{secret}},B),\operatorname {sign} {\big (}e_{\text{private}},\operatorname {h} (\operatorname {encrypt} (e_{\text{secret}},B){\big )}{\Big )}{\Big \}}}$

Шаг 7. A

• проверяет авторизованность ключа
• проверяет подлинность сообщения сравнивая хеш зашифрованного сообщения и хеш, полученный при помощи ${\displaystyle e_{private}}$
• публикует тройку в открытом списке

Шаг 8. Появление тройки в открытом списке сигнализирует E отправить A новый набор: ${\displaystyle {\big \{}e_{\text{public}},e_{\text{secret}},\operatorname {sign} {\big (}e_{\text{private}},\operatorname {h} (e_{\text{secret}}){\big )}{\big \}}}$

Шаг 9. A

• проверяет подлинность сообщения, сравнивая хеши
• расшифровывает ранее полученную бюллетень
• публикует все данные
• подсчитывает результат

Шаг 10. После голосования V публикует список всех зарегистрировавшихся избирателей, а A — список всех авторизованных ключей.

Схема Хэ — Су удовлетворяет почти всем требованиям к протоколу тайного голосования. Остаётся только повышенный стимул купли/продажи голосов[17]. у A и V теперь нет возможности сжульничать, так как теперь публикуются все списки: возможных избирателей, зарегистрировавшихся и авторизированных ключей. Соответственно, нельзя ни внести несуществующих избирателей, ни голосовать за существующих, но не пришедших. При этом во время составления этих списков ни избирательное агентство, ни регистратор дополнительной информации не получают[31]. У избирателей есть возможность изменить голос. Основной недостаток протокола Хэ — Су — его сравнительная сложность. Так как для поддержания протокола необходимо большое количество ресурсов, он уязвим перед DoS-атаками.

Шаг 1. A

• утверждает список участников голосования;
• пусть набралось n легитимных избирателей. Тогда A выбирает не менее чем n идентификаторов и применяет ANDOS протокол к голосующим. Идентификаторы — большие простые числа, они пронумерованы как ${\displaystyle 1,...,n}$.

Шаг 2. E

• выбирает номер i и получает i-е простое число ${\displaystyle p_{i}}$ из списка (A ничего не знает о взаимосвязи между i и E)
• выбирает криптографическую хеш-функцию ${\displaystyle h_{E}(x,y)}$ двух переменных
• пересылает A пару ${\displaystyle {\big (}p_{i},h_{E}(p_{i},v_{E}){\big )}}$, где ${\displaystyle v_{E}}$ — выбор (имя кандидата, или в более общем виде, выборочная стратегия) выраженный численно

Шаг 3. A публикует ${\displaystyle h_{E}(p_{i},v_{E})}$.

Шаг 4. После появления ${\displaystyle h_{E}(p_{i},v_{E})}$ в открытом списке E отправляет A пару ${\displaystyle (p_{i},h_{E}^{-1})}$. Считая, что y всегда может быть получен по заданным ${\displaystyle h_{E}(x,y)}$, ${\displaystyle x}$ и ${\displaystyle h_{E}^{-1}}$, A теперь знает связь между ${\displaystyle p_{i}}$ и ${\displaystyle v_{E}}$ (но не между E и его выбором ${\displaystyle v_{E}}$).

Упрощённая версия шагов 2—4 может состоять в том, что E посылает A напрямую пару ${\displaystyle p_{i},v_{E}}$. Однако, в этом случае будет невозможно для E как проверить засчитан ли голос правильно, так и переголосовать на более поздней стадии. Так может выйти, так как если A публикует идентификатор ${\displaystyle p_{i}}$ в списке тех, кто придерживался стратегии ${\displaystyle v_{E}}$, то E будет точно знать, что его голос зачтён правильно, однако впоследствии кто-нибудь сможет замаскироваться под обладающего идентификатором ${\displaystyle p_{i}}$ и изменить голос на угодный ему. С другой стороны, если A публикует только количество участников, придерживающихся определённой стратегии ${\displaystyle v_{E}}$, то участники не могут ничего проверить и A может публиковать любые результаты выборов. Хеш-функции используются для того, чтобы злоумышленники не могли определить количество голосов с определённой стратегией ${\displaystyle v_{E}}$ (эта информация оказывается полезной), так как задача нахождения исходных значений вычислительно тяжёлая с учётом характерного времени проведения голосования.

Шаг 5. Когда голосование подходит к концу, A объявляет промежуточные результаты, публикуя списки стратегий (кандидатов) с числами ${\displaystyle h_{E}(p_{i},v_{E})}$, соответствующими участникам, голосовавшим за ${\displaystyle v=v_{E}}$.

Шаг 6. Если участник E замечает, что его голос размещён в неверном списке, то он посылает A жалобу в виде тройки ${\displaystyle {\big (}p_{i},h_{E}(p_{i},v_{E}),h_{E}^{-1}{\big )}}$, которая явным образом показывает верность либо ошибочность результата.

Спустя некоторое время можно начать процедуру изменения голосов (см. финальный шаг). Более простой вариант (Шаг 7) может быть использован для проведения единственного круга повторного голосования.

Шаг 7. Участник E, который хочет изменить свой выбор, отправляет A тройку ${\displaystyle {\big (}p_{i},h_{E}(p_{i},v_{E}),v'_{E}{\big )}}$, где ${\displaystyle v'_{E}}$ — новая стратегия. Когда подходит конец тура изменения голосов, A публикует изменённые результаты. Затем повторяется проверка правильности.

Шаг 7'. Всё как и в шаге 7, но теперь участник E отправляет пару ${\displaystyle {\big (}p_{i},h'_{E}(p_{i},v'_{E}){\big )}}$, где ${\displaystyle h'_{E}}$ — новая хеш-функция, выбранная E. A удостоверяет получение сообщения, публикуя ${\displaystyle h'_{E}(p_{i},v'_{E})}$, после чего E отправляет A пару ${\displaystyle {\big (}p_{i},(h'_{E})^{-1}{\big )}}$. Теперь A знает взаимосвязь между ${\displaystyle p_{i}}$ и ${\displaystyle v'_{E}}$. При повторном подведении результатов ${\displaystyle h_{E}(p_{i},v_{E})}$ удаляется из соответствующего списка, а ${\displaystyle h'_{E}(p_{i},v'_{E})}$ добавляется в список с ${\displaystyle v'=v'_{E}}$. Участник E может оспорить результат как и прежде.

По сравнению с шагом 7, шаг 7' имеет преимущество в том, что участники, отличные от E, могут лишь наблюдать, что что-либо исчезло из списка ${\displaystyle v}$, но не будут знать, что оно переместилось в список ${\displaystyle v'}$.

В протоколе ANDOS возможна ситуация, когда два голосующих выберут одно и то же i, таким образом получив одинаковый идентификатор ${\displaystyle p_{i}}$. Возможные решения этой проблемы[32]:

• A удостоверяется, что число идентификационных номеров настолько больше числа голосующих, что вероятность коллизии пренебрежимо мала.
• При повторном получении идентификатора ${\displaystyle p_{i}}$ A публикует пару ${\displaystyle {\big (}p'_{i},h_{E}(p_{i},v_{E}){\big )}}$, где ${\displaystyle p'_{i}}$ — идентификатор, который был не «на продажу» в протоколе ANDOS. По второй компоненте участник E видит, что он под вопросом и отправляет A пару ${\displaystyle {\big (}p'_{i},h_{E}(p'_{i},v_{E}){\big )}}$. Другие участники не могут этого сделать, так как они не знают хеш-функции ${\displaystyle h_{E}}$. Далее процесс идёт по той же схеме: A публикует ${\displaystyle h_{E}(p'_{i},v_{E})}$ и т. д. После получения ${\displaystyle h_{E}^{-1}}$ A удостоверяется, что откликнулся нужный участник.

Протокол ANDOS довольно затратен, зато для него не нужен независимый регистратор V. Избирателям необходимо выбирать и пересылать не только идентификаторы, но и хеширующие функции, что может быть сложно или долго[32]. А всё ещё может жульничать, распределяя по своему выбору голоса тех, кто заявил о своём намерении принять участие в голосовании, но так и не совершил свой выбор, а E имеют повышенный стимул купли/продажи голосов, так как можно убедиться в результате сделки.