Главная » Хабрахабр » [Перевод] Криптографические протоколы для электронного голосования

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

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

Исследование электронного голосования занимается созданием протоколов, ключевых математических компонентов, защищённых и проверяемых систем голосования, или таких систем, в которых независимые аудиторы и избиратели могут безопасно проверить правильность подсчёта голосов. Для исследователей криптографии электронное голосование в первую очередь связано не с машиной для голосования и не с онлайн-голосованием – это просто поле для математических исследований. Я не буду давать вам полное описание всего протокола электронного голосования со всеми его нюансами, но желающие могут самостоятельно поискать работы на эту тему, коих достаточно много. Эти системы представляют собой не простые теоретические работы, но уже реальные технологии, использовавшиеся для реальных выборов: в городе Такома-Парк штата Мэриленд избиратели доверились системе 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), используя в качестве ключа публичный ключ, выданный организаторами.

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

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

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

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

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

Enc(v1) = g v1 r1 n mod n2

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

Enc(v1) × Enc(v2) = (g v1 r1 n) × (g v2 r2 n) mod n2 = g v1+v2 (r1r2) n mod n2 = Enc(v1 + v2)

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

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

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

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

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

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

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

Заключение

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

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

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

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


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

[Перевод] Python Testing с pytest. Начало работы с pytest, Глава 1

Вернуться Дальше Это уже приносит мне дивиденды в моей компании.Chris ShaverVP of Product, Uprising Technology Я обнаружил, что Python Testing с pytest является чрезвычайно полезным вводным руководством к среде тестирования pytest. 6 и pytest 3. Примеры в этой книге написаны ...

[Перевод] Python Testing с pytest. ГЛАВА 3 pytest Fixtures

Вернуться Дальше Эта книга — недостающая глава, отсутствующая в каждой всеобъемлющей книге Python. Frank RuizPrincipal Site Reliability Engineer, Box, Inc. 6 и pytest 3. Примеры в этой книге написаны с использованием Python 3. pytest 3. 2. 6, 2. 2 поддерживает ...