html текст
All interests
  • All interests
  • Design
  • Food
  • Gadgets
  • Humor
  • News
  • Photo
  • Travel
  • Video
Click to see the next recommended page
Like it
Don't like
Add to Favorites

Mother of the gods, it is Surfingbird!

You finally got here. We've been waiting for you and we have so many interesting things!

Close

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

Сегодня я хочу рассказать вам о том, как можно сделать процедуру голосования лучше и надежнее. Во-первых, советую посмотреть речь Дэвида Бисмарка на 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 · m2)(SK1 · 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
Читать дальше
Twitter
Одноклассники
Мой Мир

материал с habrahabr.ru

0

      Add

      You can create thematic collections and keep, for instance, all recipes in one place so you will never lose them.

      No images found
      Previous Next 0 / 0
      500
      • Advertisement
      • Animals
      • Architecture
      • Art
      • Auto
      • Aviation
      • Books
      • Cartoons
      • Celebrities
      • Children
      • Culture
      • Design
      • Economics
      • Education
      • Entertainment
      • Fashion
      • Fitness
      • Food
      • Gadgets
      • Games
      • Health
      • History
      • Hobby
      • Humor
      • Interior
      • Moto
      • Movies
      • Music
      • Nature
      • News
      • Photo
      • Pictures
      • Politics
      • Psychology
      • Science
      • Society
      • Sport
      • Technology
      • Travel
      • Video
      • Weapons
      • Web
      • Work
        Submit
        Valid formats are JPG, PNG, GIF.
        Not more than 5 Мb, please.
        30
        surfingbird.ru/site/
        RSS format guidelines
        500
        • Advertisement
        • Animals
        • Architecture
        • Art
        • Auto
        • Aviation
        • Books
        • Cartoons
        • Celebrities
        • Children
        • Culture
        • Design
        • Economics
        • Education
        • Entertainment
        • Fashion
        • Fitness
        • Food
        • Gadgets
        • Games
        • Health
        • History
        • Hobby
        • Humor
        • Interior
        • Moto
        • Movies
        • Music
        • Nature
        • News
        • Photo
        • Pictures
        • Politics
        • Psychology
        • Science
        • Society
        • Sport
        • Technology
        • Travel
        • Video
        • Weapons
        • Web
        • Work

          Submit

          Thank you! Wait for moderation.

          Тебе это не нравится?

          You can block the domain, tag, user or channel, and we'll stop recommend it to you. You can always unblock them in your settings.

          • tachikoma
          • домен habrahabr.ru

          Get a link

          Спасибо, твоя жалоба принята.

          Log on to Surfingbird

          Recover
          Sign up

          or

          Welcome to Surfingbird.com!

          You'll find thousands of interesting pages, photos, and videos inside.
          Join!

          • Personal
            recommendations

          • Stash
            interesting and useful stuff

          • Anywhere,
            anytime

          Do we already know you? Login or restore the password.

          Close

          Add to collection

             

            Facebook

            Ваш профиль на рассмотрении, обновите страницу через несколько секунд

            Facebook

            К сожалению, вы не попадаете под условия акции