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

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

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

Обзор

Предпосылки создания

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

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

Опыты регламентации и реализации

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

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

Текущее состояние дел

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

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

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

Обязательные:

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

Желательные:

• каждый легитимный участник может проверить, правильно ли зачтён его голос;
• каждый легитимный участник может передумать и изменить свой выбор в течение определённого периода времени;
• система должна быть защищена от продажи голосов избирателями;
• в случае, если голос зачтён неправильно, каждый легитимный участник может сообщить об этом системе, не раскрывая своей анонимности;
• невозможно отследить, откуда дистанционно проголосовал избиратель;
• аутентификация оператора;
• можно узнать, кто принимал участие в голосовании, а кто — нет;
• поддержание системы не должно требовать много ресурсов;
• система должна быть отказоустойчива в случае технических неисправностей (потеря электропитания), непреднамеренных (потеря избирателем ключа) и злоумышленных (намеренная выдача себя за другого избирателя, DoS/DDoS) атак.

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

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

Простой протокол тайного цифрового голосования

Простой алгоритм электронного голосования по сути представляет собой переписку с электронными подписями между избирательным комитетом и множеством избирателей. Пусть здесь и далее: А — агентство, проводящее электронное голосование (англ. agency), E — избиратель, легитимный участник голосования (англ. elector), B — цифровой бюллетень. B может содержать число, имя кандидата, развёрнутый текст или какие-либо другие данные, сообщающие о выборе E, верифицирующие его или необходимые для усиления безопасности протокола. Ход голосования выглядит так:

Алгоритм

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

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

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

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

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

Шаг 5. E

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

Шаг 6. A

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

Особенности, преимущества и недостатки

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

Протокол двух агентств

Он же протокол Нурми — Саломаа — Сантина. Основная идея состоит в том, чтобы заменить одно избирательное агентство двумя, чтобы они контролировали друг друга. Пусть здесь и далее V — регистратор (англ. validator), в обязанности которого входит подготовка списков, а также допуск или недопуск участника до голосования. Последовательность действий выглядит так:

Алгоритм

Шаг 1. V

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

Шаг 2. E

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

Шаг 3. A

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

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

Шаг 5. A

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

Особенности, преимущества и недостатки

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

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

Протокол Фудзиоки — Окамото — Оты

Схема Фудзиоки — Окамото — Оты, разработанная в 1992 году, основывается на протоколе двух агентств и криптографической подписи вслепую. Несильно усложняя протокол, эта схема частично решает проблему сговора двух агентств. Для работы протокола необходим заранее выбранный способ маскирующего шифрования, под которым избиратель присылает регистратору бюллетень. Ослепляющее (маскирующее) шифрование — особый вид шифрования, позволяющее удостовериться в том, что документ подлинный и подписан авторизованным пользователем, но не даёт узнать содержащиеся в нём данные. Маскирующее шифрование должно быть коммутативным с электронной подписью, то есть $\operatorname {sign} {\big (}\operatorname {blind} (B){\big )}=\operatorname {blind} {\big (}\operatorname {sign} (B){\big )}$.

Алгоритм

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

Шаг 2. E

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

Шаг 3. V

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

Шаг 4. E снимает с бюллетени слой маскирующего шифрования (в силу коммутативности остаётся $\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
• помещает всё ещё зашифрованную $e_{\text{secret}}$ бюллетень в специальный список, который будет опубликован после того как все избиратели проголосуют или по истечении заранее оговорённого срока

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

Шаг 7. A

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

Протокол Sensus

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

Особенности, преимущества и недостатки

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

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

Протокол Хэ — Су

В 1998 году Ци Хэ и Чжунминь Су (Qi He, Zhongmin Su) представили ещё более продвинутый по сравнению с Sensus протокол голосования. Этот алгоритм удовлетворяет большей части требований к безопасному протоколу цифрового голосования. Как и Sensus, протокол Хэ — Су использует идею слепой подписи, но подписывается не бюллетень избирателя, а его ключ. Это позволяет голосующим изменять своё решение до конца голосования и ещё больше сужает возможности регистратора и избирательного агентства в случае сговора. Для этого протокола требуется заранее оговорённый способ ослепляющего шифрования и хеш-функция $\operatorname {h} ()$. Как и в протоколе Фудзиоки — Окамото — Оты маскирующее шифрование должно быть коммутативным с электронной подписью V: $\operatorname {sign} {\big (}\operatorname {blind} (B){\big )}=\operatorname {blind} {\big (}\operatorname {sign} (B){\big )}$, а также $\operatorname {sign} (A\,B)=\operatorname {sign} (A)\,\operatorname {sign} (B)$.

Алгоритм

Шаг 1. V

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

Шаг 2. E

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

Шаг 3. V

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

Шаг 4. E

• снимает слой ослепляющего шифрования (умножает на обратный элемент $x$) и получает подписанный ключ $e_{\text{public}}^{\text{signed}}$
• проверяет подлинность подписи регистратора: выполняется ли $\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 пару ${\big \{}e_{\text{public}},e_{\text{public}}^{\text{signed}}{\big \}}$

Шаг 5. A

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

Шаг 6. E

• создаёт $e_{\text{secret}}$ (используется для шифровки бюллетеней, чтобы ни A ни внешний злоумышленник до нужного времени не мог узнать содержимое бюллетеня)
• подготавливает сообщение B с выбранным решением
• отправляет A набор ${\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

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

Шаг 8. Появление тройки в открытом списке сигнализирует E отправить A новый набор: ${\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 — список всех авторизованных ключей.

Особенности, преимущества и недостатки

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

Протокол на основе ANDOS

За основу взят протокол ANDOS (англ. All or Nothing Disclosure Of Secrets). Идея состоит в том, чтобы усилить стойкость протокола за счёт замены заранее выбранного шифрования секретным ключом на хеширование пользовательской функцией. Далее описано ядро алгоритма. В описании для краткости опущены меры предосторожности и безопасности. В случае необходимости можно применить методы криптографии на открытых ключах и электронной подписи. Предполагается, что для защиты от вмешательства кого-либо извне избиратели могут ещё и мешать информацию между собой, но тогда злонамеренный избиратель может вносить помехи в голосование, поэтому этот шаг тоже пропущен.

Алгоритм

Шаг 1. A

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

Шаг 2. E

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

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

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

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

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

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

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

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

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

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

Особенности, преимущества и недостатки

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

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

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

Прочие протоколы

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

Например, протокол двух агентств можно распространить на $n$ избирательных центров, представляющие различные противоборствующие, но заинтересованные в честных выборах фракции. В этом случае распределение голосов может быть подделано только если все центры окажутся в сговоре, что не имеет смысла по условию. Такой алгоритм использует какую-либо схему неинтерактивного публично проверяемого разделения секрета (англ. NIVSS — Non-Interactive Verifiable Secret Sharing). В зависимости от выбранного способа разделения секрета (кто за кого проголосовал) протокол может иметь разную стойкость к разным атакам и разную скорость обработки данных. Хороший результат показывает, например, использование проблемы дискретного логарифмирования для обеспечения сокрытия данных.

Главным недостатком системы является то, что хотя сфальсифицировать результаты могут только все избирательные центры вместе, сорвать ход выборов может любой из них в одиночку. Решением дилеммы является ещё одна модификация алгоритма, когда распределение голосов могут восстановить $k<n$ центров. Но тогда и подделать результаты смогут $k$ сговорившихся центров, а сорвать выборы — $n-k$. Схема может быть улучшена, чтобы допускать несколько вариантов ответа в бюллетени, а также поэтапное или параллельное голосования. Дополнительный плюс: при такой системе избиратель не может доказать, за кого именно он проголосовал, что делает чрезвычайно трудной покупку/продажу голосов.

Для работы данного протокола необходим примитив «доска бюллетеней» — область данных, которую могут читать все целиком, а писать — каждый только в свою часть. По сути это — общая область памяти с доступом по сети и некоторыми криптографическими ограничениями. Если в выборах участвует $n$ центров голосований $A_{1},\dots ,A_{n}$ и $m$ избирателей $E_{1},\dots ,E_{m}$, то количество битов, необходимое для доски бюллетеней — $O(nmk)$, где $k$ — некоторая переменная криптостойкости, пропорциональная количеству битов ключа.

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