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

(e) Шифрует результат этапа (d) открытым ключом Алисы.

(f) Добавляет новую случайную строку к результату этапа (e) и шифрует получившееся открытым ключом Дэйва. Он записывает значение случайной строки.

(g) Добавляет новую случайную строку к результату этапа (f) и шифрует получившееся открытым ключом Кэрол. Он записывает значение случайной строки.

(h) Добавляет новую случайную строку к результату этапа (g) и шифрует получившееся открытым ключом Боба. Он записывает значение случайной строки.

(i) Добавляет новую случайную строку к результату этапа ( g) и шифрует получившееся открытым ключом Алисы. Он записывает значение случайной строки.

Если E - это функция шифрования, Ri - случайная строка, а V - бюллетень , то его сообщение будет выглядеть следующим образом:

Ea(R5,Eb(R4.Ec(R3.Ed(R2.Ea(Eb(Ec(Ed(V,Ri))))))))

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

(2) Каждый голосующий отправляет сообщение Алисе.

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

(4) Алиса перетасовывает все бюллетени и посылает результат Бобу. Теперь каждый бюллетень будет выглядеть следующим образом: Eb(R4,Ec(R3.Ed(,R2.Ea(Eb(Ec(Ed(V,Ri)))))))

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

Теперь каждый бюллетень будет выглядеть следующим образом: Ec(Rs,Ed(R2,Ea(Eb(Ec(Ed(V,Ri))))))

(6) Кэрол расшифровывает все бюллетени, используя свой закрытый ключ, проверяет, есть ли ее бюллетень среди присланных бюллетеней, удаляет все случайные строки на этом уровне, тасует бюллетени и посыл а-ет результат Дэйву.

Теперь каждый бюллетень будет выглядеть следующим образом: Ed(R2,Ea(Eb(Ec(Ed(V,Ri )))))

(7) Дэйв расшифровывает все бюллетени, используя свой закрытый ключ, проверяет, есть ли его бюллетень среди присланных бюллетеней, удаляет все случайные строки на этом уровне, тасует бюллетени и посыл а-ет результат Алисе.

Теперь каждый бюллетень будет выглядеть следующим образом: Ea(Eb(Ec(Ed(V,Ri ))))

(8) Алиса расшифровывает все бюллетени, используя свой закрытый ключ, проверяет, есть ли ее бюллетень среди присланных бюллетеней, подписывает все бюллетени и посылает результат Бобу, Кэрол и Дэйву.

Теперь каждый бюллетень будет выглядеть следующим образом:

Sa (Eb(Ec(Ed(V,Ri ))))

(9) Боб проверяет и удаляет подписи Алисы. Он расшифровывает все бюллетени, используя свой закрытый ключ, проверяет, есть ли его бюллетень среди присланных бюллетеней, подписывает все бюллетени и п о-сылает результат Алисе, Кэрол и Дэйву.

Теперь каждый бюллетень будет выглядеть следующим образом: Sb(,Ec(Ed(V,Ri )))

(10) Кэрол проверяет и удаляет подписи Боба. Она расшифровывает все бюллетени, используя свой закрытый

ключ, проверяет, есть ли ее бюллетень среди присланных бюллетеней, подписывает все бюллетени и п о-сылает результат Алисе, Бобу и Дэйву.

Теперь каждый бюллетень будет выглядеть сл едующим образом: Sc(,Ed(V,R,))

(11) Дэйв проверяет и удаляет подписи Кэрол. Он расшифровывает все бюллетени, используя свой закрытый ключ, проверяет, есть ли его бюллетень среди присланных бюллетеней, подписывает все бюллетени и п о-сылает результат Алисе, Бобу и Кэрол.

Теперь каждый бюллетень будет выглядеть следующим образом: Sd(V,R,)

(12) Все проверяют и удаляют подпись Дэйва. Они убеждаются, что их бюллетени находятся среди получе н-ных (находя свою случайную строку).

(13) Все удаляют случайные строки из каждого бюллетеня и суммирует бюллетени.

Этот протокол не только работает, он сам является своим арбитром . Алиса, Боб, Кэрол и Дэйв немедленно узнают, если кто-нибудь из них попытается мошенничать . Не нужно никаких ЦИК и ЦУР. Чтобы увидеть, как это работает, попытаемся смошенничать.

Если кто-нибудь пытается добавить бюллетень, Алиса обнаружит эту попытку на этапе (3), когда она получит бюллетеней больше чем количество людей, участвующих в голосовании . Если Алиса попытается добавить бюллетень, Боб обнаружит это на этапе (4).

Более ловкой является подмена одного бюллетеня другим . Так как бюллетени шифруются различными о т-крытыми ключами, каждый может создать столько правильных бюллетеней, сколько нужно . Протокол дешифрирования состоит из двух частей: первая включает этапы (3)-(7), а вторая - этапы (8)-(11). Подмена голоса на различных этапах обнаруживается по разному.

Если кто-нибудь заменит один бюллетень другим во второй части, его действия будут обнаружены неме д-ленно. На каждом этапе бюллетени подписываются и посылаются всем избирателям . Если один избиратель (или несколько) обнаруживает, что его бюллетеня больше нет среди набора бюллетеней , он немедленно прекращает выполнение протокола. Так как бюллетени подписываются на каждом этапе , и так как каждый может вернуться во второй части протокола на несколько шагов назад , то обнаружить мошенника, подменившего бюллетени, легко.

Замена одного бюллетеня другим в первой части протокола более тонка . Алиса не может сделать замену на этапе (3), потому что Боб, Кэрол и Дэйв обнаружат это на этапах (5), (6) или (7). Боб может попробовать на этапе (5). Если он заменит бюллетени Кэрол и Дэйва (помните, он не знает, какой бюллетень чей), Кэрол или Дэйв заметят это на этапах (6) или (7). Они не будут знать, кто подменил их бюллетени (хотя это должен быть кто-то, уже обработавший бюллетени), но они будут знать, что их голоса подменены. Если Бобу повезло, и ему удалось подменить бюллетень Алисы, она не заметит этого до второй части протокола. Тогда она обнаружит исчезновение своего голоса на этапе (8), но не сможет узнать, кто подменил бюллетень. В первой части бюллетени перетасовываются на каждом этапе и не подписываются, поэтому никто не сможет отработать протокол обратно и определить, кто подменил бюллетени.

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

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

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

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

Другие схемы голосования

Было предложено много сложных безопасных протоколов выборов . Их можно разделить на два типа. Существуют протоколы с перемешиванием, как "Голосование без Центральной избирательной комиссии", в которых все бюллетени перемешиваются, чтобы никто не мог связать бюллетень и избир ателя.

Также существуют протоколы с разделением , в которых личные бюллетени делятся между различными счетными комиссиями так, что ни одна из них не сможет обмануть избирателей [360, 359, 118, 115]. Эти иро-токолы Эти протоколы защищают анонимность избирателей только, если различные "части" правительства (или кто бы не проводил голосование) не сговариваются против избирателя. (Идея разбить центральный орган на несколько частей, которые пользуются доверием, только когда они действуют параллельно, пришла из [316].)

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

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

Еще один, более сложный протокол, решающий некоторые из этих проблем можно найти в [770, 771]. Существует даже протокол, использующий шифры со многими ключами [219]. Другой протокол, который, как утверждается, подходит для крупномасштабных выборов, приведен в [585]. А [347] позволяет избирателям не голосовать.

Протоколы голосования работают, они даже облегчают продажу и покупку голосов . Когда покупатель может быть уверен, что продавец проголосует, как обещал, стимул купить голоса становится еще сильнее . Ряд протоколов были спроектированы без подтверждения, не позволяя избирателю доказать кому-либо еще, что он пр о-голосовал определенным образом [117, 1170, 1372].

6.2 Безопасные вычисления с несколькими участниками

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

Протокол №»l

Как может группа людей вычислить свою среднюю зарплату без того, чтобы зарплата одного стала известна другому?

(1) Алиса добавляет секретное случайное число к сумме своей зарплаты, шифрует результат открытым кл ю-чом Боба и посылает его Бобу.

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

(3) Кэрол расшифровывает результат своим закрытым ключом. Она добавляет сумму своей зарплаты к пол ученному от Боба значению, шифрует результат открытым ключом Дэйва и посылает его Дэйву.

(4) Дэйв расшифровывает результат своим закрытым ключом. Он добавляет сумму своей зарплаты к пол ученному от Кэрол значению, шифрует результат открытым ключом Алисы и посылает его Алисе.

(5) Алиса расшифровывает результат своим закрытым ключом. Она вычитает случайное число, прибавленное на этапе (1), получая сумму всех зарплат.

(6) Алиса делит результат на число людей (в данном случае на четыре) и объявляет результат.

Этот протокол подразумевает, что каждый участник честен - они хотя и могут любопытствовать, но следуют протоколу. Если любой из участников солжет о своей зарплате, средняя зарплата будет рассчитана неправильно. Более серьезная проблема состоит в том, что Алиса может искажать итоговый результат. Она может вычесть на этапе (5) любое число, которое ее устраивает, и никто об этом не узнает. Помешать Алисе сделать это можно, потребовав от нее вручить ее случайное число с помощью одной из схем вручения бита из раздела 4.9, но когда