Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
Еще одна интересная задача — это вычисления с зашифрованными данными, которая основана на идее, сначала исследованной Джоэном Фейгенбаумом [174], и впоследствии усовершенствованной им совместно с соавторами [1]. В этой задаче Алиса хочет узнать значение f(x) некоторой открытой функции / от секретного аргумента х, но испытывает при этом недостаток ресурсов (или знаний), чтобы ее вычислить. У Боба же такие способности есть, и он хочет помочь Алисе. Функция / называется
Дополнительные применения 125
шифруемой, если Алиса способна использовать Боба не только так, чтобы тот помог ей вычислить 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. Введение
Когда для пересылки цифровой информации применяются такие элементарные квантовые системы, как поляризованные фотоны, то использование принципа неопределенности Гейзенберга позволяет достичь совершенно нового криптографического феномена, который абсолютно недостижим для обычных средств передачи информации. Например, можно получить такой канал связи, в котором в принципе невозможно какое бы то ни было прослушивание без наличия таких нарушений при передаче, которые не были бы обнаружены с очень большой вероятностью. Посред-
Введение 127
ством такого канала достигается одно из основных преимуществ криптографии с открытым ключом: он позволяет осуществить безопасное распределение ключей между Алисой и Бобом, которые первоначально не обладали никакой совместно используемой секретной информацией, при условии, что они имеют доступ, кроме квантового, еще и к обычному каналу, который допускает не только пассивное прослушивание, но и активную фальсификацию. (Более того, распределение секретных ключей можно выполнить даже при наличии активного фальсификатора, если Алис а и Боб при этом с самого начала используют некоторую совместную секретную информацию, но при условии, что фальсификация не настолько активна, чтобы полностью подавить всю связь.) Возникающий в результате соответствующих действий сторон квантовый канал является вероятностно секретным даже для противника с более передовой компьютерной технологией и имеющего неограниченные вычислительные ресурсы (и даже если, все-таки, V = AfV!), при единственном условии, что в этом процессе не нарушаются коренным образом общепризнанные физические законы.
В традиционной теории информации и криптографии считается не требующим доказательств то, что цифровая связь может всегда пассивно просматриваться или копироваться даже лицом, которое не осведомлено об информации, которая передается. Это может быть полезно, например, тому, кто надеется быть способным вычислить (или разузнать) секретный ключ в дальнейшем по прошествии какого-то времени, возможно, после того, как будет накоплен достаточный объем шифртекста. В противоположность этому, когда информация закодирована в неортогональных квантовых состояниях, например, в одиночных фотонах с направлениями поляризации 0°, 45°, 90° и 135°, то получается такой канал связи, что почта в нем даже в принципе не может с достоверностью ни читаться, ни копироваться нарушителем, не знающим некую информации о ключе, которая используется при формировании пересылаемого сообщения. Нарушитель не может извлечь никакой частичной информации об этой пересылке, позволяющей отличить ее от случайной, и таким способом, который не поддавался бы контролю и который не смогли бы обнаружить законные пользователи канала.
Недостаток подобного подхода на практике заключается в
128 Квантовая криптография
