Демократия – это не голосование, это подсчёт голосов.
Том Стоппард
Для исследователей криптографии электронное голосование в первую очередь связано не с машиной для голосования и не с онлайн-голосованием – это просто поле для математических исследований. Исследование электронного голосования занимается созданием протоколов, ключевых математических компонентов, защищённых и проверяемых систем голосования, или таких систем, в которых независимые аудиторы и избиратели могут безопасно проверить правильность подсчёта голосов. Эти системы представляют собой не простые теоретические работы, но уже реальные технологии, использовавшиеся для реальных выборов: в городе Такома-Парк штата Мэриленд избиратели доверились системе Scantegrity II, основанной на бумажных бюллетенях с невидимыми чернилами, а сами криптографы использовали системы для онлайн-голосования Helios для избрания руководства.
Электронное голосование – тема сверхсложная, поэтому в данной статье я ограничусь ключевыми понятиями: что означает безопасная проверка голоса, как можно подсчитать голоса, не обращаясь к каждому по отдельности, и что не даёт избирателям жульничать. Я не буду давать вам полное описание всего протокола электронного голосования со всеми его нюансами, но желающие могут самостоятельно поискать работы на эту тему, коих достаточно много.
Безопасное подтверждение
Чего следует ожидать от системы безопасного голосования?
Первое, и самое очевидное: нужно проверить, что бюллетени подсчитаны правильно, то есть, чтобы каждый мог подтвердить, что итоговый подсчёт выполнен в соответствии с количеством бюллетеней, заполненных избирателями. Проверка не должна выдавать никакой дополнительной информации, кроме итоговых чисел. В частности, у проверяющего не должно быть возможности догадаться, кто как голосовал. Это эквивалентно классическому подсчёту бумажных бюллетеней вручную.
Во-вторых, нужно, чтобы любой избиратель мог удостовериться, что его голос подсчитали, и подсчитали правильно. Это нужно уметь сделать без раскрытия его голоса, а в более общем случае, избиратель не должен иметь возможности доказать, за кого он голосовал. Это делается для исключения принуждений, и для того, чтобы дать возможность избирателям свободно выбирать кандидата, не боясь последствий своего выбора.
Наконец, система голосования должна быть защищённой против подлогов: избиратель не должен иметь возможности голосовать более одного раза, и не должно быть возможности изменять или копировать бюллетень. Кроме того, иметь возможность голосовать должны только зарегистрированные избиратели.
Итак, подытожим: нам нужна публичная проверяемость, уверенность избирателей, сопротивляемость принуждению и целостность избирания. Эти принципы были выдвинуты в основополагающем исследовании за авторством Чаума, Неффа и других, вышедшем в начале 2000-х.
Основные принципы
Большинство классических протоколов электронного голосования работают следующим образом:
- Избиратель получает токен в виде бюллетеня, который изменяет соответственно своему выбору. Разные избиратели получают разные бюллетени.
- Избиратель шифрует бюллетень (используя особый тип шифрования, позволяющий работать магии электронного голосования, и отправляет его так, чтобы организаторы голосования получили зашифрованный бюллетень.
- Организаторы публикуют зашифрованные бюллетени на доске объявлений, «публичном широковещательном канале с памятью», на жаргоне криптографов – говоря проще, на чём-то вроде Pastebin.
- Организаторы комбинируют зашифрованные бюллетени для подсчёта зашированного итога. Затем они расшифровывают его (но не сами бюллетени!) и публикуют результаты.
- Получив результат и зашифрованные голоса, любой может проверить его корректность.
Безопасный подсчёт: гомоморфное шифрование
На 4-м шаге организаторы комбинируют криптограммы для создания новой криптограммы, шифрующей сумму отдельных голосов. Для этого схемы электронного голосования используют схему шифрования Enc(), в которой можно подсчитать Enc(v1 + v2), имея на руках только Enc(v1) и Enc(v2), и не зная ключа шифрования. Такие схемы шифрования называются гомоморфными.
К примеру, если сильно упростить, избиратели США производят следующие действия 8 ноября:
- Получают от организаторов бюллетень «Клинтон» и бюллетень «Трамп» (для простоты рассмотрим всего двух кандидатов).
- Пишут на одном бюллетене Enc(1), а на другом – Enc(0), используя в качестве ключа публичный ключ, выданный организаторами.
Зашифрованные бюллетени затем публикуются на доске объявлений вместе с ID избирателя. Все знаю, кто проголосовал, но невозможно понять, за кого именно, поскольку каждые Enc(0) и Enc(1) уникальны, а мы используем сильное и рандомизированное шифрование. Если бы шифрование было детерминистское, избирателя можно было бы заставить раскрыть его голос, вычислив Enc(0) заново и сравнив его со значением на доске.
Наконец, организаторы комбинируют все бюллетени за «Клинтон» и получают результат Enc(количество голосов за Клинтон), а потом то же делают с бюллетенями за «Трампа» и получают Enc(количество голосов за Трампа). Затем они берут ключ расшифровки и расшифровывают два этих значения, объявляя победителя.
А как найти гомоморфную схему шифрования? Довольно легко – такие схемы, как RSA и ElGamal, гомоморфны в своих базовых вариантах, поскольку удовлетворяют уравнению
Enc(v1) ? Enc(v2) = Enc(v1 ? v2)
Но это не совсем то, что нам надо – это мультипликативный гомоморфизм, а нам нужен аддитивный. Существуют трюки, превращающие схемы RSA и ElGamal в аддитивно гомоморфные, но вместо этого я покажу менее известную схему, которая сразу же аддитивно гомоморфна: криптосистема Пэйе, шифрующая сообщение v1 до
Enc(v1) = g v1 r1 n mod n2
Где n = pq и g – фиксированы, а r1 – случайное целое число из ]1; n2 [. Следовательно, мы имеем:
Enc(v1) ? Enc(v2) = (g v1 r1 n) ? (g v2 r2 n) mod n2 = g v1+v2 (r1r2) n mod n2 = Enc(v1 + v2)
То есть, схему Пэйе можно использовать для подсчёта зашифрованных голосов.
Предотвращаем мошенничество: доказательство с нулевым разглашением
Чтобы сжульничать, избиратель может захотеть написать в бюллетене Enc(10000) вместо Enc(1), чтобы добавить кандидату голосов. В случае недобрых намерений можно написать Enc(очень_большое_число), чтобы это привело к переполнению целого и к отказу всей системы. Как же гарантировать допустимость голоса (0 или 1) без дешифровки?
Решением будет не интерактивное нулевое разглашение (НИНР) [non-interactive zero-knowledge, NIZK]. Доказательство НИНР – весьма сложный и чрезвычайно мощный криптографический объект: в нашем случае он позволит избирателю доказать, что их криптограмма содержит 0 или 1, но при этом не показывая само зашифрованное сообщение. В общем случае НИНР-доказательства позволяют доказывающему убедить проверяющего в истинности утверждения, отправляя ему только набор данных без каких-то других видов взаимодействия.
Возможно, простейшая система с нулевым разглашением, это схема Шнорра: допустим, вы знаете решение задачи дискретного логарифма (сложная задача, стоящая за DSA и шифрованием на эллиптических кривых), и хотите доказать, что знаете её решение, не разглашая само решение. То есть, вам известен такой х, что gx = y mod p, а проверяющий знает только g, y и p. Чтобы убедить проверяющего, вы играете в следующую игру:
- Выбираете случайное число r и отправляете проверяющему значение gr (обязательство).
- Получаете от проверяющего случайное число с (вызов).
- Отправляете проверяющему s = r + cx.
- Проверяющий вычисляет gs = gr + cx и проверяет, что оно равно gr ? yc = gr ? (gx) c.
В этом интерактивном протоколе доказывающий не раскрывает значения х, поскольку отправляет только случайные числа. Однако лишь доказывающий, который знает х, сможет отправить s, проходящее последнюю проверку.
Для превращения такого интерактивного протокола в неинтерактивный (такой, который можно отправить одним набором данных), строятся НИНР-доказательства. Мы самостоятельно играем в эту игру и симулируем проверяющего так, чтобы реальный проверяющий убедился в том, что мы не можем придумать НИНР-доказательство, не зная доказанного утверждения.
Заключение
Ключевые идеи, рассмотренные в статье:
- Основная проблема безопасной системы электронного голосования – публичная проверяемость. Это достигается публикацией зашифрованных бюллетеней на публично доступном форуме. Организаторы голосования также должны описать механизм, проводящий само подтверждение.
- Правильность голосования подтверждается путём проведения авторизации каждого избирателя с уникальным ID и давая избирателям доступ, который позволяет им проверить, что их бюллетень 1) засчитан и 2) не изменён.
- Избирателей нельзя наказать за голоса за «неправильных» кандидатов благодаря сопротивлению принуждению, которое, в частности, достигается за счёт непредсказуемого и вероятностного шифрования.
- Приватность бюллетеней гарантируется тем, что зашифрованные голоса не расшифровываются, а расшифровывается только итог, созданный при помощи гомоморфного шифрования.
- Жульничество не проходит, если мы заставляем избирателей публиковать криптографическое доказательство допустимости их бюллетеня при помощи НИНР.
Концепции и технологии, описанные здесь, могут казаться глубокими и сложными, но на самом деле это только верхушка айсберга. Вы не сможете создать безопасно работающую систему электронного голосования, просто следуя описанию. К примеру, я опустил такие детали, как способ проверки избирателями своих бюллетеней на практике, причину использования сервером НИНР, и прочее. Суть в том, что любой безопасный протокол электронного голосования – штука очень сложная и полная нюансов, и реальная реализация добавляет дополнительных сложностей из-за человеческих и организационных факторов.
Чтобы больше узнать про криптографию, связанную с темой электронного голосования, можете изучить эти, качественные материалы:
Комментарии (16)
spmbt
18.01.2019 17:56Ещё нужна защита при оцифровке ввода:
Важно, чтобы и руки были закрыты. Но лицо — открыто для идентификации. Труба от лица должна быть прозрачной и быть под наблюдением камеры с независимого устройства — смартфона. Т.к. при электронном удалённом голосовании нужно обеспечить аутентификацию голосующего.
Впрочем, и первое устройство может быть смартфоном не под управлением брендовых ОС (т.к. все они прослушиваются, логируются вендором), а устройство защиты может быть чем-то вроде кувшина с рукавами.
Ark_V
18.01.2019 18:52а в более общем случае, избиратель не должен иметь возможности доказать, за кого он голосовал.
а значит организатор голосования может заменить голос избирателя на нужный ему.
И даже если вот тут
нужно, чтобы любой избиратель мог удостовериться, что его голос подсчитали, и подсчитали правильно.
он и сможет удостоверится, что его голос подсчитали не правильно, его можно будет спокойно слать лесом и итоге будет не подсчет голосов, а голосование для показухи и никакой демократии.
Демократия – это не голосование, это подсчёт голосов.
математика не заменит юриспруденцию.
pohjalainen
18.01.2019 19:17а значит организатор голосования может заменить голос избирателя на нужный ему.
Вовсе нет. Это значит, что избиратель не сможет продать свой голос (типа как сейчас фоткают бюллетени).
assad77
19.01.2019 14:45Математика криптоголосования верифицируема и позволяет избавится от подлогов. Есть вероятность, что организатор раскроет тайну голосования, но такая проблема тоже решается (см мою ссылку), по крайней мере частично, путем распределенных организаторов и схемы шамира. Про это, к сожалению, здесь не сказано.
robux
18.01.2019 19:06-1Во-вторых, нужно, чтобы любой избиратель мог удостовериться, что его голос подсчитали, и подсчитали правильно.
Всё верно, это называется верифицируемость.
Это нужно уметь сделать без раскрытия его голоса, а в более общем случае, избиратель не должен иметь возможности доказать, за кого он голосовал.
А вот здесь уже подлог — тайное голосование по определению неверифицируемо. Я повторяю: по определению. Тайного голосование — это значит, что нельзя сопоставить результаты голосования и голосующих, это и есть корень неверифицируемости.
Поэтому единственный способ провести верифицируемое голосование — это сделать его ОТКРЫТЫМ.
Это делается для исключения принуждений, и для того, чтобы дать возможность избирателям свободно выбирать кандидата, не боясь последствий своего выбора.
Ложь. Байка про «принуждения» внедряется в сознание обывателя для педалирования тайного, а значит, неверифицируемого голосования! А это, в свою очередь, делается для безнаказанных фальсификаций результатов голосования!
Запомните: тайное голосование — это тайный лохотрон.assad77
19.01.2019 14:50В данном случае не лохотрон. С точки зрения математики все верифицируется. Эта схема не защищает от мертвых душ. В остальном отлично работает. Вернее не эта схема конечно. Эта не работает, а та откуда все это взяли и неправильно оптсали.
robux
19.01.2019 18:03> С точки зрения математики все верифицируется.
Ничего не верифицируется.
1. Я много раз слышал, что анонимную верифицируемость можно «закопать» в криптографию, но рабочего инструмента (программы) мне никто не предоставил.
2. Если мы говорим про тайное (анонимное) голосование, это значит, мы говорим, что голосующий никак не связан с результатами. Для меня это и есть корень неверифицируемости — раз сопоставить голосующих и результаты выборов нельзя, то нельзя и доказать отсутствие «вбросов», «мёртвых душ», умышленно-математических ошибок, закладок в ПО и другого рода фальсификации.
3. Если зомбированные граждане не понимают, что тайные выборы — это лохотрон, и боятся участвовать в открытых голосованиях, то пусть сидят тихонько дома — на общественных выборах анонимусам делать нечего. Здоровые граждане хотят открытую политику.
4. При открытом голосовании публикуется таблица, кто за кого голосовал. Только открытое голосование верифицируемо. Всех лиц, которые появятся в таблице открытого голосования можно рано или поздно проверить на их реальность (например, активисты в своих районах могут пройти по квартирам, а соседи увидят «мёртвых душ», которых им приписали), а вот в тайном голосовании такой проверки сделать нельзя.
5. Репрессий при открытом голосовании опасаться не стоит потому что, если они возникнут, сразу станут известны общественности и поднимется бунт. К тому же всех в стране (142 млн официально) репрессиями не подавишь и не напугаешь. А вот чего на самом деле надо опасаться, то это фальсифируемого тайного голосования, которое делается элементарно: заменяешь бюллютени, переписываешь протоколы или ещё проще — объявляешь по телику «нужные» результаты.
6. При открытом голосовании по крайней мере будет видно, что людей заставляют. Станет очевидно, что система держится на страхе и насилии — но люди сами выбирают рабство. При тайном же голосовании люди ходят на псевдовыборы, тем самым легитимизируют негодяев и создают иллюзию своей сопричастности, но это только иллюзия — при тайном голосовании граждане ничего не решают.
7. Ну и последнее, мне непонятно: КОМУ НУЖНЫ ТАЙНЫЕ ГОЛОСОВАНИЯ?! Кому нужна анонимность в политической жизни?? Почему так усиленно пропихивают эту вонючую анонимность?! Почему боятся открытого голосования?? Вот мне например анонимность нахрен не нужна — я хочу видеть кто за кого как проголосовал. И это не потому что я весь такой открытый, а потому что открытость — это единственный способ избежать фальсификаций. Единственный 100% способ.
P.S. Если кому-то действительно интересно, как должна выглядеть демократия здорового человека (которая включает децентрализованные системы голосования, сбора записей, подсчета голосов, принятия решений), то читайте мою статью "Демократия как технология".assad77
19.01.2019 22:36>Ничего не верифицируется.
Еще как верифицируется. Я сам этим матаппаратом пользовался.
>нельзя и доказать отсутствие «вбросов», «мёртвых душ»
Вбросы можно, а «мертвые души» действительно нельзя.
С умышленными ошибками и закладками бороться сложно, но есть механизмы типа opensource.
все остальное мне просто не очень интересно, я смотрю только со стороны математики.
Хотя некоторые моменты, если и не оспорил, то привёл бы контрдоводы, например, уже сейчас используется админ ресурс, когда сгоняют на массовки кучу народу. В такой ситуации, когда, допустим, твоя работа зависит от того, как ты проголосуешь, а работы нет, ты ещё как будешь голосовать как скажут.
Это есть и в России и в Украине да и думаю такое будет везде.
Да и влияние стыда, когда ты не хочешь конфликтовать с окружением, но имеешь иное мнение тоже не стоит сбрасывать со счетов.
Эта статья социальных аспектов не учитывает. в ней решается чисто математическая проблема «Тайного голосования». Математика всегда ценна сама по себе без привязок к реальной жизни. предлагаю так эту статью и рассматривать.robux
20.01.2019 04:46> Вбросы можно, а «мертвые души» действительно нельзя.
Если мы не можем доказать, содержат результаты голосования мертвые души или не содержат, то всё — система неверифицируема.
Я так сразу и сказал: тайное голосование неверифицируемо.assad77
21.01.2019 10:321. мертвые души вполне могут быть и при открытом голосовании. этот момент вообще ничего не решает.
кроме того, в масштабах страны организовать открытое голосование практически невозможно. хоть в электронном хоть в каком виде. можно не предпринимать дополнительных мер для сокрытия, но даже просто регистрация голосов в электронном виде достаточно сильно закрывает открытость, из-за небольшого числа людей способных убедиться в итогах голосования. Лучше уж чтобы оно было закрытым, чтобы хотя-бы правила игры были для всех одинаковы. (Это кстати тоже плюс к тем доводам, что дискредитируют открытое голосование)
2. голосование верифицировано. это регистрация неверифицируема. также вполне возможна ситуация, когда есть способы выполнить верифицировать регистрацию другими способами. например, в группах, где процент голосующих достаточно высок, а подделать количество экономически нецелесообразно, тк все друг друга знают по переписке, например, а аватара содержать может быть слишком дорого.
vlad9486
19.01.2019 00:19Электронное голосование должно давать возможность менять свой голос в любой момент времени и избирать почти кого угодно (кого можно по конституции). Нужна криптовласть (в блокчейне) — которою можно делегировать, переделегировать и отзывать.
Sheti
19.01.2019 07:02Не совсем понятно почему столько усилий концентрируется именно на голосовании. Это всего лишь один этап в целой цепочке событий. То что в результате голосования выбирается какой то представитель это вовсе не означает, что этот представитель будет проводить в жизнь чаяния тех кто его избрал.
С другой стороны путь прямого голосования, за каждый вопрос каждым гражданином это чересчур утопичная идея. И у нас целый институт людей создан чья работа именно голосовать за тех кто его избрал (это конечно в идеале).
Лично я, если уж фантазировать, вижу систему несколько другой. Я бы основывался именно на идее делегирования права голоса. Если это реализовать в электронном виде и дать возможность менять того кому ты делегируешь право своего голоса в любой момент получается система очень близкая к идеи демократии. Следующим шагом было бы дать возможность делегировать право своего голоса вообще любому гражданину. Таким образом допустим вся семья делегирует права своих голосов допустим дедушке, дедушка свой и те голоса которые ему делегировали передавал бы дальше. Таким образом выстраивалось бы дерево где в конце некоторое кол-во людей концентрировали бы на себе множество голосов. Вполне аналог современных политиков, но при учете всего, что я говорил выше таким политиком мог бы стать любой человек без необходимости создавать партии и идти на поклон гос-ву для её регистрации. И мне видится, что такая группа людей с большим кол-вом голосов уже бы могла целенаправленно заниматься тем, чем сейчас занимаются депутаты в думе — голосовали бы за законы на постоянной основе.
Конечно всё, что я говорил это в высшей степени утопия зато очень близкая к идеи прямой демократии.vlad9486
19.01.2019 14:42Криптовласть концентрируется у людей, они разыгрывают должности на аукционах и раздают остатки власти людям со своей команды что-бы те разыграли должности заместителей. Когда кто-то теряет власть, она транзитивно изымается у одного из заместителей, тот теряет должность и эта должность переразыгрывается на новом аукционе, куда уже может пройти оппозиция. Так команда может терять власть постепенно.
maxzhurkin
20.01.2019 21:17это мультипликативный гомоморфизм, а нам нужен аддитивный
логарифмирование — наше всё
P.S. Простите, не удержался
assad77
тут автор немного накосячил он видать начитался, но не не всё понял ( я имею в виду изначального автора)
как минимум в ElGamal Enc(0) = 0, а Dec(Enc(1)*Enc(1))=1
а Enc(0)*Enc(1) = 0
поэтому для елгамаля и для RSA такой способ не работает.
Есть другой, он и описан в приведенной статье.
Разработать же для Пайе весь стек необходимый для голосования достаточно нетривиальная задача.