Прозрачные и проверяемые выборы

Сегодня я хочу рассказать вам о том, как можно сделать процедуру голосования лучше и надежнее. Во-первых, советую посмотреть речь Дэвида Бисмарка на TED или здесь в моей озвучке (перевод Андрея Новика):

Как это работает?

Я расскажу о системе электронного голосования на примере системы Бена Адида, которая отличается от системы Дэвида Бисмарка, но в конечном итоге обладает всеми теми же важными для людей свойствами. Оба варианта — лишь примеры, подобных систем можно придумать огромное количество.

Проблема современных систем голосования (как классических, так и компьютеризованных): человек не может удостовериться в том, что его голос учтен. Объясняется это, обычно, принципом анонимности голосования, но это сугубо техническая причина. Если хорошенько подумать, то можно найти способ проверки собственного голоса без нарушения принятых норм. Хорошее сравнение — банкоматы. Мы все ими пользуемся и доверяем, при этом наши деньги остаются в сохранности, и, что самое главное, мы всегда можем проверить каждую операцию (на сайте или в банке). Хорошая система электронных выборов должна быть проверяема на всех стадиях.

Для такой системы были определены следующие требования:

система публичных/частных ключей: голосующие зашифровывают голос, кандидаты — расшифровывают
легко-генерируемые случайные ключи: для каждого голосующего генерируется случайный ключ, так что голоса за одного кандидата от разных людей не являются идентичными в зашифрованном виде
гомоморфизм

Про последний пункт мы поговорим чуть позже.

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

Каждый кандидат генерирует и публикует следующую информацию:
- Большое простое число p
- Число a_b (по модулю p)
- Публичный ключ y_b (y_b = a^x_b mod p)
  - Частный ключ x_b (случайное число от 1 до p-1; не публикуется!)
Голосующий должен зашифровать свой голос — некое сообщение m (-1<m<p). Каждый голосующий имеет свои публичный и частный ключи — y_a и x_a, соответственно.
- Формируется общий ключ SK (shared key): SK = (y_b)^x_a = (y_a)^x_b
- Голос это пара (c1, c2) = (ya, m*SK) mod p
Только тот кандидат, за которого был отдан голос, сможет его расшифровать:
- (m * SK * SK^-1) mod p = (m * a^x_ax_b* a^-x_ax_b) mod p = m

Вот простой пример:

p = 13, a = 2, y_b = 7, x_b = 11 (7 = 2¹¹ mod p).
m = 7, (c1, c2) = (2⁶, 7*(2¹¹)⁶) mod 13 = (12, 6)
(7*2⁶⁶ * 2^-66) mod 13 = 7 = m.

Теперь немного о последнем пункте списка требований: гомоморфизм (в нашем случае — гомоморфизм групп). Если вы знакомы с теорией групп из математики, то должны вспомнить это свойство. Если коротко: группа это математический объект, «замкнутый» относительно некоторой операции. Например, целые числа относительно сложения — группа, так как взяв два любые элемента из этой группы (два целых числа) и применив операцию сложения (сложив эти числа) мы получим другое целое число — другой элемент той же группы. Это и есть «замкнутость». Такую группу обозначили бы как (Z, +).

Пусть у нас есть две такие группы: (G, *) и (H, ·). Гомоморфизмом будет являться функция h: G → H, если h(u*v) = h(u) · h(v). В нашем случае функцией является зашифровка:

enc(u·v) = enc(u)·enc(v).

Это свойство системы необходимо для обеспечения возможности подсчета голосов публикой без нарушения анонимности голосования. В нашем случае гомоморфизм таков:

enc(m1) · enc(m2) = (y_x₁, m1 · SK1) · (y_x₂, m · SK2) mod p = (y_x₁, · (m1 · m2)(SK1 · SK2)) mod p = enc(m1 · m2).

Как происходит голосование?

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

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

Испытания

Данная система была опробована на выборах в локальные органы самоуправления в университетах MIT, Harvard, Unversite Catholique de Louvain (25000 избирателей), University of Ottawa. 3 ноября 2009 года эта система применялась на выборах в Takoma Park, Maryland, USA.

К прочтению

[1] Ben Adida. Advances in Cryptographic Voting Systems. MIT. (2006). [2] Avi Rubin. An Election Day clouded by doubt, October 2004. [3] Blakley, G. R. Safeguarding cryptographic keys. Proceedings of the National Computer Conference 48: 313-317, (1979). [4] Josh D. Cohen and Michael J. Fischer. A robust and verifiable cryptographically secure election scheme. In FOCS, pages 372–382. IEEE Computer Society, 1985. [5] S. Poblig and M. Hellman, An improved algorithm for computing logarithms over GF(p) and its cryptographic significance, IEEE, Transaction on Information Theory It-24:106-110, (1978). [6] T. El Gamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory, 31, pg. 469-472. (1985) [7] Презентация Jimin Park, Applied Cryptography class, Carleton University, Feb. 2011