Голосование со слепыми подписями

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

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

(2) Каждый избиратель лично маскирует все сообщения (см. раздел 5.3) и посылает их в ЦИК вместе с ма с-кирующим множителями.

(3) ЦИК по своей базе данных проверяет, что пользователь не присылал раньше для подписания свои зама с-кированные бюллетени. ЦИК открывает 9 из наборов, проверяя, что они правильно сформированы . Затем она индивидуально подписывает каждое сообщение набора и посылает их обратно избирателю, сохраняя имя избирателя в своей базе данных.

(4) Избиратель снимает маскировку с сообщений и получает набор бюллетеней, подписанных ЦИК . (Эти бюллетени подписаны, но не зашифрованы, поэтому избиратель легко увидит, какой из бюллетеней - "да", а какой - "нет". )

(5) Каждый избиратель выбирает один из бюллетеней (о, демократия!) и шифрует его открытым ключом

ЦИК.

(6) Избиратель отправляет свой бюллетень.

(7) ЦИК расшифровывает бюллетени, проверяет подписи, проверяет по базе данных уникальность идентиф и-кационного номера, сохраняет последовательный номер и подводит итоги. Она опубликовывает результ а-ты голосования вместе с каждым последовательным номером и соответствующим бюллетенем .

Мэллори, избиратель-жулик, не может обмануть эту систему. Протокол слепой подписи обеспечивает еди н-ственность его бюллетени. Если он попытается отправить тот же бюллетень дважды, ЦИК обнаружит дублир о-вание последовательных номеров на этапе (7) и не будет учитывать второй бюллетень. Если он попытается получить несколько бюллетеней на этапе (2), ЦИК обнаружит это на этапе (3). Мэллори не может создать свои собственные бюллетени, потому что он не знает закрытого ключа комиссии . По той же причине он не может перехватить и изменить чужие бюллетени.

Протокол "разрезать и выбрать" на этапе (3) должен обеспечить уникальность бюллетеней. Без этого этапа Мэллори мог бы создать точно такой же, за исключением идентификационного номера, набор бюллетеней и заверить их все в ЦИК.

Мошенническая ЦИК не сможет узнать, как голосовал конкретный избиратель. Так как протокол слепой подписи маскирует последовательные номера бюллетеней до момента подведения итогов , ЦИК не сможет установить связь между подписанным ею замаскированным бюллетенем и подытоживаемым бюллетенем . Опубликование перечня последовательных номеров и связанных с ними бюллетеней позволяет пользователям убедит ь-ся, что их бюллетени были правильно учтены.

Но проблемы все еще остаются. Если этап (6) не анонимен, и ЦИК может записать, кто какой бюллетень прислал, то она сможет узнать, кто за кого голосовал. Однако, это невозможно, если комиссия получает бюллетени в запечатанной урне для голосования и считает их позже . Хотя ЦИК и не сможет установить связь между избирателями и их бюллетенями, она сможет создать большое количество подписанных и правильных бюлл е-теней и смошенничать, прислав их сама себе . И если Алиса обнаружит, что ЦИК подменила ее бюллетень, она не сможет доказать этого. Аналогичный протокол, пытающийся устранить эти проблемы, описан в [1195, 1370].

Голосование с двумя Центральными комиссиями

Одним из решений является разделить ЦИК пополам . Ни у одной из них не будет достаточно власти, чтобы смошенничать по своему усмотрению.

В следующем протоколе используется Центральное управление регистрации (ЦУР), занимающееся прове р-кой пользователей, и отдельная ЦИК для подсчета бюллетеней [1373].

(1) Каждый избиратель отправляет письмо в ЦУР, запрашивая регистрационный номер.

(2) ЦУР возвращает избирателю случайный регистрационный номер. ЦУР ведет список регистрационных номеров. Кроме того, ЦУР хранит список получателей регистрационных номеров на случай, если кто-то попытается проголосовать дважды.

(3) ЦУР отправляет список регистрационных номеров в ЦИК.

(4) Каждый избиратель выбирает случайный идентификационный номер. Он создает сообщение с этим ном ером, регистрационным номером, полученным в ЦУР, и своим бюллетенем. Он посылает это сообщение в

ЦИК.

(5) ЦИК проверяет регистрационные номера по списку, полученному от ЦУР на этапе (3). Если регистрац ионный номер есть в списке, ЦИК вычеркивает его (чтобы избежать повторного голосования). ЦИК доба в-ляет идентификационный номер к списку тех, кто проголосовал за определенного кандидата, и прибавляет единичку к соответствующему итоговому числу.

(6) После того, как все бюллетени будут получены, ЦИК публикует результаты вместе со списками, содерж а-щими идентификационные номера и соответствующие бюллетени.

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

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

Мэллори, не обладающий избирательными правами, может попытаться смошенничать, угадав правильный регистрационный номер. Угроза этого может быть минимизирована, если множество возможных регистрацио н-ных номеров намного больше, чем множество реальных регистрационных номеров : 100-битовое число для миллиона избирателей. Конечно же, регистрационные номера должны генерироваться случайным образом .

Несмотря на это, ЦУР должна быть заслуживающим доверия органом власти - ведь она может зарегистр и-ровать неправомочных избирателей. Она также может зарегистрировать правомочных избирателей несколько раз. Этот риск может быть сведен к минимуму, если ЦУР опубликует список зарегистрировавшихся избират елей (но без их регистрационных номеров). Если число избирателей в этом списке меньше, чем число подсчитанных бюллетеней, то что-то не так. Однако, если зарегистрировалось больше избирателей, чем было прислано бюллетеней, то это, возможно, означает, что ряд зарегистрировавшихся избирателей не проголосовал . Многие, зарегистрировавшись, не утруждаются бросить в урну свой бюллетень .

Этот протокол беззащитен перед сговором ЦИК и ЦУР. Если они действуют вместе, они могут объединить свои базы данных и узнать, кто за кого голосует.

Голосование с одной Центральной комиссией

Чтобы избежать опасности сговора между ЦУР и ЦИК можно использовать более сложный протокол [1373]. Этот протокол идентичен предыдущему с двумя изменениями :

- ЦУР и ЦИК являются единой организацией, и

- для анонимного распределения регистрационных номеров на этапе (2) используется ANDOS (см. раздел

4.13).

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

Улучшенное голосование с одной Центральной комиссией

В этом протоколе также используется ANDOS [1175]. Он удовлетворяет всем шести требованиям хорошего протокола голосования. Он не удовлетворяет седьмому требованию, но обладает двумя свойствами, дополня ю-щими перечисленные в начале раздела шесть свойств :

7. Избиратель может изменить свое мнение (т.е., аннулировать свой бюллетень и проголосовать заново) в течение заданного периода времени.

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

Вот этот протокол:

(1) ЦИК публикует список всех правомочных избирателей .

(2) В течение определенного срока каждый избиратель сообщает в ЦИК, собирается ли он голосовать .

(3) ЦИК публикует список избирателей, участвующих в выборах .

(4) Каждый избиратель получает идентификационный номер, /, с помощью протокола ANDOS.

(5) Каждый избиратель генерирует пару открытый ключ/закрытый ключ : к, d. If Если v - это бюллетень, то избиратель создает и посылает в ЦИК следующее сообщение :

I,Ek(I, v)

Это сообщение должно быть послано анонимно .

(6) ЦИК подтверждает получение бюллетеня, публикуя: Ek(l v)

(7) Каждый избиратель посылает ЦИК: I, d

(8) ЦИК расшифровывает бюллетени. В конце выборов она публикует их результаты и, для каждого варианта выбора, список соответствующий значений Ek(I, v).

(9) Если избиратель обнаруживает, что его бюллетень подсчитан неправильно, он протестует, посылая ЦИК : I, Ek(I, v), d

(10) Если избиратель хочет изменить свой бюллетень с v на v, он пос1лает ЦИК: I, Ek(I, v), d

Другой протокол голосования использует вместо ANDOS слепые подписи, но по сути мало чем отличается [585]. Этапы (1) - (3) являются предварительными. Их цель состоит в том, чтобы узнать и опубликовать всех действительных избирателей. Хотя некоторые из них, вероятно, не примут участи в голосовании, это уменьшает возможность ЦИК добавить поддельные бюллетени .

На этапе (4) два избирателя могут получить один и тот же идентификационный номер . Эта возможность может быть минимизирована, если число возможных идентификационных номеров будет гораздо больше, чем число реальных избирателей. Если два избирателя присылают бюллетени с одинаковым идентификатором, ЦИК генерирует новый идентификационный номер, I, выбирает одного из избирателей и публикует:

I,Ek(I, v)

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

Этап (6) дает каждому избирателю возможность проверить, что ЦИК правильно получила его бюллетень . Если его бюллетень неправильно подсчитан, он может доказать это на этапе ( 9). Предполагая, что бюллетень избирателя на этапе (6) правилен, сообщение, которое он посылает на этапе (9) доказывает, что его бюллетень был неправильно подсчитан.

Одной из проблем этого протокола является то, что жульническая ЦИК сможет воспользоваться людей, к о-торые сообщили о намерении голосовать на этапе (2), но не голосовали в действительности . Другой проблемой является сложность протокола ANDOS. Авторы рекомендуют разбивать избирателей на меньшие группы, н а-пример избирательные округа.

Еще одной, более серьезной проблемой является то, что ЦИК может не подсчитать какой-нибудь бюллетень . Эта проблема неразрешима: Алиса утверждает, что ЦИК намеренно пренебрег ее бюллетенем, а ЦИК утве р-ждает, что Алиса никогда не голосовала.

Голосование без Центральной избирательной комиссии

В следующем протоколе ЦИК не используется, избиратели следят друг за другом . Этот протокол, созданный Майклом Мерриттом [452, 1076, 453], настолько громоздок, что возможность его реализации больше чем для пяти человек сомнительна, но все же познакомиться с ним будет полезно .

Алиса, Боб, Кэрол и Дэйв голосуют (да/нет или 0/1) по какому-то вопросу . Пусть у каждого избирателя есть открытый и закрытый ключи. Пусть также все открытые ключи известны всем.

(1) Каждый голосующий решает, как голосовать, и делает следующее:

(a) Добавляет случайную строку к своему бюллетеню.

(b) Шифрует результат этапа (а) открытым ключом Дэйва.

(c) Шифрует результат этапа (b) открытым ключом Кэрол.