Концепция проверяемых выборов

sn0wsky

Источник: http://habrahabr.ru/blogs/htranslations/113877/#habracut



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



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



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



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



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


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

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

  • гомоморфизм



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



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


  1. Каждый кандидат генерирует и публикует следующую информацию:


    • Большое простое число p

    • Число ab (по модулю p)

    • Публичный ключ yb (yb = axb mod p)


      • Частный ключ xb (случайное число от 1 до p-1; не публикуется!)







  2. Голосующий должен зашифровать свой голос — некое сообщение m (-1<m<p). Каждый голосующий имеет свои публичный и частный ключи — ya и xa, соответственно.


    • Формируется общий ключ SK (shared key): SK = (yb)xa = (ya)xb

    • Голос это пара (c1, c2) = (ya, m*SK) mod p




  3. Только тот кандидат, за которого был отдан голос, сможет его расшифровать:


    • (m * SK * SK-1) mod p = (m * axaxb * a-xaxb) mod p = m






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



1. p = 13, a = 2, yb = 7, xb = 11 (7 = 211 mod p).

2. m = 7, (c1, c2) = (26, 7*(211)6) mod 13 = (12, 6)

3. (7*266 * 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) = (yx1, m1 · SK1) · (yx2, m · SK2) mod p = (yx1, · (m1 · m2SK1 · SK2 mod p = enc(m1 · m2).



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


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

  2. Избиратель делает выбор.

  3. Отрывает левую часть.

  4. Уничтожает публичный ключ.

  5. Сканирует бюллетень, уходит домой.



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



Испытания



Данная система была опробована на выборах в локальные органы самоуправления в университетах 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
Понравилось в комментариях:
>> Сейчас то же не составит труда заставить сотрудников проголосовать нужным образом, например заставить всех снять свой бюллетень на камеру от мобильника и потом отчитаться, кто этого не сделает того уволить/отчислить и т.п.
Тем не менее так никто не делает. Потому что это слишком нагло. Потому что это — потенциальная возможность вызвать шумиху в прессе, которая так и ждёт горяченьких фактов.
Лол, чувак в другом мире живет. У нас не просто так делают, это очень и очень распространенная практика.

12457806

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

12457806

А впрочем похуй, я туплю. Быдла же кругом.

rjhgec

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

sever576

все эти концепции это попытки обмануть шулера и заведомо обречены на провал, поскольку шулер будет играть с вами по своим правилам
Оставить комментарий
Имя или ник:
Комментарий: