она откроет свое случайное число в конце протокола Боб сможет узнать ее зарплату. Протокол №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-нет. Они не обязаны использовать эти "супер-бюллетени" и, если хотят, могут воспользоваться обычными бюллетенями. Если никто не использует "супер-бюллетени", то вопрос решается простым большинством голосов. В случае применения одного или двух эквивалентных "супербюллетеней" все обычные голоса игнорируются. В случае двух противоречащих вопрос решается большинством обычных голосов. Нам нужен протокол, который надежно осуществляет такую форму голосования.

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

Si S2 N1 N2 N3 N4 N5

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

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

Si S2 N1 N2 N3 N4 N5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

нарушить анонимность плательщика? Чаум решает проблему:

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

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

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

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

(1) Пользователи упорядочиваются по кругу.

(2) Через регулярные интервалы времени соседние пары пользователей бросают между собой монету, испол ь-зуя какой-нибудь безопасный от злоумышленников протокол бросания "честной" монеты .

(3) После каждого броска каждый пользователь объявляет либо "одинаковые", либо "разные" .

Если Алиса хочет передать широковещательное сообщение, она просто начинает инвертировать свое утве р-ждение в тех раундах, которые соответствуют 1 в двоичном представлении ее сообщения. Например, если ее сообщение б1ло "1001", она инвертирует ее утверждение, сообщит правду, сообщит правду, и затем инвертир у-ет снова утверждение. При условии, что результатом ее бросков было были "разные", "одинаковые", "одинаковые", "одинаковые", она будет говорить "одинаковые", "одинаковые ", "одинаковые", "разные".

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

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

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

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