другой (кроме той, что может быть извлечена из значения /(а, Ь) и собственного секрета одной из сторон). Яо в качестве применения такого вычисления показал, что оно позволяет двум сторонам сотрудничать при выборе некоторого целого числа, которое, как им известно, является произведением в точности двух простых чисел так, что ни одна из сторон не сможет вычислить эти сомножители в том случае, когда они перестанут сотрудничать друг с другом [366]. См. также [232, 129, 130, 233].

Секретное распределенное вычисление естественным образом обобщается на произвольное число сторон. Криптографические решения обобщенной проблемы секретных распределенных вычислений были даны Одедом Голдрейчем, Сильвио Микэли и Эви Вигдерсоном [195], и независимо Дэвидом Чаумом, Иваном Дам-гардом и Йереоном ван де Граафом [112]. Зви Галил, Стюарт Хабер и Моти Юнг изучали секретные устойчивые к ошибкам протоколы в модели системы с открытым ключом [182]. Позднее и независимо Дэвидом Чаумом, Клодом Крепеу и Иваном Дамгардом в [111], а также Майклом Бен-Ором, Шафи Гольдвассер и Эви Вигдерсоном в [38] было показано, что безусловно секретные распределенные вычисления могут быть выполнены при одном-единственном предположении, что нечестными являются не более, чем одна треть от общего числа участников. См. также [301, 106].

Схема выборов является специальным случаем предыдущей проблемы. Как могут несколько сторон участвовать в голосовании по компьютерной сети таким образом, что будут в состоянии вычислить результат голосования, но при этом все индивидуальные бюллетени сохранятся в тайне? Этот вопрос изучался многими исследователями, включая Джоша Беналоха [Коэна] и Майкла Фишера [119], Майкла Бен-Ора и Натана Линиэла [39], а также и Беналоха и Моти Юнга [23].

Еще одна интересная задача - это вычисления с зашифрованными данными, которая основана на идее, сначала исследованной Джоэном Фейгенбаумом [174], и впоследствии усовершенствованной им совместно с соавторами [1]. В этой задаче Алиса хочет узнать значение f{x) некоторой открытой функции / от секретного аргумента х, но испытывает при этом недостаток ресурсов (или знаний), чтобы ее вычислить. У Боба же такие способности есть, и он хочет помочь Алисе. Функция / называется

шифруемой, если Алиса способна использовать Боба не только так, чтобы тот помог ей вычислить f{x), но и так, чтобы при этом Боб не смог узнать никакой информации об х, за исключением значения f{x). Жиль Брассар и Пауль Брэтли указали на прямую связь между этим понятием и техникой проектирования алгоритмов, которая известна под названием стохастическая предпосылка [77]. См. также [17, 255, 320, 73] и [74].

Множество других замечательных сведений о криптологии вы можете узнать также, если прочитаете [2, 48, 327, 252], или обратитесь к трудам «онференций CRYPTO, EUROCRYPT, FOCS и STOC или попробуете заглянуть в журналы Journal of Cryptology и Cryptologia. Кроме того, другие научные журналы регулярно публикуют специальные выпуски, посвященные криптологии. Смотрите, например, майский выпуск ТИИЭР 1988 года.

Глава 7

Квантовая криптография

(Нгшисина совместлр с Чирльзом X. Беннеттом)

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

§ 1. Введение

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