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

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

Также существуют протоколы с разделением, в которых личные бюллетени делятся между различными счетными комиссиями так, что ни одна из них не сможет обмануть избирателей [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, но когда

она откроет свое случайное число в конце протокола Боб сможет узнать ее зарплату. Протокол №2

Алиса и Боб вместе в ресторане и спорят о том, кто старше. Никто, однако, не хочет сообщить другому свой возраст. Каждый из них мог бы прошептать свой возраст на ушко доверенной нейтральной стороне (например, официанту), кто мог бы сравнить числа в уме и объявить результат и Алисе, и Бобу.

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

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

Конечно, этот протокол не защитит от активных мошенников. Ничто не сможет помешать Алисе (или Бобу, какая разница) солгать о своем возрасте. Если бы Боб был компьютерной программой, которая слепо следовала бы протоколу, Алиса могла бы узнать его возраст (является ли возрастом компьютерной программы отрезок времени с момента ее написания или с момента ее запуска?), повторно выполняя протокол. Алиса могла бы ук а-зать, что ее возраст - 60 лет. Узнав, что она старше, она могла бы выполнить протокол снова, указав, что ее во з-раст - 30 лет. Узнав, что Боб старше, она могла бы снова выполнить протокол, указав, что ее возраст - 45 лет, и так далее, пока Алиса не узнает возраст Боба с любой нужной ей степенью точности.

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

Протокол №3

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

В Службе безопасных вычислений с несколькими участниками мы спроектировали протокол для подобных людей. Мы занумеровали впечатляющий список их пристрастий от "африканских муравьедов" до "яблочных пирогов". Разделенные модемной линией связи, Алиса и Боб могут участвовать в безопасном протоколе с н е-сколькими участниками. Они вместе могут определить, есть ли у них общие привычки . Если есть, они могли бы устремиться к обоюдному счастью . Если нет, то они могли бы безопасно расстаться, сохраняя уверенность, что их привычки остались в тайне . Никто, даже Служба безопасных вычислений с несколькими участниками, ник о-гда не узнает об их пристрастиях.

Вот как это работает:

(1)С помощью однонаправленной функции Алиса хэширует свою привычку как семизначную строку .

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

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

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

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

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

Протокол №4

Вот другая проблема для безопасных вычислений со многими участниками [1373]: совет семи регулярно

встречается, чтобы тайно проголосовать по некоторым вопросам. (Все в порядке, они управляют миром - не говорите никому, что я вам проговорился.) Все члены совета могут голосовать "да" или "нет". Кроме того, две стороны обладают "супер-бюллетенями": 5-да и 5-нет. Они не обязаны использовать эти "супер-бюллетени" и, если хотят, могут воспользоваться обычными бюллетенями. Если никто не использует "супер-бюллетени", то вопрос решается простым большинством голосов. В случае применения одного или двух эквивалентных "супербюллетеней" все обычные голоса игнорируются. В случае двух противоречащих вопрос решается большинством обычных голосов. Нам нужен протокол, который надежно осуществляет такую форму голосования.

Следующие два примера иллюстрируют процесс голосования . Пусть участвуют пять обычных избирателей , от N1 до N5, и два суперизбирателя: S1 и S2. Вот голосование по вопросу №1:

StS2NN2N3N4N5

Супер-да нетнетнетнетдада

В этом примере действует только один "супер-бюллетень" S1, и результат голосования - "да". А вот голосование по вопросу №2:

StS2NN2N3N4N5

Супер-да Супер-нет нетнетнетдада

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

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

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

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

Это только частный случай общей теоремы: любая функция с n входами может быть вычислена n игроками способом, который позволит всем узнать значение функции, но любое количество игроков, меньшее, чем n/2, не сможет получить никакой дополнительной информации, не следующей из их собственных входов и результата вычислений. Подробности можно найти в [136, 334, 1288, 621].

Безопасная оценка схемы

Вход Алисы - а, а Боба - b. Они вместе хотят вычислить некоторую функцию f(a,b) так, чтобы Алиса не смогла ничего узнать о входе Боба, а Боб - о входе Алисы. Главная проблема безопасных вычислений с н е-сколькими участниками также называется безопасной оценкой схемы. Алиса и Боб могут создать произвол ь-ную логическую схему. Эта схема получает на вход значения Алисы и Боба и выдает результат . Безопасная оценка схемы является протоколом, который реализует следующие три требования :

1.Алиса может ввести свое значение так, что Боб не сможет его узнать .

2.Боб может ввести свое значение так, что Алиса не сможет его узнать .

3.И Алиса, и Боб могут вычислить результат, причем обе стороны будут убеждены в том, что результат правилен и не подтасован ни одной стороной .

Детали протокола безопасной оценки схемы можно найти в [831].

6.3 Анонимная широковещательная передача сообщений

Вам не удастся пообедать с компанией криптографов и не оказаться среди ожесточенной перепалки . В [321] Дэвид Чаум вводит Проблему обедающих криптографов :

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

Как криптографам Алисе, Бобу и Кэрол узнать, не заплатил ли за обед кто-нибудь из них, и в то же время не