Thursday, September 12, 2013

Навально-технологическое

Это не про политику, это про технологию. Пока Алексей Навальный готовит грузовики бумаги для доказательства мухлежа на Московских выборах, а Борис Шнайер всем рекомендует забраться под ТОР для защиты от NSA, я гляжу на это дело в древнерусской тоске. И думается мне вот что.

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

Наше волеизъявление - это перфоманс. За пару месяцев "до" во всех СМИ начинают отсвечивать разного рода личности. Они пыжатся, поливают друг друга помоями, мобилизуют, врут, собирают компроматы. Потом - мы голосуем. И эти личности уходят в свободное плавание, рукою твердою направляя нашу отчизну по нужному им азимуту. А мы пассивно рефлексируем - вот же мрази, что творят! До следующих выборов.

А есть ли альтернативы? Я не про поросенка Петра и трактор, я про математику. Можно ли изменить протокол волеизъявления так, чтобы граждане имели контроль над процессом? Чтобы ЦИК, к примеру, не считал голоса?


Чтобы окончательно отвлечься от политики предлагаю такую постановку задачи:
На острове Р. власть захватили уголовники и сформировали партии - Жулики, Воры, Карманники, Проститутки, Наркоторговцы и т.д. Для простоты обозначим их N1...Nk. В стране так же есть и честные граждане, которых пока большинство, и они представлены партиями G1..Gm. К сожалению ни кто ни кому не доверяет, потому что все гос. органы состоят из членов этих самых N-партий. Требуется разработать такой протокол голосования, при котором народ многострадального острова сможет управлять своей отчизной, например предотвратить войну с соседним островом, которую жулики хотят развязать, чтобы ввести военное положение.
Для начала попробуем решить классическую задачу, в которой мы выбираем, например, кабинет министров. Нам нужно выбрать x министров из x+y кандидатов. Для простоты будем считать что от каждой партии выставляется один претендент и x+y = m+k. В зависимости от того, сколько кандадатов из N-партий будет в числе x выбранных министров, кабинет может оказаться "честным" или "уголовным". Если просто голосовать по-честному, то люди выберут m кандидатов из G-партий и остаток из N-партий, т.е. урки проиграют. Поэтому последним надо мухлевать чтобы удержать власть.

Типовые варианты мухлежа

У N-партиий есть несколько вариантов атаки на выборы:

  • Неверный подсчет голосов. Неважно как вы проголосовали, мы в отчет напишем то, что хотим.
  • Вброс голосов за своих кандидатов. Предполагает опциональное изъятие части голосов и замена изъятых бюллетеней на свои.
  • Манипуляции с явкой.
    • "Потертять" голоса пришедших избирателей проголосовавших за другого кандидата.
    • Добавить "мертвые души" - несуществующих избирателей голосующих за урок.
    • Химичить с разделением на округи. Например, мы знаем, что в городе всего 1 миллион человек которые могут прийти на выборы, но на севере живет 400 тыс. жуликов. Если голосовать честно, но надо замотать 100 тыс. голосов. Но если поделить город на три округа - южный, северо-восточный и северо-западный, то в южном округе победят G-партии, а в юго-восточном и юго-западном - N-партии. Итоговое соотношение по округам будет 2:1 в пользу N-партий. Заметим, что мы говорим о учтенных пришедших избирателях, а не о проживающих людях. Так что умело используя демографию можно поделить город на равные части с перевесом в нужную сторону.
  • Подкуп избирателей. Нужно запугать или подкупить часть граждан, чтобы они проголосовали за нужных кандидатов.
  • Обвинение конкуррентов в махинациях с голосами. Можно при проигрыше признать выборы нелегитимными из-за нарушений которых небыло.
Очевидно наш протокол должен защищать от этих атак. Давайте рассмотрим их подробнее.

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

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

Атака "потеря голосов" использует тот факт, что контроль целостности очуществляется жуликами. Значит у нас и контроль за целостностью должен быть распределенным.

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

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

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

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

Какое-нибудь решение

Тут конечно простор для анализа, но вот простенькое решение. Пусть у нас есть избирательная комиссия (ИК), которая тоже состоит из жуликов. Тем не менее в этой комиссии стоит некоторая БД в которой мы будем копить результаты и которые потом будем "официально" анализировать. Так же мы примем наличие "официальной" CA которая будет обеспечивать легитимность электронных подписей ИК.
  1. Для начала ИК генерирует уникальный номер бюллетеня (последовательность бит фиксированной длины) и заносит его себе в базу. При этом он подписывает номер и отдает его всем партиям и избирателю, тем самым подтверждая что он его таки выдал.
  2. Партии тоже подписывают этот номер своими ЭП, дескать да, был такой бюллетень. Этими двумя шагами мы боремся со вбросами. Чтобы теперь сфабриковать бюллетень нужно не просто подписать его от ИК-а, но и подделать подписи всех партий.
    1. Вообще партии могут добавлять свои последовательности к номеру бюллетеня Н, и таким образом вставить свои шифропоследовательности в номер, если они не доверяют алгоритму ЭП и не доверяют ИК-у с генерацией номеров без коллизий. Ну это уже рюшки.
  3. Теперь на сцену выходит избиратель. Избиратель готовит последовательность Г и разовый секретный ключ. После этого избиратель:
    1. Дописывает Г к номеру бюллетеня Н и шифрует полученное на своем ключе. Получает П0.
    2. Выбирает какую-то партию и просит ее зашифровать и подписать шифротекст, получает шифротекст П1. Партия использует разовый ключ.
    3. Просит эту партию сказать ключ на котором она шифровала П1, расшифровывает и убеждается в том, что действительно обратное преобразование дает Г+Н.
    4. Затем опять добавляет Г к П1 и шифрует все вместе на Настоящем ключе, получает шифротекст П2.
    5. Снова выбирает другую партию и просит обработать П2 и так далее. Получается совоеобразная матрешка из шфиротекстов "переложенная" добавлением Г,  шифроманием на ключе избирателя и подписыванием шифротекста партией. На стороне избирателя, при этом, сосредоточился пакет из разовых ключей + Г + его секретный ключ.
    6. Наконец избиратель публикует полученную "матрешку" из шифротекстов и последовательность Г, а каждой из партий отдает ключ. 
    7. Как вы уже догадались, та партия, которой он доверяет получает настоящий ключ, а все остальные - фальшивый.
  4. Когда приходит пора посчитать голоса, все партии предоставляют номера бюллетеней и разовые ключи избирателей. Та партия, которая сможет "развернуть" матрешку не нарушив целостность подписей и продемонстрировать Г , Н, а главное целостность всех подписей в конце засчитывает себе голос. Остальные - обламываются.
    1. Кстати, считать голоса можно так. Сначала публикуются m+k -е ключи, в ответ партии предоставляют Пm+k -е шифротексты, потом m+k-1 -е ключи и т.д.
99.(9):1 что это дырявый велосипед, и тут наверняка можно все упростить и улучшить, избежать такого количества разовых ключей, а до кучи еще и исключить ИК. На это есть люди поумнее меня. А пока давайте прорезюмируем:
  • Чтобы "развернуть" матрешку и продемонстрировать целостность подписей надо собрать все ключи. Это происходит только в конце голосования при подсчете голосов. До этого момента жулики не поймут кто за что голосовал. Даже после этого связать конкретный голос с человеком довольно трудно без участия ИК.
  • Чтобы засчитать себе голос партия должна доказать что он ей принадлежит. Математически. Т. е. изначально есть только факт доверия между избирателем и той партией, за которую он голосует, все остальные друг другу не верят.
  • У нас нет необходимости всем использовать одинаковый алгоритм ЭП и одинаковый алгоритм шифрования. Разные партии могут использовать разные криптосредства.
  • Наконец в голосовании могут участвовать контроллирующие органы - т.е. "партии" за которые нельзя голосовать, но которые участвуют в протоколе. Это могут быть как общественные, так и международные организации.

Ну и как там с атаками?

А давайте посмотрим решили ли мы типовые атаки:
  • Неверный подсчет голосов. ИК не считает голоса, а проверяет их. Партии считают голоса независимо друг от друга. Если получается расхождение, сначала проверяем по номерам бюллетеня, потом проверяем "разворачивание" матрешки по несовпавшим бюллетеням. У кого-то обязательно будет ошибка, т.е. голос засчитается только одной партии. Если вдруг голос засчитался двум, значит имела место утечка и голос считается "испорченым". Кстати сказать, "поломать" голоса довольно сложно - мало того, что нужно увести секреты, так еще и ключи всех партий.
  • Вброс за своих кандидатов. Эта атака по сути сводится к предыдущей. Жулики должны как-то изготовить фальшивые голоса. Для этого им прийдется подделать ЭП других партий. Помимо этого, нужно что-то делать с их собственными ЭП которые стоят на "настоящих" бюллетенях. Это еще сложнее, потому как их проверяет на этапе подписания избиратель. И забывать про уникальные номера бюллетеней не стоит. Наличие "неучтенки" у группы партий однозначно свидетельствует о вбросе.
  • Потеря голосов. Если даже ИК потеряет все бюллетени, доказательность голоса от этого не пострадает. Как я уже говорил из схемы его вообще наверное можно выкусить.
  • Разделение на округи. Доказательность для каждого голоса в отдельности, считаются все голоса одновременно.
  • Подкуп избирателей. Жулики не могут проверить за кого голосовал избиратель до самой проверки голосов. А потом? Потом им надо подтянуть "первичные данные" из ИК и связать бюллетени с конкретными личностями. Это одна из причин почему в этой схеме ИК все-таки нужен. Должен же кто-то паспорта проверять... В жуликам прийдется верить избирателю "на слово".
  • Обвинение конкуррентов. Опять же доказательность голоса. Изготовить фальшивый бюллетень очень сложно, к тому же есть ваши подписи на как минимум одном промежуточном этапе. Наличие контроллирующих участников так же помогает.
Неужели отстрелялись? Наверняка умные люди скажут свое веское "фе", но, я думаю, и предложат какие-то альтернативы. Так что надежда все же есть.

Хотите еще?

А теперь давайте подумаем как такая возможность может изменить политический ландшафт. Ну во-первых мы не обязаны теперь производить выборы раз в два-четыре-десять лет. Серьезно. Если реализовать протокол на основе устройства вроде банкомата "изъявлять свою волю" гражданин может хоть по десяти раз на дню.

Тогда можно реализовать такой вариант отношений с государством:
  • Время от времени, когда мне удобно, я иду к "избирательному банкомату" и доверяю право использовать мой голос конкретным партии или ее представителю.
  • При этом я могу ограничить действие этого голоса конкретной областью деятельности, рассматриваемыми вопросами, временем и т.д.
  • Когда партии голосуют за закон или решение они "складываются" своими голосами и доказывают, что обладают самым последним мандатом для конкретного гражданина. Т.е. они доказывают две вещи:
    • У меня есть право использовать его голос по данному вопросу и
    • Ни у кого нет более позднего бюллетеня с правом использовать этот голос
Клево, да? Сижу я, смотрю по телеку очередного деятеля, за которого я голосовал, и он тут заявляет "а мы внесли законопроект и поднимаем налоги в два раза!". Ну тут я встаю и иду к голосовальному банкомату, и отдаю голос кому-то другому. Это своеобразная "волатильность" электората, возможность быстро менять мнение и реагировать на него.

Что нам в этом? 
  • Ну во-первых мнение электората становится более важным. Т.е. мы можем надеяться на внимание кандидатов между выборами.
  • Во вторых - упомянутая выше волатильность. Как следствие избиратель может быть более активным, потому что от него что-то зависит.
  • В-третьих - у политиков есть возможность держать руку на пульсе и ориентироваться на рельную поддержку электората, а не на соц. опросы.
  • Конец "торговли местами". У республиканцев столько-то мест, у демократов - столько-то... Какая разница, все равно голосовать они могут только количеством голосов, которые им доверены. Поэтому подмазывать конкретного политика смысла нет.
  • Наконец это персональная ответственность каждого избирателя за политику своей страны. Теперь нельзя будет сказать "я тут не при чем, это все Кремль, Вашингтон и т.д.". У вас есть один конкретный голос и он чего-то значит.

Неужели это возможно?

Да! Все, что нужно - уже есть. Есть и телекоммуникации, и удостоверяющие центры федерального значения, и технические возможности на местах. Такая система может быть разработана, кстати, открыто, усилиями open source community и поддерживаться международным комитетом мэйнтейнеров. А самое классное? Такую систему не надо внедрять повсеместно. Правда. Можно начать с одного города, или ТСЖ, или кружка любителей опоссумов. Законодательная база пока не достаточна для проведения легитимных выборов по такой схеме, но любое сообщество может внутри себя договориться "доверять" такому протоколу или упрощенной его версии. Даже профинансироваться можно через кикстартер. Так почему бы и нет?

Действительно, почему? Может заняться?

5 comments:

  1. Я не понял про подписывание бюллетеня — Каждая партия в итоге имеет список всех бюллетеней, подписанных всеми партиями?

    ReplyDelete
    Replies
    1. Да, и ИК тоже. С этого собственно все начинается. Для того, чтобы избератель мог разговаривать с партиями он должен доказать что может принимать участие в голосовании. Номер бюллетеня за подписью ИК и всех остальных партий собственно это и доказывает.

      Delete
  2. Всем спасибо за критику. Услилями сообщества нашли некоторые дыры, в частности:
    * В текущей схеме если партия или наблюдатель хочет сорвать выборы достаточно "потерять" свои ключи или предоставить неправильные на момент подсчета голосов. Да, у пользователей они есть, но им тяжело будет их собрать вместе.
    * Партия может легко проверить проголосовал ли за нее конкретный кандидат или нет до подсчета голосов. Достаточно проверить последний раунд обмена. Если тот ключ, который избиратель вам дал позволяет восстановить шифротекст с чьей-либо подписью, то ключ верный и значит избиратель выбрал вас. Иначе - нет.
    * Возникает вопрос с использованием устройств для голосования. Атаковать имеет смысл именно их, не углубляясь в криптографию. Если же разрешить пользователю выяснять за кого он проголосовал - это нарушение конфиденциальности.

    Так же мне совершенно справедливо порекоммендовали не изобретать велосипедов а посмотреть на существующие алгоритмы групповой подписи.

    Сути дела это не меняет, но идею надо забрать на доработку...

    ReplyDelete
    Replies
    1. Вот еще статья на тему - с более "классической" постановкой.

      http://habrahabr.ru/post/214023/

      Delete
  3. Отличная идея. Как только появились "биткоины" мне она пришла самому. Зачем городить весь огород, можно сделать через биткоин. Есть как кажется два основных пути в первом государство "помогает": по списку избираетелей генерируется пара приватны-публичный ключ, все приватные ключи раздаются избирателям а приватные шьются в программу. В программу заранее вбиты дата выборов, кандидаты. Потом люди голосуют своими приватными ключами. Кто не хочет - по старинке, "не ту кнопку нажал" - "заяву" и исправление. Но, хочется организовать выборы без участия государства - тогда всё становится намного сложнее. Например, пишете в программе: "я такой-то такой-то, проживаю здесь" если вам лайкнули сколько-то раз то выдаётся "право голоса"... не знаю как по другому решить задачу: "в государстве есть N людей никто не хочет выдавать свою личную информацию при этом все должны проголосовать и быть подсчитаны".
    И уже совсем фантастической, выглядит идея - "а почему бы вообще не разогнать всех этих чиновников?". Например - налоги зачисляются на ваш счёт но потратить вы их не можете - но можете - создать проект "ремонт дороги" вдруг ваш проект "залайкали", скинулись деньгами выбрали подрядчика(тоже по лайкам) и отремонтировали. что-то в таком духе... Идея примерно в том что - человек это как клетка в многоклеточном организме, например в вас. Возьмите уколите палец иголкой, что вы почувствуете? Да, ваша клетка на пальце просит вас этого не делать, причём убедительно, при достаточно большой иголке. Это демократия - когда каждый имеет право голоса и может быть услышан. Старый способ управления государством подразумевал, что - "людей много" и для мобильности, люди выбирают представителя "депутата" и он их представляет. Но с появлением интернета это возможно устарело и теперь каждый человек может себя представлять. Осталось только написать правильную софтину и главное P2P, потому что любая централизация это очень плохо.

    ReplyDelete