(Ноябрь 2007)
Сильные, но малоизвестные технологии для честных электронных выборов
Компьютерные технологии в системах голосования вызывают очень много споров, потому что с их помощью значительно легче подделывать результаты выборов. Но это смотря как к электронике подходить.
Как и любой другой инструмент двойного применения, компьютерные системы голосования можно затачивать под манипуляции, а можно и совсем наоборот – под полную прозрачность и проверяемость результатов от начала до конца (или кратко E2E – входящий ныне моду термин «end-to-end audit»).
Простые решения для сложных проблем
Что обычно принято подразумевать под честными и справедливыми выборами? Ответ на этот вопрос сводят к двум основополагающим принципам.
(1) Избиратели должны делать свое волеизъявление с помощью тайного голосования. Так, чтобы никто не мог узнать, кто как проголосовал (даже если избиратель почему-то захочет сам рассказать). Иначе говоря, чтобы никто не мог подкупить человека или вынудить силой к голосованию нужным образом, а избиратели, соответственно, не могли бы продавать свой голос.
(2) Процесс голосования должен быть точным и проверяемым. Так, чтобы все могли быть уверены, что никто не проголосовал больше одного раза; что никаких голосов не было вброшено, уничтожено или подменено; что голосовали только зарегистрированные избиратели, а все отданные голоса были подсчитаны правильно.
Главная проблема честных выборов в том, что два этих базовых принципа очень трудно совместить друг с другом.
Совсем несложно сделать голосование точным и проверяемым – просто зафиксировав все пары «избиратель-голос» и открыто опубликовав результаты для всеобщей проверки. Но тогда будет также очень просто подкупать голоса и манипулировать избирателями, подрывая основы демократии.
Механизмы же тайного голосования, с другой стороны, по «темной» природе своей дают широчайшее поле для злоупотреблений и махинаций с голосами.
Однако, как это часто бывает в жизни вообще, первоначальное восприятие вроде бы очевидного факта о плохой сочетаемости базовых принципов на самом деле оказывается неверным.
Например, на протяжении многих столетий люди были уверены, что засекреченная связь возможна лишь между теми, кто непременно владеет общим секретом – ключом к шифру.
Столь же прочны были и представления о единственно возможном механизме организации выборов с помощью избирательных комиссий, подсчитывающих конкретное число голосов, отданных за конкурирующих кандидатов.
Но четверть века назад в защите информации произошла великая революция, когда выяснилось, что существуют математически строгие методы засекречивания, позволяющие шифровать связь между абсолютно незнакомыми и никогда не общавшимися людьми – посредством криптографии с открытым ключом.
А попутно ученые установили, что с помощью тех же самых, в сущности, идей можно реализовать и честные выборы, успешно примиряющие взаимно-исключающие принципы. Правда, поначалу лишь в условиях идеализированных теоретических моделей, довольно далеких от реалий жизни.
Эти модели подразумевали избирателей, подающих свои голоса в зашифрованном виде, чтобы никто из счетчиков комиссии не знал содержимое заполненного бюллетеня. При этом специальный метод «доказательства с нулевым знанием» (zero knowledge proof) обеспечивал для счетчиков механизм, подтверждающий правильность учтенных и подсчитанных голосов.
А независимые комиссии наблюдателей, в свою очередь, могли проверять эти доказательства и убеждаться, что счетчики действительно не жульничали. Однако при этом никто не получал информации о том, кто и как за кого проголосовал – это становилось известно лишь на финише, при публикации итогового подсчета голосов.
Главная красота моделей была в том, что здесь не требовалось слепо доверять честности власти, организующей выборы, или программистам, сделавшим систему выборов по заказу правительства, или кому-либо еще. Никто из них просто в принципе не мог сжульничать. Потому что это было математически невозможно – обмануть и при этом не быть пойманным проверяющими (с убедительным доказательством жульничества).
Все, что для этого требовалось – заложить в систему права на верификацию. И тогда любой, в принципе, грамотный человек мог воспользоваться программой-верификатором (или написать собственную) и проверить доказательства честности выборов самостоятельно – согласно стандартным процедурам проверки.
Такого рода модели в теории выглядели совершенно великолепно, но для практического воплощения они были чересчур сложны. Лежавшие же в их основе идеи основаны на нетривиальной математике, доступной для понимания лишь специалистам. А потому убедить обычного среднестатистического избирателя в том, что новая схема выборов намного лучше всех прежних, казалось задачей практически невыполнимой.
Иначе говоря, обеспеченные криптографией подлинно честные выборы многие годы рассматривались как грандиозная, в принципе, идея, но увы, абсолютно неприменимая в реальной жизни.
Подобные взгляды держались довольно долго, но затем – к середине нынешнего десятилетия – сразу несколько умных человек вдруг поняли, что те же самые в сущности идеи можно реализовать совсем просто, безо всякой мудреной математики и понятно даже для детей. Вряд ли должно удивлять, что людьми этими оказались видные и широко известные в мире ученые-криптографы.
Далее будут представлены две наиболее значительные из новых систем, впервые обнародованные – практически одновременно – около года тому назад (в 2006).
Система Punchscan
Система под названием, переводимым примерно как «Дыркоскан» (http://punchscan.org), изобретена Дэвидом Чомом (David Chaum) и ныне совместно развивается коллективом аспирантов и студентов из четырех университетов США и Канады.
Ранее Чомом был разработан целый ряд криптографических протоколов, широко применяемые ныне в электронной коммерции, а также концепция «цифровых наличных». Кроме того, в 1982 году Дэвид Чом был одним из отцов-основателей IACR, Международной ассоциации криптологических исследований, по сию пору остающейся главной в мире организацией для ученых и инженеров открытой криптографии (т.е. работающих вне секретных спецслужб).
При сравнении с традиционным избирательным бюллетенем система Punchscan поначалу может показаться несколько замысловатой, однако принцип ее работы объясняется легко и просто. Особенно тем людям, кто играет в лотерею, поскольку новый бюллетень по устройству похож на карточки лото, несколько частей которых идентично заполняются самими играющими.
Бюллетень Punchscan представляет собой лист бумаги, поделенный на две равные части линией перфорации, проходящей посередине. На каждой из половин напечатан уникальный номер, идентифицирующий бюллетень. Лист складывают пополам по линии раздела, так что на первой странице оказываются напечатаны имена избираемых кандидатов, каждому из которых случайным образом присвоена одна из букв алфавита.
Ниже списка имеется горизонтальный ряд круглых отверстий, число которых соответствует количеству кандидатов. Через эти отверстия видно те же буквы алфавита, соответствующие кандидатам, но напечатанные на второй половине бюллетеня опять-таки в произвольном порядке.
Когда избиратель выбирает кандидата, ему надо найти в отверстиях соответствующую букву и отметить ее специальным маркером-фломастером. Диаметр красящего стержня у маркера преднамеренно сделан большего размера, чем величина отверстия. Поэтому такой маркер обязательно пометит обе половинки бюллетеня в позиции избранного кандидата.
Когда выбор сделан, избиратель разделяет бюллетень по линии перфорации. Одна из половинок (все равно какая) тут же публично уничтожается в машине-шреддере, а вторая пропускается через стандартный портативный сканер и остается у избирателя в качестве проверочной квитанции.
Отсканированный бюллетень с распознанным выбором изображается на экране, так что избиратель имеет возможность убедиться в правильности учета и подтвердить завершение голосования.
Таким образом, система Punchscan фиксирует выборы, сделанные избирателями, однако не имеет никакой базы данных, сопоставляющей конкретный бюллетень с использовавшим его человеком.
Очень важно случайное присвоение букв каждому из кандидатов, так что в разных бюллетенях эти буквы будут гарантированно разными у одних и тех же фамилий в списке. По этой причине каждая из половинок бюллетеня по отдельности не дает никакой информации о сделанном выборе.
Ибо на одной части есть фамилии с присвоенными им буквами и помеченная дырка, но неизвестно какая там была буква. А на второй части есть помеченная буква, но неизвестно, какому кандидату она была присвоена.
Благодаря такой системе, избиратели не могут продавать свой голос, предъявляя квитанцию. А избирательные комиссии, проводящие выборы на местах, соответственно, обеспечивают лишь правильную процедуру голосования, но при этом не имеют ни малейшего понятия, как именно отданы голоса.
Итоги может подвести лишь центральная система Punchscan, где случайное присвоение букв было изначально зафиксировано в базе для каждого номера бюллетеня. Система, как уже говорилось, ничего не знает о том, каким избирателям достались какие номера. Однако каждый избиратель после итогового подсчета голосов может зайти в онлайновую базу и по номеру оставшейся у него квитанции проверить, что его голос учтен и учтен правильно.
Комплекс программного обеспечения Punchscan в первой стабильной версии 1.0 был опубликован с открытыми исходными кодами в ноябре 2006 на условиях лицензии Revised BSD.
При этом система Punchscan разработана на основе принципов безопасного программирования, т.е. защита информации здесь реализована программно-независимым образом – на основе известных и надежных криптографических функций. Иначе говоря, такую архитектуру можно доверяемо реализовывать и в системах с закрытыми кодами вроде Windows.
Система 3Ballot
Другая система, под названием ThreeBallot или «Трехчастевой бюллетень» (rangevoting.org/Rivest3B.html), разработана знаменитым американским криптографом Рональдом Райвестом (Ronald Rivest).
Ученый известен, прежде всего, как буква «R» в популярнейшей криптосхеме с открытым ключом RSA, озаглавленной по фамилиям изобретателей, а также благодаря его массово распространенным криптоалгоритмам для поточного шифрования, блочного шифрования и хеширования (RC4, RC5, MD5 и многие другие).
В придуманной Райвестом системе выборов ThreeBallot для учета отданных избирателями голосов тоже используется бумажный бюллетень, но другой особой конструкции.
Как можно догадаться по названию системы, здесь бюллетень состоит из трех практически одинаковых частей, разделенных перфорацией для легкого отрывания. Каждую часть отличает от соседних (и всех остальных в прочих бюллетенях) уникальный случайно присвоенный номер-идентификатор, напечатанный по нижнему краю.
Главная хитрость этого изобретения в том, каким образом бюллетень заполняется избирателем. Три идентичные части предоставляют три позиции голосования для каждого из кандидатов. Чтобы проголосовать «за» кого-то из кандидатов, избиратель отмечает его «птичками» в любых двух из трех частей (в третьей оставляя позицию незаполненной).
В то же время здесь следует голосовать «против» тех кандидатов, которых избиратель выбирать не желает. Для этого напротив них тоже проставляется «птичка», но только в одной произвольной части бюллетеня из трех (чтобы две остальные остались пустыми). Иначе говоря, совсем пустых рядов быть не может, ибо заполнить надо каждую строку бюллетеня – «за» двумя отметками, «против» одной.
После чего бюллетень разделяется по перфорации на три отдельных части, по выбору избирателя с одной из частей делается копия и выдается ему в качестве квитанции, а затем все три части опускаются в избирательную урну.
В исходной статье Райвеста о ThreeBallot [pdf] со всеми подробностями разбирается, каким образом при такой системе с высокой степенью достоверности удается совместить взаимно противоречивые требования к демократическим выборам – тайну голосования и проверяемость верности учета.
Одно из важных достоинств системы в ее прозрачности и простоте проверки – поскольку после сканирования всех бюллетеней, изъятых из урн, они полностью и открыто публикуются на веб-сайте избиркома.
Кроме того, квитанция совершенно не раскрывает информации о том, кем и за кого был отдан голос, т.е. не может быть использована в скупке голосов избирателей.
Как и любая другая система голосования, ThreeBallot имеет не только достоинства, но и недостатки. В Массачусетском технологическом институте, где многие десятилетия работает Райвест, студенты уже в декабре 2006 года устроили «игрушечные» выборы, чтобы в реальных условиях проверить работоспособность новой системы.
Изъяны ThreeBallot, выявленные в полевых испытаниях и в придирчивых аналитических исследованиях коллег, автор попытался исправить в новой работе, подготовленной совместно с общественным активистом-математиком Уорреном Смитом (Warren D. Smith) и опубликованной летом 2007 года.
Принимая во внимание высочайшую важность эффективных технологий голосования для поддержания и развития демократии, Райвест не стал защищать свое изобретение никакими патентами и лицензиями, сразу передав идею ThreeBallot во всеобщее достояние.
Проверки и дополнительная безопасность
Базовые процедуры проверки честности выборов для описанных систем содержат как несколько общих моментов, так и некоторые существенные различия.
В каждой из технологий квитанция, оставляемая у избирателя после выборов, не раскрывает то, за кого был отдан голос. Иными словами, в квитанции не содержится никакой секретной информации. Поэтому после выборов избирательная комиссия публикует содержимое каждой из квитанций в онлайновой базе данных.
А всякий избиратель, соответственно, может свободно зайти в эту базу и, введя идентификационный номер своей квитанции, сверить ее содержимое с учетной записью в базе. Таким образом, избиратель может удостовериться, что его/ее голос зафиксирован правильно.
Также благодаря такой базе любой избиратель или всякая заинтересованная в честных выборах сторона могут проинспектировать и правильность итоговых подсчетов в целом.
В случае системы Punchscan, правда, все содержимое базы предоставить для проверки нельзя, поскольку это позволит установить соответствие между голосами и идентификаторами бюллетеней. Однако, половина базы данных здесь может быть раскрыта вполне безопасно и без нарушения принципов тайного голосования.
И поскольку эта половина формируется в результате случайного выбора записей, контрольная процедура с высокой надежностью позволяет удостовериться, что все бюллетени подсчитаны правильно.
В системе ThreeBallot подобной проблемы нет, поэтому для открытого доступа и проверки правильности учета/подсчета публикуются все 3N бюллетеней при N проголосовавших.
Если непосредственно при голосовании использование компьютеров сведено к минимуму (как звена, наиболее уязвимого для злоупотреблений), то на этапах подготовки выборов и итоговых подсчетов результатов продвинутые инфотехнологии оказываются чрезвычайно полезны для усиления возможностей проверки.
Разработчики Punchscan, в частности, создали целый ряд мер для обеспечения целостности и честности выборов в условиях работы избиркомов, полностью разложенных коррупцией. Для итоговых подсчетов, например, придумана схема из нескольких независимых друг от друга баз данных.
Каждая база может быть наполовину открыта для инспекции конкурентами, а при итоговых подсчетах все они должны давать один и тот же результат. Так что если власть захочет подделать итоги выборов, ей придется подделывать содержимое каждой из баз данных. Вероятность обнаружения жульничества при этом растет в экспоненциальной зависимости от числа независимых баз. Так что обеспечить честные выборы становится намного легче.
Созвучные варианты ИТ-подходов разработаны и для обеспечения честных выборов на этапе их подготовки – при печати бюллетеней и создании исходной базы (или баз) данных с идентификационными номерами напечатанных бюллетеней.
Методы проверки тут строятся на основе криптографических однонаправленных функций, заранее вычисляющих на основе уникальных идентификаторов и прочей исходной информации хеш-значения или «битовые обязательства» власти не жульничать.
Подводя же общий итог этому краткому обзору новостей в технологиях голосования можно заключить следующее. Научные методы теории информации, теории вероятностей и криптографии на сегодняшний день позволили построить простые для понимания, эффективные в механизмах и очевидно реализуемые на практике технологии демократии для безопасного и насквозь прозрачного голосования.
Реально эти технологии для выборов государственной власти пока что нигде не применяются. Захочет ли вообще власть этими технологиями воспользоваться – вопрос пока открытый.
The End
[ВРЕЗКА]
Какие выборы лучше?
Граждане России, США и многих других стран знакомы, главным образом, лишь с одной системой выборов власти – по большинству отданных за кандидата голосов (Plurality Voting).
Суть этой системы сводится к нехитрой формуле «выбери одного кандидата из списка – и гуляй отсюда». Выигрывает выборы, соответственно тот, кого отметили в наибольшем числе бюллетеней. К сожалению, эта система весьма неудачна во многих отношениях:
- кандидат, значительным большинством расколотых избирателей расцениваемый как наихудший вариант из всех, в таких условиях может легко обойти конкурентов и выиграть выборы;
- голосование избирателей за своего любимого кандидата может быть большой стратегической ошибкой (оттягивая очень нужные голоса у более вероятного победителя, противостоящего совсем неприемлемому, но тоже вероятному варианту);
- выборы по большинству голосов отражают наименьшее количество информации о реальных предпочтениях людей, опровергая идею о том, что цель голосования – сбор информации о воле народа;
- с течением времени страны с выборами по большинству голосов трансформируются в систему двухпартийного доминирования, так что у избирателей остается лишь самый минимальный выбор, подрывающий суть демократии.
При этом ученым политологам уже 200 лет, по меньшей мере, известны куда более лучшие системы голосования.
Одна из самых простых – это голосование одобрением (Approval Voting), где избиратель отмечает в бюллетене всех кандидатов, которых «одобряет». А выигрывает, соответственно, тот, кто получил наибольшее число одобряющих голосов.
Эта система даже проще классической схемы «по большинству», потому что здесь нет никаких особых правил для отбраковки «неправильно заполненных» бюллетеней с голосами за несколько кандидатов. (Один из вариантов голосования одобрением использовался на заре демократии в США, при выборе первых четырех президентов).
Среди наиболее удачных вариантов из альтернатив – голосование ранжированием (Range Voting), где избиратель оценивает каждого кандидата по десятибалльной, скажем, системе от 0 до 9.
Понятно, что выигравшим считается кандидат, набравший наибольшее количество баллов. Но одновременно и отдача 9 баллов любимому кандидату никогда не будет стратегической ошибкой, так что избиратели будут голосовать более честно и предоставлять более объективную картину о воле народа.
[КОНЕЦ ВРЕЗКИ]
[Межколонные ВРЕЗКИ]
**
Электронные системы голосования, ускоренными темпами внедряемые ныне в политическую жизнь множества стран, уже успели сильно разочаровать публику своей капризностью и ненадежностью. За последние месяцы применение подобных систем было запрещено в Нидерландах, отодвинуто в неопределенное будущее в Британии и существенно скорректировано новыми законами в США.
**
В период с 1860 по 1890 годы для борьбы с широкомасштабной подделкой выборов в США было введено множество разных технических средств. Таких, как избирательные урны с прозрачными стеклянными стенками для недопущения двойного дна и встроенных тайных отсеков. Или механических счетчиков для опускаемых в щель бюллетеней, чтобы предотвратить хищения отданных голосов и массовое вбрасывание фальшивых бюллетеней.
**
На основе системы Райвеста ThreeBallot за последний год разработано еще несколько новых систем голосования: трехчастевой бюллетень VAV (Голос-Антиголос-Голос), упрощенная система Twin с одночастевым бюллетенем и ряд других модификаций. На основе идей Punchscan Дэвид Чом разрабатывает ныне более продвинутую систему голосования Scantegrity (www.scantegrity.org).
[КОНЕЦ ВРЕЗОК]
kiwi arXiv 