Перфорация

Перфорация

Разработчик(и)	Ричард Карбэк , Дэвид Чаум , Джереми Кларк , Алекс Эссекс и Стефан Поповенюк .
Стабильная версия	1,0 (2 ноября 2006 г.) [±]
Предварительный выпуск	1,5 (16 июля 2007 г.) [±]
Написано в	Ява
Операционная система	Кросс-платформенный
Доступно в	Английский
Тип	система подсчета голосов
Лицензия	Пересмотренная лицензия BSD
Веб-сайт	http://punchscan.org/

Punchscan — с оптическим сканированием, система подсчета голосов изобретенная криптографом Дэвидом Чаумом . Punchscan призван обеспечить целостность, конфиденциальность и прозрачность. Система доступна для проверки избирателями, обеспечивает механизм сквозного аудита (E2E) и выдает квитанцию ​​о голосовании каждому избирателю . Система выиграла главный приз на Университетском конкурсе систем голосования в 2007 году .

Компьютерное программное обеспечение , которое включает в себя Punchscan, имеет открытый исходный код ; исходный код был выпущен 2 ноября 2006 года под пересмотренной лицензией BSD . Однако Punchscan не зависит от программного обеспечения; он черпает свою безопасность из криптографических функций вместо того, чтобы полагаться на безопасность программного обеспечения, такого как машины для голосования DRE . По этой причине Punchscan можно запускать в с закрытым исходным кодом операционных системах , таких как Microsoft Windows , и при этом сохранять безусловную целостность.

С тех пор команда Punchscan вместе с другими участниками разработала Scantegrity .

Процедура голосования

Помеченный бюллетень Punchscan. Полный бюллетень (вверху), раздельный бюллетень (внизу).

Punchscan Бюллетень состоит из двух слоев бумаги. На верхнем слое кандидаты перечислены с символом или буквой рядом с их именем. Под списком кандидатов в верхнем слое бюллетеня находится ряд круглых отверстий. Внутри отверстий нижнего слоя напечатаны соответствующие символы.

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

Порядок символов рядом с именами кандидатов генерируется случайным образом для каждого бюллетеня и, таким образом, отличается от бюллетеня к бюллетеню. Аналогично и с порядком символов в отверстиях. По этой причине квитанция не содержит достаточной информации для определения того, за какого кандидата был отдан голос. Если верхний слой сохранен, порядок прохождения символов через отверстия неизвестен. Если нижний слой сохраняется, порядок символов рядом с именем кандидата неизвестен. Таким образом, избиратель не может доказать кому-либо, как он голосовал, что предотвращает подкуп голосов или запугивание избирателей.

Процедура подведения итогов

В качестве примера рассмотрим выборы двух кандидатов между Coke и Pepsi , как показано на предыдущей диаграмме. Порядок букв рядом с именами кандидатов может быть следующим: A и затем B или B и затем A. Мы назовем этот порядок букв $P_{1}$, и пусть $P_{1}$=0 для прежнего порядка и $P_{1}$=1 для последнего. Поэтому,

$P_{1}$: порядок символов рядом со списком кандидатов,

$P_{1}\in \{0,1\}=\{{\mbox{AB}},{\mbox{BA}}\}\,$.

Аналогично мы можем обобщить и другие части бюллетеня:

$P_{2}$: порядок символов через отверстия,

$P_{2}\in \{0,1\}=\{{\mbox{AB}},{\mbox{BA}}\}\,$.

$P_{3}$: какое отверстие отмечено,

$P_{3}\in \{0,1\}=\{{\mbox{1st}},{\mbox{2nd}}\}\,$.

$R$: результат голосования,

$R\in \{0,1\}=\{{\mbox{Coke}},{\mbox{Pepsi}}\}\,$.

Обратите внимание, что порядок имен кандидатов фиксирован во всех бюллетенях. Результат голосования можно рассчитать непосредственно как:

$R=P_{1}+P_{2}+P_{3}{\bmod {2}}\,$ ( Уравнение 1 )

Однако если один слой бюллетеня будет уничтожен, либо $P_{1}$ или $P_{2}$ разрушен. Поэтому информации для расчета недостаточно. $R$ из квитанции (которая сканируется). Для подсчета результатов выборов электронная база данных используется .

Перед выборами база данных создается с рядом столбцов как таковая. Каждая строка в базе данных представляет бюллетень для голосования, а порядок хранения бюллетеней в базе данных меняется ( с использованием криптографического ключа каждый кандидат , который может внести ). Первый столбец, $D_{1}$, имеет перетасованный порядок серийных номеров. $D_{2}$ содержит псевдослучайный битовый поток, сгенерированный на основе ключа, и он будет действовать как поточный шифр . $D_{3}$ сохранит промежуточный результат. $D_{4}$ содержит такой бит, что:

$D_{2}+D_{4}=P_{1}+P_{2}{\bmod {2}}\,$

Результат каждого голосования будет храниться в отдельной колонке. $R$, где порядок бюллетеней будет снова перетасован. Таким образом $D_{5}$ содержит номер строки в $R$ столбец, в который будет помещен результат.

После проведения выборов и $P_{3}$ значения были отсканированы, $D_{3}$ рассчитывается как:

$D_{3}=P_{3}+D_{2}{\bmod {2}}\,$

И результат рассчитывается как,

$R=D_{3}+D_{4}{\bmod {2}}\,$

Это эквивалентно уравнению 1,

${\begin{aligned}R&=(D_{3})+D_{4}{\bmod {2}}\\&=(P_{3}+D_{2})+D_{4}{\bmod {2}}\\&=P_{3}+(D_{2}+D_{4}){\bmod {2}}\\&=P_{3}+(P_{1}+P_{2}){\bmod {2}}\end{aligned}}$

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

Обобщенная форма

На выборы с $n$ кандидатов, описанная выше процедура выполняется с использованием уравнений по модулю -n.

Основные процедуры аудита

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

Любой избиратель или заинтересованная сторона также может проверить часть базы данных, чтобы убедиться в правильности расчета результатов. Они не могут проверить всю базу данных, иначе они могут связать голоса с серийными номерами бюллетеней. Однако половину базы данных можно безопасно проверить, не нарушая конфиденциальности. Производится случайный выбор между открытием $\{D_{1},D_{2},D_{3}\}$ или $\{D_{3},D_{4},D_{5}\}$ (этот выбор может быть получен из секретного ключа или из действительно случайного источника, такого как игральные кости или фондовый рынок ). Данная процедура позволяет избирателю быть уверенным в том, что вся совокупность бюллетеней была засчитана как поданная .

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

Дополнительная безопасность

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

Несколько баз данных

С $D_{1}$, $D_{2}$, и $D_{5}$ в базе данных все генерируются псевдослучайно, можно создать несколько баз данных с разными случайными значениями для этих столбцов. Каждая база данных независима от других, что позволяет открывать и проверять первую половину некоторых баз данных и вторую половину других. Каждая база данных должна выдавать одинаковый итоговый результат. Таким образом, если бы избирательный орган вмешался в базу данных, чтобы исказить окончательные результаты, ему пришлось бы вмешаться в каждую из баз данных. Вероятность обнаружения взлома в ходе проверки возрастает с увеличением количества независимых баз данных.

Обязательства

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

Проверка бюллетеней

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

См. также

• Потоковое шифрование
• Схема обязательств
• Доказательство с нулевым разглашением

Внешние ссылки

• Домашняя страница проекта
• Представление Vocomp — подробный 80-страничный документ, объясняющий все аспекты системы.
• Электронная демократия — BBC World ’s Digital Planet аудиоинтервью с Дэвидом Чаумом .
• Учет каждого электронного голоса — IEEE Spectrum .
• Прозрачное и открытое голосование с помощью Punchscan: Часть I и Часть II
• Future Tense Аудиоинтервью с Дэвидом Чаумом .