Криптографические протоколы для электронного голосования

Демократия – это не голосование, это подсчёт голосов.
Том Стоппард

Для исследователей криптографии электронное голосование в первую очередь связано не с машиной для голосования и не с онлайн-голосованием – это просто поле для математических исследований. Исследование электронного голосования занимается созданием протоколов, ключевых математических компонентов, защищённых и проверяемых систем голосования, или таких систем, в которых независимые аудиторы и избиратели могут безопасно проверить правильность подсчёта голосов. Эти системы представляют собой не простые теоретические работы, но уже реальные технологии, использовавшиеся для реальных выборов: в городе Такома-Парк штата Мэриленд избиратели доверились системе Scantegrity II, основанной на бумажных бюллетенях с невидимыми чернилами, а сами криптографы использовали системы для онлайн-голосования Helios для избрания руководства.

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

Безопасное подтверждение

Чего следует ожидать от системы безопасного голосования?

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

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

Наконец, система голосования должна быть защищённой против подлогов: избиратель не должен иметь возможности голосовать более одного раза, и не должно быть возможности изменять или копировать бюллетень. Кроме того, иметь возможность голосовать должны только зарегистрированные избиратели.

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

Основные принципы

Большинство классических протоколов электронного голосования работают следующим образом:

1. Избиратель получает токен в виде бюллетеня, который изменяет соответственно своему выбору. Разные избиратели получают разные бюллетени.
2. Избиратель шифрует бюллетень (используя особый тип шифрования, позволяющий работать магии электронного голосования, и отправляет его так, чтобы организаторы голосования получили зашифрованный бюллетень.
3. Организаторы публикуют зашифрованные бюллетени на доске объявлений, «публичном широковещательном канале с памятью», на жаргоне криптографов – говоря проще, на чём-то вроде Pastebin.
4. Организаторы комбинируют зашифрованные бюллетени для подсчёта зашированного итога. Затем они расшифровывают его (но не сами бюллетени!) и публикуют результаты.
5. Получив результат и зашифрованные голоса, любой может проверить его корректность.

Безопасный подсчёт: гомоморфное шифрование

На 4-м шаге организаторы комбинируют криптограммы для создания новой криптограммы, шифрующей сумму отдельных голосов. Для этого схемы электронного голосования используют схему шифрования Enc(), в которой можно подсчитать Enc(v1 + v2), имея на руках только Enc(v1) и Enc(v2), и не зная ключа шифрования. Такие схемы шифрования называются гомоморфными.

К примеру, если сильно упростить, избиратели США производят следующие действия 8 ноября:

1. Получают от организаторов бюллетень «Клинтон» и бюллетень «Трамп» (для простоты рассмотрим всего двух кандидатов).
2. Пишут на одном бюллетене Enc(1), а на другом – Enc(0), используя в качестве ключа публичный ключ, выданный организаторами.

Зашифрованные бюллетени затем публикуются на доске объявлений вместе с ID избирателя. Все знаю, кто проголосовал, но невозможно понять, за кого именно, поскольку каждые Enc(0) и Enc(1) уникальны, а мы используем сильное и рандомизированное шифрование. Если бы шифрование было детерминистское, избирателя можно было бы заставить раскрыть его голос, вычислив Enc(0) заново и сравнив его со значением на доске.

Наконец, организаторы комбинируют все бюллетени за «Клинтон» и получают результат Enc(количество голосов за Клинтон), а потом то же делают с бюллетенями за «Трампа» и получают Enc(количество голосов за Трампа). Затем они берут ключ расшифровки и расшифровывают два этих значения, объявляя победителя.

А как найти гомоморфную схему шифрования? Довольно легко – такие схемы, как RSA и ElGamal, гомоморфны в своих базовых вариантах, поскольку удовлетворяют уравнению

Enc(v1) × Enc(v2) = Enc(v1 × v2)

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

Enc(v1) = g ^v1 r1 ⁿ mod n²

Где n = pq и g – фиксированы, а r1 – случайное целое число из ]1; n² [. Следовательно, мы имеем:

Enc(v1) × Enc(v2) = (g ^v1 r1 ⁿ) × (g ^v2 r2 ⁿ) mod n² = g ^v1+v2 (r1r2) ⁿ mod n² = Enc(v1 + v2)

То есть, схему Пэйе можно использовать для подсчёта зашифрованных голосов.

Предотвращаем мошенничество: доказательство с нулевым разглашением

Чтобы сжульничать, избиратель может захотеть написать в бюллетене Enc(10000) вместо Enc(1), чтобы добавить кандидату голосов. В случае недобрых намерений можно написать Enc(очень_большое_число), чтобы это привело к переполнению целого и к отказу всей системы. Как же гарантировать допустимость голоса (0 или 1) без дешифровки?

Решением будет не интерактивное нулевое разглашение (НИНР) [non-interactive zero-knowledge, NIZK]. Доказательство НИНР – весьма сложный и чрезвычайно мощный криптографический объект: в нашем случае он позволит избирателю доказать, что их криптограмма содержит 0 или 1, но при этом не показывая само зашифрованное сообщение. В общем случае НИНР-доказательства позволяют доказывающему убедить проверяющего в истинности утверждения, отправляя ему только набор данных без каких-то других видов взаимодействия.

Возможно, простейшая система с нулевым разглашением, это схема Шнорра: допустим, вы знаете решение задачи дискретного логарифма (сложная задача, стоящая за DSA и шифрованием на эллиптических кривых), и хотите доказать, что знаете её решение, не разглашая само решение. То есть, вам известен такой х, что g^x = y mod p, а проверяющий знает только g, y и p. Чтобы убедить проверяющего, вы играете в следующую игру:

1. Выбираете случайное число r и отправляете проверяющему значение g^r (обязательство).
2. Получаете от проверяющего случайное число с (вызов).
3. Отправляете проверяющему s = r + cx.
4. Проверяющий вычисляет g^s = g^{r + cx} и проверяет, что оно равно g^r × y^c = g^r × (g^x) ^c.

В этом интерактивном протоколе доказывающий не раскрывает значения х, поскольку отправляет только случайные числа. Однако лишь доказывающий, который знает х, сможет отправить s, проходящее последнюю проверку.

Для превращения такого интерактивного протокола в неинтерактивный (такой, который можно отправить одним набором данных), строятся НИНР-доказательства. Мы самостоятельно играем в эту игру и симулируем проверяющего так, чтобы реальный проверяющий убедился в том, что мы не можем придумать НИНР-доказательство, не зная доказанного утверждения.

Заключение

Ключевые идеи, рассмотренные в статье:

• Основная проблема безопасной системы электронного голосования – публичная проверяемость. Это достигается публикацией зашифрованных бюллетеней на публично доступном форуме. Организаторы голосования также должны описать механизм, проводящий само подтверждение.
• Правильность голосования подтверждается путём проведения авторизации каждого избирателя с уникальным ID и давая избирателям доступ, который позволяет им проверить, что их бюллетень 1) засчитан и 2) не изменён.
• Избирателей нельзя наказать за голоса за «неправильных» кандидатов благодаря сопротивлению принуждению, которое, в частности, достигается за счёт непредсказуемого и вероятностного шифрования.
• Приватность бюллетеней гарантируется тем, что зашифрованные голоса не расшифровываются, а расшифровывается только итог, созданный при помощи гомоморфного шифрования.
• Жульничество не проходит, если мы заставляем избирателей публиковать криптографическое доказательство допустимости их бюллетеня при помощи НИНР.

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

Чтобы больше узнать про криптографию, связанную с темой электронного голосования, можете изучить эти, качественные материалы:

• David Chaum’s 2004 article in IEEE S&P
• Report The Future of Voting sponsored by the US Vote Foundation
• Ben Adida’s GoogleTech talk
• How human and operational factors can compromise e-voting schemes
• Lecture notes on zero-knowledge proofs