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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

К примеру, если сильно упростить, избиратели США производят следующие действия 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 в аддитивно гомоморфные, но вместо этого я покажу менее известную схему, которая сразу же аддитивно гомоморфна: криптосистема Пэйе ^[11], шифрующая сообщение 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)

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

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

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

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

Возможно, простейшая система с нулевым разглашением, это схема Шнорра ^[14]: допустим, вы знаете решение задачи дискретного логарифма (сложная задача, стоящая за DSA ^[15] и шифрованием на эллиптических кривых), и хотите доказать, что знаете её решение, не разглашая само решение. То есть, вам известен такой х, что 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 ^[16]
• Report The Future of Voting sponsored by the US Vote Foundation ^[17]
• Ben Adida’s GoogleTech talk ^[18]
• How human and operational factors can compromise e-voting schemes ^[19]
• Lecture notes on zero-knowledge proofs ^[20]

Автор: SLY_G

Источник ^[21]