- PVSM.RU - https://www.pvsm.ru -

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

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

Демократия – это не голосование, это подсчёт голосов.
Том Стоппард [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 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)

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

Автор: SLY_G

Источник [21]


Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/kriptografiya/305759

Ссылки в тексте:

[1] Том Стоппард: https://ru.wikipedia.org/wiki/%D0%A1%D1%82%D0%BE%D0%BF%D0%BF%D0%B0%D1%80%D0%B4,_%D0%A2%D0%BE%D0%BC

[2] поле для математических исследований: https://encrypted.google.com/search?q=site%3Aeprint.iacr.org%2F2015+e-voting

[3] проверяемых систем голосования: https://en.wikipedia.org/wiki/End-to-end_auditable_voting_systems

[4] Scantegrity II: http://scantegrity.org/

[5] Helios: https://vote.heliosvoting.org/

[6] избрания: http://www.iacr.org/elections/eVoting/

[7] коих: http://scantegrity.org/papers/scantegrityIEEESP.pdf

[8] достаточно: https://people.csail.mit.edu/rivest/pubs/AR06.pdf

[9] много: http://eprint.iacr.org/2016/670

[10] гомоморфными: https://ru.wikipedia.org/wiki/%D0%93%D0%BE%D0%BC%D0%BE%D0%BC%D0%BE%D1%80%D1%84%D0%BD%D0%BE%D0%B5_%D1%88%D0%B8%D1%84%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5

[11] криптосистема Пэйе: https://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D0%9F%D1%8D%D0%B9%D0%B5

[12] доказательство с нулевым разглашением: https://ru.wikipedia.org/wiki/%D0%94%D0%BE%D0%BA%D0%B0%D0%B7%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D1%81%D1%82%D0%B2%D0%BE_%D1%81_%D0%BD%D1%83%D0%BB%D0%B5%D0%B2%D1%8B%D0%BC_%D1%80%D0%B0%D0%B7%D0%B3%D0%BB%D0%B0%D1%88%D0%B5%D0%BD%D0%B8%D0%B5%D0%BC

[13] non-interactive zero-knowledge: https://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof

[14] схема Шнорра: https://ru.wikipedia.org/wiki/%D0%A1%D1%85%D0%B5%D0%BC%D0%B0_%D0%A8%D0%BD%D0%BE%D1%80%D1%80%D0%B0

[15] DSA: https://ru.wikipedia.org/wiki/DSA

[16] David Chaum’s 2004 article in IEEE S&P: https://people.csail.mit.edu/rivest/voting/papers/Chaum-SecretBallotReceiptsTrueVoterVerifiableElections.pdf

[17] Report The Future of Voting sponsored by the US Vote Foundation: https://www.usvotefoundation.org/sites/default/files/E2EVIV_full_report.pdf

[18] Ben Adida’s GoogleTech talk: https://youtu.be/ZDnShu5V99s

[19] How human and operational factors can compromise e-voting schemes: https://www.usenix.org/legacy/event/sec05/tech/full_papers/karlof/karlof.pdf

[20] Lecture notes on zero-knowledge proofs: http://www.cs.jhu.edu/~susan/600.641/scribes/lecture10.pdf

[21] Источник: https://habr.com/ru/post/436560/?utm_campaign=436560