Отправитель и получатель. Сообщения и шифрование 13 глава

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

I,E_k(I, v)

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

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

E_k(I, v)

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

I, d

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

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

I, E_k(I, v), d

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

I, E_k(I, v'), d

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

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

I',E_k(I, v)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

E_A(R₅,E_B(R₄,E_C(R₃,E_D(R₂,E_A(E_B(E_C(E_D(V,R₁ ))))))))

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

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

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

(4) Алиса перетасовывает все бюллетени и посылает результат Бобу.

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

E_B(R₄,E_C(R₃,E_D(R₂,E_A(E_B(E_C(E_D(V,R₁ )))))))

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

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

E_C(R₃,E_D(R₂,E_A(E_B(E_C(E_D(V,R₁ ))))))

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

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

E_D(R₂,E_A(E_B(E_C(E_D(V,R₁ )))))

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

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

E_A(E_B(E_C(E_D(V,R₁ ))))

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

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

S_A (E_B(E_C(E_D(V,R₁ ))))

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

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

S_B(E_C(E_D(V,R₁ )))

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

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

S_C(E_D(V,R₁ ))

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

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

S_D(V,R₁ )

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

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

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

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

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

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

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

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

Более того, из-за начальной случайной строки, R₁, даже одинаковые бюллетени шифруются по разному на каждом этапе протокола. Никто не может узнать значение бюллетеня до этапа (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, но когда она откроет свое случайное число в конце протокола Боб сможет узнать ее зарплату.

Протокол №2

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

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

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

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

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

Протокол №3

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

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

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

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

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

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

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

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

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

Протокол №4

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

Следующие два примера иллюстрируют процесс голосования. Пусть участвуют пять обычных избирателей, от N₁ до N₅, и два суперизбирателя: S₁ и S₂. Вот голосование по вопросу №1:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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