Организация честного голосования // the220th stash

Содержание

Организация честного голосования

Здесь будет описано, что такое честное голосование, и постараемся его организовать.

Прежде чем начинать

Определимся, что такое вообще голосование и как это происходило до сего момента.

Голосование — способ принятия решения группой людей, при котором общее мнение формулируется путём подсчета голосов членов группы.

Также хорошо было бы определиться с тем, какие бывают голосования, кто может голосовать, и кто участвует в голосовании.

Виды голосований

По возможности определения голосующего:

Открытое.
Тайное.

Открытое:

Здесь я думаю понятно. Голосующий открыто всем рассказывает за кого/что голосует.

Тайное:

С этим не так всё просто. Нужно обеспечить анонимность голосующим по разным причинам (не будем вдаваться в подробности по каким). Тайное голосование практикуют с древних времён. Ещё в Древних Афинах так голосовали при принятии различных решений.

По способу голосования

Здесь имеется ввиду как именно показать свой голос, можно придумать много вариантов:

Жестикуляция. Поднять руку или палец вверх, кивнуть или ещё как-нибудь.
Звук. Можно просто назвать претендента.
Предметы. Как вариант можно сказать, что камешек – это претендент 1, а палочка - это претендент 2. Далее складывать это в коробочку, потом считать.
Бюллетени. Наверное, это первое, что приходит в голову. “Бумажки”, на которых делается выбор, потом сдаются.
Механические или электромеханические средства. Подойти и нажать кнопку с номером кандидата. Или электрический регистратор голосов Эдисона 1869 год.
Электронное. Это, наверное, нас и интересует в первую очередь. Подразумеваются как электронные средства голосования, так и технические электронные средства подсчёта голосов. Сюда включаются, в том числе и перфокарты, где голосующий проделывает дырочку, а дальше какое-нибудь электронное устройство считает голоса. Или ещё вариант поставить галочку на бумаге, которую потом считает сканер. СМС-голосование – тоже вариант. Но самое интригующее – это, конечно, интернет голосование.

Немного про интернет голосование:

В мире набирает обороты практика интернет-голосования на специализированных сайтах или с помощью специального программного обеспечения. Избиратели могут сделать свой выбор не только на избирательных участках, оборудованных компьютерами, но и в любом удобном месте: интернет-кафе, дома или со смартфона. Звучит, конечно, не очень с точки зрения безопасности. Но об этом позже, как раз и нужно добиться в этом материале того, чтобы всё было “безопасно” и честно.

В США первым опытом Интернет-голосования стали предварительные выборы Демократической партии в штате Аризона в марте 2000 г. В феврале 2008 г. было организовано Интернет-голосование на первичных выборах для избирателей-демократов, находящихся за границей.

Неплохое распространение Интернет-голосование получило в Швейцарии и Эстонии. В швейцарском кантоне Женева для Интернет-голосования на референдумах используются избирательные карточки. Перед голосованием избиратель, предъявив паспорт, может взять в своем почтовом отделении карточку для электронного голосования с уникальным номером и секретным кодом, скрытым под защитным слоем. Далее, на сайте электронного голосования кантона следует ввести номер карточки, поставить галочки напротив нужных вариантов вопросов референдума, затем, убрав с карточки защитный слой, ввести секретный код и получить электронное подтверждение голоса, которое в дальнейшем может быть проверено в администрации кантона. Карточка является одноразовой и перед каждым голосованием за ней надо ходить на почту. В 2005 г. Эстония стала первой страной, предложившей общенациональные выборы местных органов власти через Интернет. В Эстонии для Интернет-голосования вне избирательных участков необходимо с сайта Республиканской избирательной комиссии скачать специальное ПО, а также иметь ID-карту гражданина Эстонии с кардридером, подключаемым к компьютеру, или SIM-карту Mobiil-ID, вставляемую в сотовый телефон. В начале процедуры голосования избиратель проходит двухфакторную аутентификацию (по карте и PIN-коду).

Обязательность

Добровольное.
Обязательное.

Можно голосовать по желанию или сделать голосование обязательным. Обязательным по разным причинам, например для увеличения легитимности.

На протяжении всей истории встречаются примеры, когда голосование вменялось в обязанность. В ряде полисов Древней Греции существовал закон: если гражданин уклонялся от участия в выборах, то его лишали гражданства и изгоняли, объясняя это решение тем, что полису не нужен гражданин, которому безразлична судьба его государства. Первыми странами, которые посредством законодательного регулирования ввели обязательное голосование, были: Бельгия – в 1892 г., Аргентина – в 1914 г. и Австралия – в 1924 г.

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

Способ явки

Очное. Голосующий приходит и голосует в специальном пункте.
Дистанционное. Голосующий никуда не ходит и голосует с любого компьютера.

Здесь у кого не спроси, кому не скажи, почти все будут говорить, что невозможно сделать дистанционное голосование честным. Мы попробуем.

По количеству голосов на голосующего

Равноправное. «Один голосующий – один голос».
Неравноправное. Избиратели изначально находятся в неравных условиях. Часть избирателей оказывается в привилегированном положении по сравнению с другими в силу своего сословного, имущественного, должностного, территориального и т.п. положения.

Сюда же можно отнести ситуацию, когда кандидат отражает мнение меньшинства. Поэтому у избирателей может быть несколько голосов. Или ситуация, когда у определённого слоя населения есть дополнительные голоса (Бельгия, собственникам крупного состояния давался доп. голос).

Ограничения голосов

Не всех можно допускать к голосованию по разным причинам.

Например, если выбирают куда поедут школьники на экскурсию, то голосовать, например, могут только: сами школьники, их родители, сопровождающие и администрация школы. Остальных же это не касается, и эти остальные не должны голосовать.

Или какие-нибудь выборы в государстве. Тогда ограничения для избирателей и кандидатов могут быть следующих видов:

По гражданству. Например, голосуют только граждане.
По возрасту. Например, голосуют только с/до определённого возраста.
По сроку проживания в государстве. Например, голосуют только те, кто прожил определённое кол-во времени в государстве.
По состоянию здоровья. Тут имеется ввиду психическое.
По истории гражданина. Например тем, кто привлекался к уголовной ответственности, ограничить голос.
По стоимости имущества. Например, ограничить голос тем, у кого имущество стоит меньше, чем определённое кол-во усл. ед.
По социальному статусу. Например, разрешить голосовать только определённому классу граждан.
По служебному положению. Например, запретить быть избранным военным или священникам.
По образованию. Например, голосуют только те, кто умеет читать.
По половому признаку.
Какие-то ещё ограничения.

Участники голосования

Попробуем выделить участников:

Сами голосующие. То есть те, кто и будет голосовать.
Кандидаты/Варианты. Те, за кого голосуют, или то, за что голосуют.
Регистратор. Тот, кто определит, кто может голосовать, а кто нет, проконтролирует это, и примет голос.
“Счётчик”. Тот, кто считает голоса.

Вопрос только в том, пересекаются ли эти множества?

Ещё пару слов

Что мы поняли? Голосование бывает разное, голосовать могут не все и в голосовании участвуют: голосующие, кандидаты, избирательная комиссия и “счётчик”.

Также нужно бы определиться с самой системой, для чего будем делать честное голосование? Потому что, если говорить про выборы из двух и более кандидатов, то найдутся те, кто скажет, что сама система (демократия) неправильная и нечестная, или те, кто спать не сможет, пока не проголосует. Абстрагируемся. Есть задача, нужно организовать голосование таким образом, чтобы можно было бы гарантировать, что оно будет честное. Чтобы “математика” гарантировала. А для чего делается система, сейчас не важно.

Что такое честное голосование?

Что из себя представляет честное голосование? Нужно ввести какие-то критерии, на которые мы будем дальше опираться:

Голосовать могут только те, кто имеет право (1)
При подсчете результатов голосования для каждого избирателя учитывается не более одного голоса (2)
Никто не может узнать, за кого проголосовал конкретный избиратель (3)
Никто не может проголосовать за другого (4)
Никто не может тайно изменить чей-то голос (5)
Голосующий может проверить, что его голос учтён и учтён правильно (6)
В случае, если голос зачтён неправильно, голосующий может сообщить об этом (7)
Каждый знает кто голосовал, а кто нет (8)
Голосующий может изменить свое мнение (9)

(3) - этот пункт самый сложный и спорный. И уж тем более не надо говорить, что если голосующих мало, то пункт (3) становится вообще бессмысленным. Также стоит отметить, что он (пункт) хоть как-то снижает продажу голосов. В том смысле, что теперь сложнее доказать, что избиратель проголосовал именно так, а не иначе, тому, кто подкупил голосующего. Но, с другой стороны, всегда можно проголосовать прямо перед скупщиком или ещё как-нибудь. Ещё и пункт (6) даёт возможность голосующему посмотреть на то, как он проголосовал, осталось сделать это перед скупщиком (а потом проголосовать как хочешь, см. пункт (9)). Избавиться от этой проблемы (подкуп голосов) почти нереально, но зато все эти пункты сильно ограничивают тех, кто принимает и считает голоса, что сильно важнее, потому что вреда от этого больше.

(5) - ключевое слово тайно. Если кто-то что-то изменит, то это станет известно голосующему, и тогда см. пункты (6) и (7)

(7) - нужно, чтобы ЦИК принимал жалобы. Он может попросту проигнорировать сообщение с ошибкой. Также нужны доказательства того, что голосующий всё сделал верно.

(8) - пункт может быть нужен для того, чтобы голосующие убедились, что голосовали только легитимные участники. Также знать каждому кто голосовал, нужно ещё и для того, чтобы регистратору было сложнее делать “мёртвые души”. Это вообще на самом деле неразрешимая проблема, но пункт 8 хотя бы как-то улучшает ситуацию. Ведь теперь можно “поимённо” пройтись по списку и убедиться, что это всё реальные люди. Но об этом поговорим позже.

(9) - тоже скорее опциональный пункт. Хотя полезен для уменьшения подкупа голосов.

Ключевой момент ещё в том, что хотелось бы всё это сделать в электронном, дистанционном формате.

С этим определились, посмотрим на протоколы.

Традиционное («бумажное») голосование

Происходит это так:

Избирательная комиссия формирует списки голосующих и готовит бюллетени. Под формирует имеется ввиду следующее:
1. Публикуется список всех возможных избирателей.
2. Голосующие сообщают, что хотят голосовать (не все же придут из пункта выше).
3. Формируются списки голосующих.
В день выборов голосующий приходит на избирательный участок, предъявляет документ, удостоверяющий личность, его регистрируют (проверяют) в списке избирателей, он получает бюллетень, расписывается в его получении. Далее голосует и опускает бюллетень в урну за ширмой.
После окончания голосования избирательная комиссия подсчитывает результаты голосования и отсылает результаты в центральную избирательную комиссию (ЦИК).

Теперь разберём это поподробнее.

Пункты честного голосования.

Плюсы, которые, вроде как, должны выполняться:

Голосуют только те, кто имеет право. Выполняется (1)
Голосующий голосует не более одного раза. Выполняется (2)
Соблюдается анонимность. Выполняется (3)
Никто не может проголосовать за другого. Выполняется (4)
Никто не может тайно изменить чей-то голос. Выполняется (5)

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

Члены избирательной комиссии могут проголосовать вместо не пришедших на голосование.
Члены избирательной комиссии могут сделать недействительными некоторые бюллетени. Например, разрисовать бюллетень или поставить ещё галочек. То есть можно вычеркивать пункты (4) и (5).
Итоги голосования могут быть непреднамеренно неправильно посчитаны.
Итоги голосования могут быть преднамеренно неправильно посчитаны.
В кабинках за ширмой могут быть скрытые камеры. В теории, можно сказать, что пункт (3) не выполняется.

Что ж, почти плюсов не осталось. Хочу отметить, что при организации честного голосования предполагается, что случается самое худшее. Это как при тестировании системы: она должна работать при наихудших событиях. Конечно, избирательная комиссия честная, но хотелось бы составить систему голосования так, чтобы об этом даже не задумываться.

Перейдём к минусам:

Голосующий не может проверить, что его голос учтён. И уж тем более, учтён ли правильно. Один из самых больших минусов. Не выполняется пункт (6), а следом и (7).
Долго. Пока дойдёшь до центра, заполнишь бумаги… Это мелочи. А важно вот что: результаты голосования обрабатываются относительно долго (около нескольких дней).

Иногда публикуются списки проголосовавший, а иногда – нет. Также и пункт (8) может выполняться, а может и нет.

Смотрим, что ещё есть.

Симметричное шифрование, асимметричное шифрование, цифровая подпись, слепая подпись

Прежде чем начать следующие пункты, нужно разобраться как работает симметричное и асимметричное шифрование.

Правда с одной оговоркой: шифрование – это не тема данного исследования, рассматривается именно честное голосование. Поэтому подробно рассказываться, как шифрование работает (и уж тем более доказательства), здесь не будет. Пробежимся кратенько. Если вам нужны подробности, то можете посмотреть здесь или ещё где-нибудь в интернете.

Симметричное шифрование - алгоритм, который с помощью ключа key может зашифровать сообщение msg с помощью функции encrypt. То есть msg_en = encrypt(msg, key), где msg_en - это зашифрованное сообщение. А потом с помощью того же ключа key может расшифровать сообщение msg_en с помощью функции decrypt, т. е. msg = decrypt(msg_en, key). Ключевой момент, что ключ key для шифрования и дешифрования одинаковый. Мы не будем рассматривать как именно генерируется ключ и как устроены функции encrypt и decrypt. Скажем просто, что будем использовать AES-256. Это один из самых криптостойких на данный момент алгоритм симметричного шифрования. Про AES-256 можно почитать тут.

Прежде чем двигаться дальше, давайте представим ситуацию: есть Боб и Алиса. Они очень сильно хотят обменяться сообщением с очень важным секретом, причём с таким секретом, что нельзя кому-либо о нём рассказывать. Но есть несколько проблем. Первая - они не способны встретиться лично на улице по разным причинам, поэтому они могут только писать друг другу в интернете. И вторая - они знают, что Ева читает их переписку. На протяжении тысяч лет эта задача была не разрешима, но был изобретён алгоритм Диффи—Хеллмана—Меркла, который решил эту проблему. А потом и ещё многие. С помощью этих алгоритмов Алиса и Боб могут обменяться сообщениями у всех на виду, и Ева не сможет украсть их секрет.

Асимметричное шифрование - алгоритм, где есть 2 ключа: публичный pubKey и секретный privKey. Публичный ключ рассказывается всем, секретный вообще никому. Сообщение msg шифруется с помощью функции encrypt и публичного ключа, получается зашифрованное сообщение msg_en = encrypt(msg, pubKey). Чтобы расшифровать сообщение, используется функция decrypt и приватный ключ: msg = decrypt(msg_en, privKey). Не будем рассматривать как именно генерируются ключи и как устроены функции encrypt и decrypt. Будем просто использовать алгоритм RSA-4096. Про RSA можно почитать тут.

То есть примерно всё так будет: Боб хочет отослать Алисе секрет. Алиса рассказывает всем свой публичный ключ. Боб шифрует сообщение с помощью публичного ключа Алисы, отсылает ей сообщение, которое потом она дешифрует с помощью своего приватного ключа. То есть у каждого собеседника есть свои публичный и приватный ключи. Вот так Алиса и Боб обменялись сообщением, а Ева не смогла прочитать его, хотя она прослушивала канал связи.

Теперь про цифровую подпись. Здесь тоже используется асимметричное шифрование, тоже есть публичные pubKey и приватные privKey ключи и функции encrypt и decrypt. В чём вообще суть? Есть какой-то документ Document.pdf, и Боб хочет подписать его. Поставить свою “подпись” так, чтобы можно было бы точно сказать, что он действительно поставил подпись и что, пока документ шёл до Алисы, ни один бит не поменялся в файле. Делается это так. Боб подписывает документ с помощью приватного ключа: signedDocument.pdf = encrypt(Document.pdf, privKey). Далее отсылается signedDocument.pdf Алисе, и та проверяет подпись с помощью публичного ключа Боба: Document.pdf = decrypt(signedDocument.pdf, pubKey). Но теперь функции будут называться по-другому: encrypt – это sign, а decrypt – это unsign, да и подписываются не сами документы/файлы, а их хэш. Про подпись для RSA можно почитать тут.

Хэш-функция f(x) = y – это такая функция, где y посчитать относительно легко, а вот, зная только y, посчитать x почти нереально. y – это и есть хэш. Причём если x1 и x2 отличаются совсем чуть-чуть (даже хотя бы на 1 бит), то y1 = f(x1) и y2 = f(x2) будут совсем разные. То есть у y1 и y2 будет разное почти “всё”. Например, f(a123) = abywz и f(a124) = gyizu. Мы будем использовать SHA-256. И ещё, под signedDocument.pdf мы будем подразумевать сам документ и подпись. То есть примерно так: signedDocument.pdf = {Document.pdf, f(Document.pdf)_sig}. Про хэш можно почитать тут.

Например, если Document.pdf = aaa, f(Document.pdf) = ngkat, encrypt(ngkat, privKey) = toebl, тоsignedDocument.pdf = {aaa, toebl} = sign(Document.pdf, privKey).

Ещё осталась слепая подпись. Может потребоваться по разным причинам, чтобы Алиса подписала что-то, не зная, что она подписывает. Например, Боб имеет документ Doc.pdf, который нужно, чтобы подписала Алиса, но сама Алиса не должна знать, что подписывает. Это делается с помощью какого-то числа r, функции blind и публичного ключа Алисы pubKey. Скрываем содержимое документа hiddenDoc.pdf = blind(Doc.pdf, r, pubKey). После Алиса подписывает сообщение с помощью своего приватного ключа privKey: signedHiddenDoc.pdf = sign(hiddenDoc.pdf, privKey), и отсылает обратно Бобу. А Бобу же остаётся снять число r: signedDoc.pdf = unblind(signedHiddenDoc.pdf, r). Вот так Алиса подписала что-то, не зная что. Можно проверить с помощью публичного ключа Алисы pubKey её подпись: Doc.pdf = unsign(signedDoc.pdf, pubKey). Как генерируется число r и как устроены функции blind и unblind, мы рассматривать не будем. Про слепую подпись можно почитать тут.

Зачем вообще так делать?! Предположим, Алиса – это человек, который подтверждает личность. Что-то вроде нотариуса. Боб хочет анонимно куда-то послать документ Doc.pdf, но место, куда Боб отсылает Doc.pdf, не принимает документы от кого попало. Скажем что нужно, чтобы документы обязательно отсылали люди, а не боты. Алиса создаёт специально ключи для подтверждения личности и ни для чего больше. Причём, когда она рассказывает всем свой публичный ключ, она уточняет, что он только для заверения личности и что Алиса вообще понятия не имеет, что подписывает. Место, куда Боб собирается отослать Doc.pdf, доверяет Алисе, так как она подписывает документы только реальным людям с паспортами. Вот зачем слепая подпись может понадобиться. Чтобы подтвердить, что Боб – это человек, а не бот.

Далее для симметричного шифрования, асимметричного шифрования и подписи будет использоваться эта библиотека: https://github.com/The220th/CipherJavaLib.

Теперь посмотрим, как это всё применить на алгоритмах голосования. От самого простого к самому соку.

Простейший протокол

Начнём с чего-то попроще. Знакомьтесь, действующие лица: ~~Алиса и Боб…~~ А если серьёзно, пусть это будут: агентство, проводящее голосование, и голосующие. 2 “сущности” короче.

Всё будет происходить так:

Агентство составляет списки:
1. Агентство выкладывает списки потенциальных голосующих, тех кому вообще можно голосовать.
2. Голосующие сообщают агентству о желании голосовать. Приходят, например, с паспортом в агентство.
3. После этого агентство выкладывает списки тех, кто голосует.
Агентство создаёт ключи: публичный A_pubKey и приватный A_privKey. Публичный рассказывается всем.
Голосующий:
1. Голосует, отмечает свой выбор в бюллетене B.
2. С помощью открытого ключа A_pubKey шифрует свой выбор: B_en = encrypt(B, A_pubKey).
3. Отсылает B_en агентству.
Агентство:
1. С помощью своего закрытого ключа дешифрует бюллетень B = decrypt(B_en, A_privKey).
2. Считает голоса и публикует.

Одно дополнение:

Шаг 1 нужен для определения и объявление числа активных участников. Хотя некоторые из них могут не участвовать, а некоторые и вовсе не существовать («мёртвые души», злонамеренно внесённые агентством), возможность манипулирования голосованием у агентства заметно снижена. Больше это затрагивать не будем.

Пункты честного голосования.

Плюсы:

Простота. Действительно просто реализовать.
Никто не может узнать, за кого проголосовал конкретный избиратель. Выполняется (3).

Пожалуй, это всё. Теперь минусы:

Голосует кто угодно… Чтобы проголосовать, нужно лишь знать открытый ключ агентства. Агентство в свою очередь не знает откуда пришли бюллетени. Минус (1).
Голосовать можно сколько захочешь раз. Минус (2).
Агентство вообще никто не контролирует. Оно может манипулировать голосами вообще, как хочет. Минус (4) и (5).
Голосующий никак не проверит, что его голос учтён, и как учтён. Минус (6) и (7).
Голосующие вообще не вкурсе, кто голосовал, а кто - нет. Минус (8).

Про (9), пожалуй, промолчим.

Протокол никуда не годится. Идём дальше.

Простой протокол

Вообще многих проблем можно было бы избежать в простейшем протоколе, если бы голосующие создавали бы свои публичные и приватные ключи, регистрировали бы их, и подписывали свой выбор. Изменим предыдущий протокол:

Голосующий создаёт публичный E_pubKey и приватный E_privKey ключи.
Агентство создаёт ключи: публичный A_pubKey и приватный A_privKey. Публичный рассказывается всем.
Агентство составляет списки:
1. Агентство выкладывает списки потенциальных голосующих, тех кому вообще можно голосовать.
2. Голосующие сообщают агентству о желании голосовать, заодно регистрируют там E_pubKey. Приходят, например, с паспортом в агентство и показывают свой публичный ключ. То есть теперь агентство знает кому какой ключ принадлежит.
3. После этого агентство выкладывает списки тех, кто голосует.
Голосующий:
1. Голосует, отмечает свой выбор в бюллетене B.
2. С помощью своего закрытого ключа E_privKey подписывает бюллетень: B_s = sign(B, E_privKey).
3. Далее B_s шифруется с помощью A_pubKey: B_s_en = encrypt(B_s, A_pubKey).
4. B_s_en отсылается агентству. Тут же он может отослать и свой публичный ключ E_pubKey, чтобы проверять подпись агентству было легче.
Агентство:
1. Расшифровывает B_s_en с помощью своего приватного ключа A_privKey: B_s = decrypt(B_s_en, A_privKey).
2. Проверяет подпись: B = unsign(B_s, E_pubKey).
3. Считает голоса и публикует.

Пункты честного голосования.

Плюсы:

Простота. Всё ещё просто. Пока что…
Голосовать могут только те, кто имеет право. Выполняется (1).
Один голос на голосующего. Выполняется (2).
Анонимность ? Остальные голосующие действительно не знают за кого мы проголосовали.
В теории мы не можем голосовать за другого, если не знаем его приватный ключ. Выполняется (4).
Если голосующий передумал, то можно повторить пункт 4. Агентство же увидит, что он уже голосовал, и поменяет его выбор. Выполняется (9).

Теперь минусы:

Анонимность не соблюдается. Агентство знает наши “паспортные данные” и наш выбор. Так что ни о какой анонимности на самом деле речи и не идёт. Минус (3).
Агентство по-прежнему никто не контролирует. Они спокойно могут подменять голоса. Минус (5).
Голосующий никак не проверит учтён ли вообще его голос, и как учтён. Минус (6) и (7).
Голосующие не знают кто голосовал, а кто - нет. Минус (8).

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

Протокол двух агентств Нурми-Саломаа-Сантин

Основная идея состоит в том, чтобы заменить одно избирательное агентство двумя, чтобы они контролировали друг друга. А то надоели подменять голоса)

Вводится новый персонаж: ~~Ева…~~ Регистратор. Тот, кто хотя бы как-то исправит положение. Он будет регистрировать избирателей, подтверждать их личность, а агентство теперь будет счётчиком. Счётчик считает и принимает голоса.

Сам алгоритм:

Регистратор составляет списки:
1. Регистратор генерирует уникальные метки {M}.
2. Регистратор выкладывает списки потенциальных голосующих, тех кому вообще можно голосовать.
3. Голосующие сообщают регистратору о желании голосовать. Приходят с документом, удостоверяющий личность, к регистратору.
4. Регистратор выдаёт голосующим уникальную метку M из {M}.
5. После этого Регистратор выкладывает списки тех, кто голосует.
6. Регистратор сообщает по защищённому каналу счётчику все уникальные метки {M}, но без указания кому-какую метку отдали.
Голосующий:
1. Делает свой выбор в бюллетене B.
2. Создаёт ключ для симметричного шифрования key (зачем это нужно, будет сказано позже).
3. С помощью секретного ключа key шифрует свою уникальную метку M и бюллетень B в виде единого файла {M, B}_en = encrypt({M, B}, key).
4. Анонимно посылает метку M и {M, B}_en счётчику.
Счётчик публикует где-нибудь в открытом доступе M и {M, B}_en.
Голосующий после того, как увидит свою метку M и {M, B}_en в открытом доступе (на сайте счётчика например), отправляет счётчику свой ключ для симметричного шифрования key.
Счётчик:
1. Дешифрует: {M, B} = decrypt({M, B}_en, key).
2. В дополнение к M и {M, B}_en публикует ещё и {M, B}.
3. Считает, подводит результаты.

Фух, этот посложнее. Сделаем пару уточнений:

Тут, когда передаются какие-то данные, то они передаются по защищённому каналу. Лень всё это расписывать. То есть у каждого опять есть публичные и приватные ключи, по которым они могут друг-другу шифровать и уже потом отправлять сообщения.
Как вы уже, наверное, поняли ключ для симметричного шифрования key создаётся для того, чтобы ни счётчик, ни посторонний не могли до нужного времени узнать содержимое бюллетеня. Плюс ко всему счётчик не сможет отрицать, что не получал бюллетень от голосующих. Благодаря публикации зашифрованного текста и бюллетеня, каждый может проверить, что его голос был учтен должным образом.
Теперь про метки {M}. Здесь есть что сказать:
- Во-первых, метку можно просто угадать. Имеется ввиду такая ситуация: предположим мы тот, кто не голосует. А нам хочется (не спрашивайте почему). Мы начинаем усердно слать счётчику наш бюллетень с рандомными метками. Рано или поздно может быть получится угадать. Поэтому эти метки должны не идти “друг за дружкой” (1, 2, 3, …), а быть рандомными на отрезке. Причём чем более длинный отрезок, тем лучше. Например, брать случайно метки с отрезка [10^100; 10^100^10]. Вроде, теперь почти не угадать (попробуйте посчитать вероятность). Или вообще этими метками могут быть длинные строками с рандомными символами.
- Во-вторых, метки можно и подписать. Пусть регистратор подпишет метки при их создании, тогда вообще не будет никаких проблем. Ведь теперь будет гарантироваться, что именно регистратор дал эти метки, а не случайно угадываются.
Ещё немного про ключ key. Его нужно передавать по защищённому каналу. Это нужно, чтобы можно было переголосовать.
Чтобы переголосовать необходимо создать новый бюллетень B2, зашифровать и прислать вновь M и {M, B2}_en, но теперь с ключом key, чтобы удостовериться, что это мы раньше голосовали.
По окончанию голосования регистратор, может опубликовать, зная кому какая метка принадлежит, и кто проголосовал, список всех проголосовавших. Таким образом будет выполняться (8).

Пункты честного голосования.

Плюсы:

Голосовать могут только те, кто имеет право. Выполняется (1).
Один голос на одного голосующего. Выполняется (2).
Анонимность? Другие избиратели не знают, кто за кого проголосовал.
Мы не можем проголосовать за другого. Выполняется (4).
Никто не может тайно изменить чей-то голос. Ведь теперь мы видим, что счётчик принял наш голос. Уже никуда не деться всяким там агентствам. Голосующие могут всё доказать. Выполняется (5) и (6). Хотя тут тоже есть одно “НО”. Но об этом ниже.
В случае, если голос зачтён неправильно, голосующий может сообщить об этом. Выполняется (7).
Каждый знает кто голосовал, а кто нет. Правда, если регистратор опубликует список всех голосовавших. Тем не менее выполняется (8).
Голосующий может изменить свое мнение. Выполняется (9).

Минусы:

Начнём с главного. Анонимность на самом деле не выполняется. У регистратора есть список всех меток с привязкой к конкретному человеку. Также у регистратора есть информация о том, “какая метка” за кого/что проголосовала. Сложить 2+2 и теперь регистратор вообще всё знает. Короче, (3) не выполняется. А ведь было так близко. Но это не единственный косяк.
Опять-таки приходится кому-то доверять, в данном случае регистратору. Во-первых, он всё про всех знает. Во-вторых, его базу данных могут взломать и выкрасть всё, тогда уже будут все всё знать (хотя это было и в предыдущем протоколе). И, в-третьих, вообще-то никто не мешает счётчику сговориться с регистратором.
Если счётчик всё-таки сговорится с регистратором, то тогда счётчику будут известны метки, и он может специально не принимать сообщения от некоторых голосующих.
И ещё одна проблема: если регистратор внесёт в список заведомо несуществующих голосующих, то счётчик сможет фальсифицировать бюллетени от них.

Немного про регистратора

Как видно от регистратора уж слишком много зависит. Во-первых, он по-прежнему уничтожает анонимность (но это мы ещё исправим!). Во-вторых, он может понаделать избирателей столько, сколько ему захочется. Опять приходится кому-то доверять. Никто же не следит за самим регистратором, он может наплодить “мёртвых душ”, которые будут голосовать как ему угодно. Но, это всё может ловиться межотраслевыми средствами. Если проходят, например, городские выборы, то “призрака” могут уловить: загс, школы, университеты, военкоматы, кадровые агентства и т. п. Если голосование проходит в какой-нибудь организации, то существуют отдел кадров и начальники, наверняка они что-нибудь заметят. А если голосование в маленькой компании людей, где все друг друга знают, то это вообще не проблема. Ну думаю принцип понятен. Но может всё-таки попробовать придумать что-нибудь такое, что бы вообще заменило регистратора?

А что, если сами голосующие его заменят? Предположим, мы начальник какого-то коллектива. Весь коллектив мы знаем в лицо. Почему бы нам не подписать их ключи? Можно ещё и подписать ключи друзей, которых хорошо знаем и т. д. В свою очередь наш ключ, тоже подпишут хорошие знакомые и т. д. При этом все публичные ключи выкладываются в открытый доступ. Это всё можно представить в виде графа, где связи – это подпись одной “вершины” ключа другой “вершины”. Теперь, когда счётчику придёт сообщение с голосом избирателя, счётчику нужно посмотреть в открытой базе ключей, что ключ избирателя подписан кем-нибудь, кому счётчик доверяет. А если ещё добавить степень доверия, то граф будет ещё реальнее отражать эту картину. Под степенью доверия имеется вот что: при подписании ключа, мы можем указать насколько сильно, мы доверяем человеку по шкале от 0 до 9 например. Если появятся боты (или обиженные нелегитимные голосующие), которые подписывают друг-другу ключи, то в этом графе появятся некоторые моменты, которые сразу бросаются в глаза. Имеется ввиду вот что. Проанализировав такой граф, можно будет сделать вывод о том, кто нам прислал голос. Но есть способы и обмануть такую систему. Скажем, есть человек, который голосует за себя и за того парня. Имеется ввиду, что у него 2 публичных ключа. Он с помощью социальной инженерии (или, например, за деньги) может попросить кого-нибудь подписать второй ключ. Таким образом у него может быть 2 голоса. Короче, это хорошо, когда сами голосующие поддерживают систему, но нужно быть уверенным, что хотя бы большая часть (процентов 95%) будут честные. Да и вообще нужно каждому в этой системе рассказать, как она работает, и что нужно кому делать, а иначе это всё бессмысленно, потому что можно будет обмануть невежду.

Короче, приходится выбирать из двух стульев. Всё же сделаем выбор в пользу регистратора. Или регистраторов (их же может быть несколько). Если их много, то ситуация улучшится. Но для простоты будем говорить, что регистратор один. Кому мы можем вообще доверять в этом мире на сегодняшний день? Наверное тому, кому мы доверяем свои денюшки. На данный момент банки могут вас идентифицировать на тех же госуслугах (а это весомый аргумент). Думаю, такой вариант устроит многих.

Протокол на основе ANDOS

Давайте немного забудем про регистратора (хотя, конечно, он ещё вернётся) и посмотрим на такую штуку как ANDOS. Это криптографический протокол «секретной продажи секретов». Продавец имеет список секретов с ответами и выставляет их на продажу. Покупатель желает купить секрет, но не хочет раскрывать какой именно. Протокол гарантирует, что покупатель получит нужный ему секрет и ничего более, в то время как продавец не будет знать, какой именно секрет получил покупатель. Под продавцом здесь имеется ввиду агентство, под покупателями - голосующие, а под секретами и ответами - номера меток и сами метки {M}. Сам протокол сложный, и здесь он не будет описываться, можно о нём почитать в интернете. Главное – это то, что агентство раздаст метки, но какая кому достанется, никто не узнает.

Пример как может работать ANDOS. Есть оооочень большие числа {M} (ответы). Также есть их порядковые номера {1, 2, 3, ...} (секреты). Всё это генерируется агентством. Потом оно выставляет напоказ все порядковые номера. Голосующие выбирают секрет (порядковый номер). Например, мы выбрали секрет с номером 1291261 и хотим “купить” ответ. Отрабатывает протокол ANDOS, мы получаем число M с порядковым номером 1291261. Например, M такое. И при этом никто не знает, какой секрет (в данном случае 1291261) мы купили, и что в ответе (то есть в M). А агентство не знает, кто купил какой ответ.

Сам протокол:

Агентство составляет списки:
1. Агентство выкладывает списки потенциальных голосующих, тех кому можно голосовать.
2. Голосующие сообщают агентству о желании голосовать. Приходят с паспортом в агентство.
3. После этого агентство выкладывает списки тех, кто голосует.
Агентство генерирует набор уникальных меток {M} и с помощью протокола ANDOS распределяет их между голосующими. Как уже было сказано, агентство не может определить принадлежность метки конкретному голосующему.
Голосующий:
1. Делает свой выбор в бюллетене B.
2. Создаёт ключ для симметричного шифрования key.
3. С помощью секретного ключа key шифрует свою уникальную метку M и бюллетень B в виде единого файла {M, B}_en = encrypt({M, B}, key).
4. Анонимно посылает метку M и {M, B}_en агентству.
Агентство публикует M и {M, B}_en в доказательство избирателю, что голос принят.
Голосующий после того, как увидит свою метку M и {M, B}_en, отправляет агентству свой ключ key.
Агентство:
1. Дешифрует: {M, B} = decrypt({M, B}_en, key).
2. В дополнение к M и {M, B}_en публикует ещё и {M, B}
3. Считает голоса, подводит результаты

Примечания:

Когда кто-то обменивается данными, то это происходит по защищённому каналу.
Как и в предыдущем протоколе меток должно быть или очень много, или их нужно подписывать. Или и то, и другое.
На этапе 2 голосующим в теории может выпасть одна и та же метка. Опять-таки, это можно минимизировать, сделав их очень большое количество. Если это произойдет, то: агентство генерирует новую метку М2, которая не использовалась нигде ранее, выбирает одного из избирателей с коллизией и публикует {M, М2, {M, B}_en}. Голосующий видит, что произошла коллизия. Он заново шифрует уже с новой меткой {M2, B}_en тем же ключом key и отсылает агентству: M2 и {M2, B}_en. Так может сделать только тот, кто до этого отсылал {M, B}_en. Проверить это легко, потому что один и тот же ключ key (известный только “правильному” голосующему) расшифрует и {M, B}_en, и {M2, B}_en.
Если сделать столько же меток {M}, сколько и голосующих, то будет сложнее агентству манипулировать голосованием, но будет много коллизий.
Можно и переголосовать. Для этого делаем новый бюллетень B2 и новый ключ key2, посылаем агентству M, старый ключ key и зашифрованное с помощью нового ключа key2 {M, B2}_en2. С помощью секретного ключа key агентство расшифровывает предыдущее шифрованное сообщение, сравнивает метки. В случае совпадения меняет {M, B}_en на {M, B2}_en2. Потом, как увидим, что агентство поменяло, присылаем key2.

Пункты честного голосования.

Плюсы:

Чувствуете этот запах? Наконец-то выполняется пункт (3)
Ещё соблюдаются (1), (2), (4), (5), (6), (7), (9)

Минусы:

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

Протокол Фудзиока-Окамото-Ота

Здесь опять 3 действующих лица: голосующий, регистратор и счётчик. Сам протокол:

Голосующий генерирует ключи для асимметричного шифрования: E_pubKey, E_privKey.
Счётчик генерирует ключи: C_pubKey и C_privKey. Публичный ключ рассказывает всем.
Регистратор составляет списки:
1. Регистратор генерирует ключи: V_pubKey и V_privKey. Публичный ключ рассказывается всем.
2. Регистратор выкладывает списки потенциальных голосующих, тех кому можно голосовать.
3. Голосующие сообщают регистратору о желании голосовать. Приходят к регистратору и подтверждают личность. Там же регистрируют свой E_pubKey.
4. После этого Регистратор выкладывает списки тех, кто голосует.
Голосующий:
1. Генерирует ключ для симметричного шифрования: key.
2. Делает выбор в бюллетене B.
3. Шифрует бюллетень: B_en = encrypt(B, key).
4. Генерируется число r, и с его помощь скрывается содержимое бюллетеня B_en_bl = blind(B_en, r, V_pubKey).
5. Подписывает зашифрованный скрытый бюллетень: B_en_bl_sigE = sign(B_en_bl, E_privKey).
6. Отправляем регистратору B_en_bl_sigE и ещё заодно E_pubKey, чтобы регистратору было проще понять от кого сообщение.
Регистратор
1. Принимает сообщение, проверяет, что оно подписано легитимный голосующим (напомним, что голосующие указывали регистратору свои публичные ключи при регистрации): B_en_bl = sign(B_en_bl_sigE, E_pubKey).
2. После того как убедился, что голосующий легальный, подписывает вслепую: B_en_bl_sigV = sign(B_en_bl, V_privKey).
3. Отправляет B_en_bl_sigV голосующему.
Голосующий раскрывает бюллетень с помощью числа r: B_en_sigV = unblind(B_en_bl_sigV, r). Вот так регистратор подписал наш бюллетень, не заглядывая туда. Теперь проверить подпись регистратора может любой, в том числе и счётчик. Осталось только ему это отослать.
Счётчик:
1. Проверяет, что B_en_sigV действительно подписан регистратором: B_en = unsign(B_en_sigV, V_pubKey).
2. Помещает B_en в специальный список в открытом доступе после оговоренного времени.
Голосующий, как увидят, что списки опубликованы, действуют дальше. Находят в этом списке номер их B_en, и отсылают счётчику этот номер и key.
Счётчик расшифровывает и подсчитывает результаты.

Пункты честного голосования.

Плюсы:

Выполняются пункты (1), (2), (3), (4), (5), (6), (7)

Минусы:

Мы не знаем кто голосовал. Кто допущен к голосованию - да, а вот кто голосовал - нет. Минус (8)
С переголосованием тут всё сложно. Во-первых, нужно модифицировать протокол. Во-вторых, придётся раскрыть личность. Это нужно, чтобы исключить повторное голосование избирателем. Второй то раз регистратор не подпишет уже бюллетень. Нужно будет показать ему ключ. Далее он расскажет счётчику, чтобы предыдущий голос аннулировали. Короче, (9) не выполняется.

Давайте, рассмотрим ещё один протокол.

Протокол He-Su

Тут как раньше, но подписывается вслепую не бюллетень, а публичный ключ избирателя:

Регистратор генерирует ключи: V_pubKey и V_privKey. Публичный ключ рассказывается всем.
Голосующий:
1. Генерирует ключи для асимметричного шифрования: E_pubKey, E_privKey.
2. Скрывает с помощью числа r публичный ключ: E_pubKey_bl = encrypt(E_pubKey, r, V_pubKey).
Счётчик генерирует ключи: C_pubKey и C_privKey. Публичный ключ рассказывает всем.
Регистратор составляет списки:
1. Регистратор выкладывает списки потенциальных голосующих, тех кому можно голосовать.
2. Голосующие сообщают регистратору о желании голосовать. Приходят к регистратору и подтверждают личность. Там же Регистратор подписывает скрытый ключ: E_pubKey_bl_sigV = sign(E_pubKey_bl, V_privKey).
3. После этого Регистратор выкладывает списки тех, кто голосует.
Голосующий:
1. Раскрывает с помощью r подписанный регистратором ключ: E_pubKey_sigV = unblind(E_pubKey_bl_sigV, r). Всё, публичный ключ подписан самим регистратором. Теперь это ключ легитимного голосующего, это может проверить каждый: E_pubKey = unsign(E_pubKey_sigV, V_pubKey). Сам регистратор не знает кому какой ключ подписал. То есть ключ легитимный, а вот чей не сказать.
2. Анонимно отправляет E_pubKey_sigV счётчику.
Счётчик:
1. Проверяет, что ключ действительно подписан регистратором: E_pubKey = unsign(E_pubKey_sigV, V_pubKey).
2. Добавляет ключ E_pubKey_sigV в открытый список авторизированных ключей.
Голосующий:
1. Генерирует ключ для симметричного шифрования key.
2. Делает выбор в бюллетене B.
3. Шифрует бюллетень: B_en = encrypt(B, key).
4. Подписывает: B_en_sigE = sign(B_en, E_pubKey).
5. Отправляет анонимно счётчику B_en_sigE и E_pubKey_sigV.
Счётчик:
1. Проверяет, что E_pubKey_sigV есть в публичном списке авторизированных ключей. Получает E_pubKey = unsign(E_pubKey_sigV, V_pubKey).
2. Проверяет авторизованность ключа: B_en = unsign(B_en_sigE, E_pubKey).
3. Публикует B_en.
Голосующий:
1. Видит, что B_en опубликовано.
2. Подписывает ключ: key_sigE = sign(key, E_privKey).
3. Отсылает анонимно счётчику key_sigE и E_pubKey_sigV.
Счётчик:
1. Проверяет, что E_pubKey_sigV есть в публичном списке авторизированных ключей. Получает E_pubKey = unsign(E_pubKey_sigV, V_pubKey).
2. Проверяет подпись ключа: key = unsign(key_sigE, E_pubKey).
3. Дешифрует бюллетень: B = decrypt(B_en, key).
4. Публикует B.
5. Подсчитывает результат.

Пункты честного голосования.

Плюсы:

Выполняются пункты (1), (2), (3), (4), (5), (6), (7)
Можно переголосовать. Надо просто прислать другой бюллетень, подписанный авторизированным ключом. Выполняется (9).

Минусы:

Снова не знаем кто голосовал. Минус (8).
Тут продать голос проще всего. Нужно лишь продать подписанный ключ E_pubKey_sigV.

Подведём небольшой итог

Почти всё выполняется, но по-прежнему есть возможность продажа голосов. Ещё так и не получилось избежать “мёртвых душ”. Противостоять этому можно публикацией списка проголосовавших (свойство (8)). Но как раз (8) и не выполняется.

Сравним пока что, что есть:

Свойство	Традиционный	Простейший	Простой	Два агентства	ANDOS	Фудзиока-Окамото-Ота	He-Su
(`1`)	+	-	+	+	+	+	+
(`2`)	+	-	+	+	+	+	+
(`3`)	+/-	+	-	-	+	+	+
(`4`)	-	-	+	+	+	+	+
(`5`)	-	-	-	+	+	+	+
(`6`)	-	-	-	+	+	+	+
(`7`)	-	-	-	+	+	+	+
(`8`)	+/-	-	-	+/-	-	-	-
(`9`)	-	-	+	+	+	-	+

Какая красота!

Последний штрих

Во-первых, знать кто проголосовал, а кто – нет, это один из самых важных пунктов. А он не выполняется. Хотелось бы хоть как-то исправить ситуацию.

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

В-третьих, мёртвые души. Регистратор – это горлышко от бутылки. Нам нужно доверять ему, что не будет лишних. В любом случае список всех тех, кому можно голосовать, публикуется, и можно, в теории, убедиться, что это реальные люди. Также см. эту часть.

Пораскинув мыслишками, можно придумать такой протокол, который бы отвечал всем требованиям (на наш взгляд). Сделаем гибрид всего того, что было до этого и ещё добавим от себя:

Счётчик генерирует ключи: C_pubKey и C_privKey. Публичный ключ рассказывает всем.
Регистратор составляет списки:
1. Регистратор генерирует ключи: V_pubKey и V_privKey. Публичный ключ рассказывается всем.
2. Регистратор выкладывает списки потенциальных голосующих, тех кому можно голосовать.
3. Голосующие сообщают регистратору о желании голосовать. Приходят к регистратору и подтверждают личность.
4. Регистратор подписывает имя голосующего name: name_sigV = sign(name, V_privKey). Отдаёт голосующему name_sigV.
5. После этого регистратор выкладывает списки тех, кто голосует.
Голосующий:
1. Генерирует себе метку M.
2. Скрывает её с помощью числа r: M_bl = blind(M, r, C_pubKey).
3. Генерирует ключ key для симметричного шифрования.
4. Шифрует name_sigV и метку: {name_sigV, M_bl}_en = encrypt({name_sigV, M_bl}, key)
5. Шифрует сообщение для отправки: {name_sigV, M_bl}_en_enC = encrypt({name_sigV, M_bl}_en, C_pubKey).
6. Отсылает анонимно счётчику {name_sigV, M_bl}_en_enC.
Счётчик:
1. Получает сообщение и дешифрует: {name_sigV, M_bl}_en = decrypt({name_sigV, M_bl}_en_enC, C_privKey).
2. Публикует {name_sigV, M_bl}_en в специальном списке.
Голосующий видит опубликованное {name_sigV, M_bl}_en и:
1. Шифрует ключ для отправки: key_enC = encrypt(key, C_pubKey).
2. Анонимно высылает key_enC.
Счётчик:
1. Дешифрует: key = decrypt(key_enC, C_privKey).
2. Дешифрует сообщение голосующего в открытом списке: {name_sigV, M_bl} = decrypt({name_sigV, M_bl}_en, key).
3. Проверяет подпись регистратора: name = unsign(name_sigV, V_pubKey).
4. Подписывает M_bl_sigC = sign(M_bl, C_privKey).
5. Публикует рядом с {name_sigV, M_bl}_en ещё и {M_bl_sigC, name_sigV}.
Голосующий:
1. Видит опубликованное {M_bl_sigC, name_sigV} и снимает закрывающее число r: M_sigC = unblind(M_bl_sigC, r). Проверяет правильность name_sigV.
2. Делает выбор в бюллетене B.
3. Генерирует ещё один (другой) ключ для симметричного шифрования key2.
4. Шифрует бюллетень B_en2 = encrypt(B, key2).
5. Генерирует ещё один ключ для симметричного шифрования keyCheck и шифрует: M_enCheck = encrypt(M, keyCheck).
6. Шифрует для отправки: {M_sigC, M_enCheck, B_en2}_enC = encrypt({M_sigC, M_enCheck, B_en2}, C_pubKey).
7. Генерирует число k.
8. Ждёт k сек. Сидит, пьёт чай и/или читает книгу.
9. Отсылает анонимно счётчику {M_sigC, M_enCheck, B_en2}_enC.
Счётчик:
1. Принимает сообщение и дешифрует: {M_sigC, M_enCheck, B_en2} = decrypt({M_sigC, M_enCheck, B_en2}_enC, C_privKey).
2. Проверяет свою подпись: M = unsign(M_sigC, C_privKey).
3. Публикует в специальном списке {M, M_enCheck, B_en2}.
Голосующий:
1. Видит опубликованное {M, M_enCheck, B_en2} и понимает, что время действовать дальше.
2. Шифрует для отправки: {M, key2}_enC = encrypt({M, key2}, C_pubKey).
3. Отправляет анонимно {M, key2}_enC счётчику.
Счётчик:
1. Принимает и дешифрует сообщение: {M, key2} = decrypt({M, key2}_enC, C_privKey).
2. Дешифрует бюллетень: B = decrypt(B_en2, key2).
3. Публикует рядом с {M, M_enCheck, B_en2} ещё и B.
4. Считает голоса и подводит итоги.

Дополнения:

В алгоритме для шифрования и подписи использовались одни и те же ключи. Так делать не рекомендуется. Здесь это сделано для упрощения усвоения алгоритма.
keyCheck нужен, чтобы потом мы могли доказать, что это сообщение отправили мы. По большей части это необходимо для повторного голосования, если совпадут метки M у разных голосующих (см. ниже). Вместо M можно с помощью этого ключа шифровать что угодно, главное, чтобы было с чем сравнить.
Забавно, что не понадобились публичные и приватные ключи голосующего. Хотя в теории они могут пригодиться. Каждый раз, когда счётчик публикует в специальном списке информацию “для голосующего”, то её можно шифровать публичным ключом избирателя. Тогда и избиратель должен всё время отсылать свой публичный ключ, когда он высылает анонимно сообщение счётчику. Проблема только в том, что нужно генерировать отдельно ключи для подачи списка имён и отдельно для подачи бюллетеня. Иначе не будет выполняться пункт (3).
Под name в шаге 2 имеется ввиду ФИО, год рождения, ID… Короче то, что может единственным образом идентифицировать человека. Или можно сказать строчка, соотносящаяся с голосующим, из списка тех, кто голосует. Причём должно быть написано, что используется “только для этого голосования”.
Шифрование {name_sigV, M_bl} в шаге 3 нужно для того, чтобы счётчик не знал до нужной поры, от кого принял сообщение. А то вдруг ему не хочется, чтобы Вася не голосовал. На шаге 4 {name_sigV, M_bl}_en публикуется и уже нельзя сказать, что сообщение не принимал.
На шаге 5 Голосующий отправляет вместе с key_enC счётчику ещё и номер своего {name_sigV, M_bl}_en в публичном специальном списке.
На шаге 7 ждать k секунд необходимо, чтобы нельзя было связать между собой список с именами и список с бюллетенями. Вот что имеется ввиду. Пусть Вася прислал своё name, получил подпись метки M_sigC, а потом сразу же отсылает свой голос {M_sigC, M_enCheck, B_en2}_enC. Очевидно, что бюллетень B_en2 прислал name, то есть Вася.
Теперь есть список тех, кто проголосовал. Между шагами 2 и 3 может пройти действительно много времени. Избиратель может просто забыть про голосование или ему станет лень, или вдруг мировоззрение поменяется, и он откажется голосовать, или просто никак (например, избиратель уехал на дачу). Поэтому тот список, который публикует регистратор не отражает число проголосовавших. А вот пункты 3 и 9 выполняются почти в одно время. Причём программой. Для голосования нужно какое-нибудь вычислительное устройство и интернет. В любом случае появляется возможность ещё ближе подойти к правильному кол-ву проголосовавших, ведь бюллетеней должно быть не больше, чем name. Плюс ко всему это ещё больше ограничивает счётчика.
Ждать k сек может оказаться действительно неудобно на первый взгляд. Но программа для голосования может работать в фоне после шага 7, как демон на GNU\Linux, или как сервис на Windows, или как фоновое приложение на Android. Сейчас такой мир, что на фоне работает много всяких приложений, хотим мы того или нет. Главное, чтобы они были с открытым исходным кодом. Приходится голосующим идти на компромисс, но зато списки проголосовавших будут очень близкими к действительности.
Голосующий на шаге 5 должен понимать, что если он в дальнейшем не проголосует, то за него в теории может проголосовать счётчик. Но возможна и такая ситуация. Например, 10 голосующих, они все выполнили 5-ый шаг. 9 уже проголосовало, а последний не голосует почему-то. Счётчик думает, что 10-ый вообще не собирается дальше участвовать, и голосует за него. Теперь все 10 голосов из 10-ти опубликованы. И тут просыпается тот самый 10-ый голосующий и ловит счётчика на лжи, показывая подписанную счётчиком метку M_sigC.
Опять-таки регистратора должны контролировать неравнодушные (а такие найдутся), которые будут следить за списком голосующих (чтобы не было “мёртвых душ”) и которые будут делать у себя копии этих публичных специальных списков. Как говорится: “Если что-то один раз попало в интернет, то остаётся там навсегда”.
Может сложиться такая ситуация, что метки M могут совпасть у разных избирателей. Маловероятно (если генерировать метки в большом диапазоне), но могут. Тогда:
- Счётчик выбирает одного из избирателей, у которых коллизия, и публикует рядом с {M, M_enCheck, B_en2} рандомно сгенерированную метку M2, которая ещё нигде не использовалась.
- Когда избиратель увидит это, он генерирует новый ключ keyCheck2, шифрует им M2_enCheck2 и присылает счётчику {M2, M2_enCheck2, keyCheck, B_en2}.
- Счётчик принимает сообщение и проверяет: M == decrypt(M_enCheck, keyCheck).
- Заменяет {M, M_enCheck, B_en2} на {M2, M2_enCheck2, B_en2}. Причём содержимое бюллетеня счётчик так и не узнал ещё. Содержимое раскроется, когда голосующий пришлёт key2.
Если нужно переголосовать:
- Напомним, что сейчас опубликовано {M, M_enCheck, B_en2} или {M, M_enCheck, B_en2} вместе с B
- Голосующий генерирует новый ключ key3 и делает новый бюллетень B2. Шифрует его B2_en3.
- Голосующий генерирует новый ключ keyCheck2, шифрует им M_enCheck2 и присылает счётчику {M, M_enCheck2, keyCheck, B2_en3}.
- Счётчик принимает сообщение и проверяет: M == decrypt(M_enCheck, keyCheck).
- Заменяет {M, M_enCheck, B_en2} на {M, M_enCheck2, B2_en3}. И, если рядом был прикреплён ещё и бюллетень B, то удаляет его.

Пункты честного голосования.

Плюсы:

Выполняются вообще все пункты. Даже (8). Хотя, конечно, может сложиться ситуация, когда он не на 100% будет отражать истину. Можно рядом с пунктом (8) поставить хотя бы +/-.

Минусы:

Возможно, алгоритм перемудрён, и можно сделать ещё лучше и проще.
Более уязвим к DoS-атакам.

Этот алгоритм как раз и будет реализовываться. Здесь можно найти саму программу и исходники.

Также, надеюсь, кто-нибудь дальше разовьёт идею с децентрализованным регистратором. Это наверняка можно сделать как-нибудь. Например, с помощью Blockchain.

Где это ещё может пригодиться?

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

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

Участники точно знали, что опубликовали их баллы правильно.
Результаты участников не должны знать посторонние наблюдатели. Это те, кто мониторит список, но не являются участниками. Или сами участники не должны знать результаты друг друга. То есть баллы публикуются, а кому какой балл принадлежит узнать нельзя.

Таких задач можно придумать много. Или можно добавлять какие-нибудь ещё требования. Например, такое: участники не могут посмотреть баллы других, пока не закончится соревнование. Или такое: участники должны знать имена всех тех, кто вообще принимает участие в соревновании.

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

Вот что имеется ввиду. Например, агентству нужны те, кто дальше всех кидает телефоны. Устраиваются соревнования по бросанию телефонов на дальность. Участники приходят к агентству, регистрируются и через какое-то время в объявленный день приходят на соревнование. Участники друг друга не знают. Конечно, они могут познакомиться, но это не критично в данной ситуации. Главное то, чтобы оценивающие правильно выставили количество метров броска, и чтобы они выставляли результаты “физическим” людям. Участники один за другим подходят к оценивающим, кидают телефон как можно дальше, а оценивающие считают метры броска, выставляют кол-во баллов и публикуют. Тот, кто только что бросил, делает что-то, чтобы результат был учтен верно. Все остальные участники тоже видели, на сколько метров он бросил телефон, и убедились, что результаты проставлены верно.

В итоге участники не знают кто бросил телефон, но знают, что такой участник действительно был, и что его результат засчитан правильно. Как-то это всё звучит неадекватно…

Алгоритм, который тут приведён наверняка можно сделать лучше, на его придумывание почти совсем не было времени. Но тем не менее вот он:

Участник создаёт публичный P_pubKey и приватный P_privKey ключи.
Оценивающий создаёт публичный E_pubKey и приватный E_privKey ключи. Публичный рассказывается всем.
Участники сообщают агентству о желании участвовать, заодно регистрируют там свой P_pubKey. Приходят, например, с паспортом в агентство и показывают свой публичный ключ. То есть теперь агентство знает кому какой ключ принадлежит.
Агентство приходит к оценивающему и просит провести соревнование. Здесь же агентство ему передаёт все публичные ключи людей, которые участвуют в соревновании.
Участник приходит на соревнование, показывает свой публичный ключ P_pubKey оценивающему, выполняет что-то и получает за это балл b, который выставляет оценивающий.
Оценивающий подписывает этот балл b_sigE = sign(b, E_privKey) и публикует в открытом списке {P_pubKey, b_sigE}. Проверить подпись могут все: b = unsign(b_sigE, E_pubKey).
Участник подписывает балл b_sigP = sign(b, P_privKey), если согласен с результатами. Показывает b_sigP оценивающему.
Оценивающий проверяет подпись b = unsign(b_sigP, P_pubKey) и подписывает b_sigP_sigE = sign(b_sigP, E_privKey). Рядом с {P_pubKey, b_sigE} публикует ещё и b_sigP_sigE.
Агентство сортирует список по баллам, смотрит лучших, и связывается с ними, так как оно знает кому какой ключ принадлежит.

Примечания:

Оценивающим и агентством может быть одна и та же сущность.
b может представлять из себя не только балл, а ещё заметку о том, кому именно он поставлен (какому ключу). Например, участник с публичным ключом HW25KAj6L3j6a получил 57 баллов, тогда b = HW25KAj6L3j6a:57. Это хорошо тем, что теперь все подписи оценивающего b_sigE будут разные. Также теперь проверить подпись участника будет проще, не нужно искать его ключ агентству в шаге 9, он уже записан в b.
В шаге 5 показать оценивающему публичный ключ нужно для того, чтобы подтвердить, что участник соревнования легитимный.
В шаге 6 другие участники соревнования увидят опубликованный балл и сравнят с тем, что они насчитали.
В шаге 7 участник подписывает свои баллы, как знак того, что балл выставлен правильно. Агентство же потом на шаге 9 может проверить подписи участников.
В шаге 8 участник увидит, что b_sigP_sigE в открытом доступе. Значит, его результаты засчитаны.
Шаг 9 может провести кто угодно (имеется ввиду отсортировать список). Таким образом участник может узнать на каком он месте в соревновании.
Вся эта процедура (подпись, проверка подписи, показ публичного ключа) может проводиться с помощью программы на каком-нибудь портативном устройстве.
Опять-таки нужно кому-то доверять. Оценивающего, например, участники не всегда могут контролировать, наблюдая со стороны. Может сложиться такая ситуация, что к оценивающему придёт сын маминой подруги и получит куча баллов.
Главная проблема: участник может подкупить кого-нибудь, кто может получить много баллов, чтобы тот выступил за него.

Приложение

Уже после написания нашлось ещё кое-что.

Модифицированный протокол Фудзиока-Окамото-Охта

Изначальный протокол не очень-то удобный. Чуть изменим:

Голосующий генерирует ключи для асимметричного шифрования: E_pubKey, E_privKey.
Счётчик генерирует ключи: C_pubKey и C_privKey. Публичный ключ рассказывает всем.
Регистратор составляет списки:
1. Регистратор генерирует ключи: V_pubKey и V_privKey. Публичный ключ рассказывается всем.
2. Регистратор выкладывает списки потенциальных голосующих, тех кому можно голосовать.
3. Голосующие сообщают регистратору о желании голосовать. Приходят к регистратору и подтверждают личность. Там же регистрируют свой E_pubKey.
4. После этого регистратор выкладывает списки тех, кто голосует.
Голосующий:
1. Генерирует ключ для симметричного шифрования: key.
2. Делает выбор в бюллетене B.
3. Шифрует бюллетень: B_en = encrypt(B, key).
4. Генерируется число r, и с его помощь скрывается содержимое бюллетеня B_en_bl = encrypt(B_en, r, V_pubKey).
5. Подписывает зашифрованный скрытый бюллетень: B_en_bl_sigE = sign(B_en_bl, E_privKey).
6. Шифруем сообщение для того, чтобы отправить регистратору: B_en_bl_sigE_enV = encrypt(B_en_bl_sigE, V_pubKey).
7. Отправляем регистратору B_en_bl_sigE_enV и ещё заодно E_pubKey, чтобы регистратору было проще понять от кого сообщение.
Регистратор
1. Принимает сообщение от голосующего и дешифрует: B_en_bl_sigE = decrypt(B_en_bl_sigE_enV, V_privKey).
2. Проверяет, что оно подписано легитимный голосующим (напомним, что голосующие указывали регистратору свои публичные ключи при регистрации): B_en_bl = sign(B_en_bl_sigE, E_pubKey).
3. После того как убедился, что голосующий легальный, подписывает вслепую: B_en_bl_sigV = sign(B_en_bl, V_privKey).
4. Шифрует сообщение для того, чтобы отправить обратно голосующему: B_en_bl_sigV_enE = encrypt(B_en_bl_sigV, E_pubKey).
5. Отправляет B_en_bl_sigV_enE голосующему.
Голосующий:
1. Принимает и дешифрует сообщение: B_en_bl_sigV = decrypt(B_en_bl_sigV_enE, E_privKey).
2. Раскрывает бюллетень с помощью числа r: B_en_sigV = unblind(B_en_bl_sigV, r).
3. Генерируем себе метку M.
4. Шифруем сообщение для счётчика: {M, B_en_sigV}_enC = encrypt({M, B_en_sigV}, C_pubKey).
5. Анонимно отсылает счётчику {M, B_en_sigV}_enC.
Счётчик:
1. Дешифрует сообщение: {M, B_en_sigV} = decrypt({M, B_en_sigV}_enC, C_privKey).
2. Проверяет подпись регистратора: B_en == unsign(B_en_sigV, V_pubKey).
3. Публикует M и B_en_sigV.
Голосующий, когда увидит, что M и B_en_sigV опубликованы:
1. Шифрует свой ключ: key_enC = encrypt(key, C_pubKey).
2. Анонимно высылает счётчику key_enC.
Счётчик:
1. Дешифрует сообщение: key = decrypt(key_enC, C_privKey).
2. Расшифровывает бюллетень: B == decrypt(B_en, key).
3. В дополнение к {M, B_en_sigV} публикует {M, B}
Счётчик считает и подводит итоги.