Punchscan

редактировать

Punchscan

Разработчик (и)	, Дэвид Чаум и.

Стабильная версия	1.0 (2 ноября 2006 г.)
Предварительная версия	1.5 (16 июля 2007 г.)

Написано на	Java
Операционная система	Кросс-платформенная
Доступна на	Английский
Тип	система подсчета голосов
Лицензия	Пересмотренная лицензия BSD
Веб-сайт	http://punchscan.org/

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

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

Команда Punchscan с дополнительными участниками с тех пор разработала Scantegrity.

Содержание

1 Процедура голосования
2 Процедура подведения итогов
- 2.1 Обобщенная форма
3 Основные процедуры аудита
4 Дополнительная безопасность
- 4.1 Несколько баз данных
- 4.2 Обязательства
- 4.3 Проверка бюллетеней
5 См. Также
6 Ссылки
7 Внешние ссылки

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

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

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

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

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

Процедура табулирования

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

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

P 1 ∈ {0, 1} = {AB, BA} {\ displaystyle P_ {1} \ in \ {0,1 \} = \ {{\ t_dv {AB}}, {\ t_dv {BA}} \} \,}

P_ {1} \ in \ {0,1 \} = \ {{\ t_dv {AB}}, {\ t_dv {BA}} \} \,

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

$P 2 {\ displaystyle P_ {2}}$ $P_ {2}$ : порядок символов в отверстиях,

P 2 ∈ {0, 1} = {AB, BA} {\ displaystyle P_ {2} \ in \ {0,1 \} = \ {{\ t_dv {AB}}, {\ t_dv {BA}} \} \,}

P_ {2} \ in \ {0,1 \} = \ {{\ t_dv {AB}}, {\ t_dv {BA}} \} \,

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

P 3 ∈ {0, 1} = {1st, 2nd} {\ displaystyle P_ {3} \ in \ {0,1 \} = \ {{\ t_dv {1st}}, {\ t_dv {2nd}} \} \,}

P_ {3} \ in \ {0,1 \} = \ {{\ t_dv {1-й}}, {\ t_dv {2-й}} \} \,

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

R ∈ {0, 1} = {Coke, Pepsi} {\ displaystyle R \ in \ {0,1 \} = \ {{\ t_dv {Coke}}, {\ t_dv {Pepsi}} \} \,}

R \ in \ {0, 1 \} = \ {{\ t_dv {Coke}}, {\ t_dv {Pepsi}} \} \,

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

R = P 1 + P 2 + P 3 mod 2 {\ displaystyle R = P_ {1} + P_ {2} + P_ {3} {\ bmod {2 }} \,}

R = P_ {1} + P_ {2} + P_ {3} {\ bmod 2} \,

(Уравнение 1 )

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

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

D 2 + D 4 = P 1 + P 2 mod 2 {\ displaystyle D_ {2} + D_ {4} = P_ {1} + P_ {2} {\ bmod {2}} \,}

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

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

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

D 3 = P 3 + D 2 mod 2 {\ displaystyle D_ {3} = P_ {3} + D_ {2} {\ bmod {2}} \, }

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

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

R = D 3 + D 4 mod 2 {\ displaystyle R = D_ {3} + D_ {4} {\ bmod {2}} \,}

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

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

R = (D 3) + D 4 mod 2 = (P 3 + D 2) + D 4 mod 2 = P 3 + (D 2 + D 4) mod 2 = P 3 + (P 1 + P 2) mod 2 {\ displaystyle {\ begin {align} 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 {align}}}

{\ begin {align} 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 {align}}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. Также

Ссылки

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

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