автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Разработка и исследование интерактивного алгоритма обработки информации для протоколов квантовой криптографии

Курицын Константин Александрович

Разработка и исследование интерактивного алгоритма обработки информации для протоколов квантовой криптографии

Специальность:

05.13.01 - Системный анализ, управление и обработка информации (в технике и технологиях)

Автореферат диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург 2007

003068338

Работа выполнена в Государственном образовательном учреждении высшего. профессионального образования «Санкт-Петербургский государственный университет аэрокосмического приборостроения» (ГУАП) на кафедре информационных систем

Научный руководитель:

кандидат технических наук,

доцент Шехунова Наталия Александровна

Официальные оппоненты: доктор технических наук,

профессор Коржик Валерий Иванович, кандидат физико-математических наук, доцент Горбачев Валерий Николаевич

Ведущая организация: Санкт-Петербургский институт информатики РАН (СПИИРАН)

Защита состоится ч.&Я/ъ 2007 года в 15 часов, на заседании

диссертационного совета Д212.233.02 при Государственном образовательном учреждении высшего профессионального образования « Санкт-Петербургский государственный университет аэрокосмического приборостроения» по адресу: 190000, Санкт-Петербург, ул.Б.Морская, 67, ГУАП

С диссертацией можно ознакомиться в библиотеке ГУАП

Автореферат разослан

Ученый секретарь диссертационного совета /

доктор технических наук, профессор • /®сипов Л-А.

Общая характеристика работы

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

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

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

Работами, положившими начало развитию раздела квантовой информации, называемому квантовой криптографией, стали статьи Визнера (Wiesner), Бен-нета (Bennett) и Брассара (Brassard), Экерта (Ekert.), Дойча (Deutch), Мермина (Merinin) и др. В 1984 году сотрудничество Веннета и Брассара, которые основывались на идее Визнера, привело к появлению первого протокола "квантового распределения ключа". Их основная идея состояла в том, чтобы использовать неортогональные квантовые состояния для распределения ключа, поскольку такие состояния не могут быть клонированы потенциальным злоумышленником. В этой работе они использовали четыре различных состояния квантовых частиц, и поэтому их схема получила название схемы с четырьмя состояниями. В 1991 году Экерт, основываясь на идеях Дойча, предложил использовать квантовую нелокальность для криптографических целей. В соответствии с его предложениями Беннетом, Брассаром и Мермином была представлена схема

квантового распределения ключа. Их версию схемы Экерта часто называют ЭПР схемой (Эйнштейн, Подольский, 'Розен). Другая важная работа, выполненная позднее Беннетом, показала, что квантовая схема распределения ключа может быть реализована с использованием только двух неортоголальных состояний. Эта схема получила название схемы с двумя состояниями. Обе эти схемы могут быть использованы для реализации протокола распределения закрытого ключа по открытому каналу, получившего название протокола квантового распределения ключа.

Каждый из известных протоколов квантового распределения ключа включает в себя два этапа: *

• передача квантовых частиц по квантовому каналу;

• открытую передачу информации о полученной/переданной последовательности квантов по дискретному (в частности, двоичному) каналу.

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

Практический интерес к квантовой криптографии заключается в следующем: математической базой современной криптографии (криптографии с открытыми ключами) являются задачи, которые в терминах теории сложности алгоритмов принадлежат классу ИР, т.е. являются "трудными". Сегодня алгоритмы и протоколы, построенные на основе этих задач, обладают вычислительной секретностью. По крайней мере часть из них обеспечивает высокий уровень защиты информации в различных ситуациях: распределения закрытых ключей по открытым каналам, обеспечения секретности, аутентификации и целостности информации. Однако стремительное развитие вычислительной техники, интенсивные исследования в области построения эффективных алгоритмов решения задач из класса NР (в частности ТУР-полных задач), результаты теории квантовых вычислений могут сделать реальным решение "трудных" задач с полиномиальной сложностью в обозримом будущем. Надежность систем квантовой криптографии определяется не вычислительной сложностью какой-либо "трудной" задачи, а основополагающим принципом квантовой механики: всякое измерение, выполненное над квантовой системой, меняет ее состояние и тем самым обнаруживается.

Основными проблемами при разработке протоколов квантового распределения ключа являются

• высокая вероятность ошибки (порядка нескольких процентов) в последовательности, переданной по квантовому каналу, что значительно превышает уровень ошибок в обычных коммуникациях;

• необходимость исправлять ошибки двух типов: символьные и фазовые. Применение помехоустойчивых кодов, исправляющих такого рода ошибки (например, кодов над 24), приводит к увеличению числа вычислений, требуемых для реализации протокола, и может привести к увеличению утечки информации из-за высокой избыточности.

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

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

В соответствии с поставленной целью были определены следующие задачи:

1. Исследование алгоритмов обработки информации в протоколах квантового распределения ключа.

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

3. Анализ качества протокола квантового распределения ключа при исполь -зовании в нем предложенного алгоритма обработки информации;

4. Получение количественных оценок качества предложенного алгоритма.

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

Научная новизна работы. Выносимые на защиту результаты обладают существенной научной новизной и впервые получены в данной диссертационной работе. В частности:

1. Проведен анализ интерактивных алгоритмов обработки информации в протоколах квантовой криптографии и построены количественные оценки

стойкости протоколов

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

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

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

математического моделирования.

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

На защту выносятся следующие основные результаты:

1. Алгоритм обработки информации, использующий интерактивное взаимодействие участников.

2. Количественные оценки для алгоритма обработки информации в открытом канале в протоколах квантового распределения ключа.

3. Доказательство безусловной секретности эквивалентного протокола квантового распределения ключа с использованием интерактивного алгоритма.

4. Результаты анализа работы протокола распределения ключа в системе квантовой криптографии с использованием предложенного алгоритма обработки информации.

Апробация работы. Основные результаты работы докладывались и обсуждались па следующих российских и международных конференциях:

• IX Российской научно-технической конференции "Методы и технические средства обеспечения безопасности информации" —• Санкт-Петербург, Россия, 2001;

• EURESCO conference on Quantum Information—San Feliu de Guixols, Spain,

2002;

• International Workshop on Quantum Computation and Learning — Riga, Latvia, 2002;

• International Symposium" Quantum Informatics-2002" —Zvenigorod, Russia 2002;

• XI Российской научно-технической конференции "Методы и технические

средства обеспечения безопасности информации" — Санкт-Петербург, Россия, 2003;

• ежегодных научных сессиях аспирантов — Санкт-Петербург, Россия, 2001-2004;

• XV Российской научно-технической конференции "Методы и технические средства обеспечения безопасности информации" Санкт-Петербург, Россия, 2006.

б

Основные результаты работы неоднократно обсуждались на научных семинарах лаборатории квантовой информации, ГУАП. Часть результатов использована в научно-исследовательских работах, проводимых на кафедрах информационных систем и высшей математике по следующим темам: 1.2.02 "Теоретические исследования коллективных явлений в задачах квантовой оптики" и 1.1.00 "Разработка теоретических основ построения и методов исследования сложных систем передачи информации".

Публикации. По теме диссертации опубликовано 11 работ, из них 6 статей в научных журналах и сборниках научных статей, 5 тезисов докладов на научных конференциях.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений. Диссертация изложена на 160 страницах. Работа содержит 20 рисунков и 6 таблиц. Список используемых источников включает 103 наименования.

Содержание работы

Во введении обоснована актуальность исследования, определены цели и задачи работы. Сформулированы научные положения, выносимые на защиту, определена их научная новизна и практическая значимость, приведены сведения об апробации и внедрения результатов работы.

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

Квантовое распределение ключа начинается с пересылки одиночного или перепутанных квантов между отправителем (Алисой) и получателем (Бобом). Подслушивание, с физической точки зрения, основано на серии экспериментов, которые подслушивающий выполняет на носителях информации, в данном случае на пересылаемых квантах. Согласно правилам квантовой механики, в общем случае любое измерение, выполняемое злоумышленником (Евой), неизбежно меняет состояние передаваемых квантов, и Алиса, и Боб могут это выяснить в последующей открытой связи. Таким образом, основные составляющие квантового распределения ключа таковы: квантовый канал для обмена квантами и так называемый открытый канал, который используется, чтобы проверить, искажено ли сообщение, переданное через квантовый канал. Любой

Боб

Базисы измерений Боба ООПОВППОВЕЭООВО Результаты намерений Боба 1001 0011000100 Просаяяные биты 1СС1 С0С1ООС1С О

Рис. 1: Принцип распределения ключа, использующий протокол ВВ84.

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

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

Рассмотрим импульсы поляризованного света, причем в каждом импульсе содержится по одному фотону, состояние поляризации которого может быть описано в базисе прямоугольной поляризации в виде а|<->) + /Щ), гДе 1аР(1/3|2) — вероятность обнаружения фотона в состоянии с горизонтальной (вертикальной) поляризацией. Чтобы передать информацию, необходима кодирующая система, которая, например, |<->) кодирует 0 и Ц) кодирует 1. Чтобы добиться конфиденциальности, Алиса добавляет еще один случайный выбор: она посылает либо предыдущие прямоугольные поляризации в базисе ф, либо одну из двух диагональных линейных поляризаций, причем \У) обозначает 1, а |\) обозначает 0 (эти поляризации соответствуют базису ®) (рис. 1).

Протокол квантового распределения ключа, предложенный Бепнетом и Брас-саром и использующий поляризационные состояния фотонов, выглядит следующим образом:

1. Алиса случайным образом выбирает базис А € {ф, <Е>} и поляризацию своих исходных фотонов и посылает их Бобу.

2. Для каждого импульса Боб также случайным образом выбирает базис, который он будет использовать, и измеряет импульс. Он либо регистрирует отсчет на одном из двух детекторов, либо ничего не регистрирует из-за потерь при связи или при детектировании. Последовательность всех полученных битов называется сырым ключом.

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

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

Квантовое распределение ключа с помощью перепутанных состояний выполняется через квантовый канал, который состоит из источника, испускающего пару фотонов в сгтглетном поляризационном состоянии |Ф~) = ^О«-*}!!) — |~>Ц)). Наличие злоумышленника определяется путем анализа уровня рассогласования результатов измерения фотонов законными участниками. Беннетом показана информационная эквивалентность протоколов распределения ключа при передаче одиночными квантами и перепутанными частицами.

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

Основной составляющей данной схемы является бинарный поиск ошибки. Данный алгоритм способен обнаружить ошибку в строках, которые имеют нечетное число ошибок. Число бит, которыми необходимо обменяться пользователям во время обнаружения и поиска ошибки в строке длиной п бит, составляет 1 + [log п]. После обработки блока с помощью бинарного поиска ошибки в нем

содержится четное число ошибок или не содержится вовсе. Вероятность нахождения в нем ошибок определяется начальной вероятностью битовой ошибки в строках Алисы и Боба. Для определения того, остались ли в обработанных блоках А и В ошибки, Алиса и Боб s раз применяют процедуру проверки, которая заключается в сравнении четностей случайных битовых подмножеств. В случае несовпадения четностей подмножеств протокол завершается неуспехом. В работе показано, что вероятность обнаружения ошибки (в случае, если они там есть) при каждой итерации составляет 1/2. После успешного завершения протокола вероятность нахождения в блоках Л и В ошибок составляет 2~".

В интерактивный схеме, предложенной Беннетом и*Сэлвейлом, Алиса и Боб разбивают свои строки на блоки, называемые первичными, длина каждого из которых равна к. Для каждого первичного блока пользователи применяют процедуру проверки наличия ошибки, и в случае обнаружения ее в подмножестве, применяют к нему бинарный поиск ошибки. На следующем этапе г > 1 Алиса и Боб формируют рабочие блоки путем объединения двух блоков, образованных на предыдущем этапе протокола. Для каждого из рабочих блоков они выполняют протокол проверки наличия ошибки г раз. Каждый раз, когда ошибка обнаружена, Алиса и Боб могут либо исправлять ошибку, либо заменять все биты первичного блока Боба, содержащего ошибочный бит, соответствующими битами первичного блока Алисы. Протокол продолжается до тех пор, пока на текущем этапе г не будет сформирован единственный рабочий блок: г = \п/к].

Пусть п — длина просеянного ключа. Среднее число ошибок после г-го этапа протокола обнаружения и исправления ошибок е? и число ошибок перед началом протокола равно е?' = ет. Каждая итерация обнаружения ошибки и исправления начинается с разделения просеянного ключа на строки, так что среднее число ошибок в каждом рабочем блоке не превышает заданный параметр д. Число блоков в строках Алисы и Боба равно jW = [еу^'/р] > и Длина блока на ¿-ом этапе составляет = п /J».

В работе показано, что среднее число ошибок, обнаруженных во время г-го шага протокола, в;1' ~ (1 — е~2в) ¡2д, и число ошибок, оставшееся после г-го шага, составляет е^ = — е[г' ~ (2д — 1 + е-2-) /2р. Выражение в скобках есть функция только одного аргумента ¡3 = ¡3(g).

Исправление ошибок прекращается, если на следующем этапе при формировании блоков необходимо создать два и менее блоков. Таким образом, число шагов протокола Ni до его завершения должно удовлетворять неравенству 1) < 2, откуда Ni ^ [log (2д/ер) / log/?].

На шаге проверки протокола взаимодействия продолжаются до тех пор, пока не произойдет N2 последовательных итерации, в которых не будет обнаружено ошибки. В данной работе показано, что количество итераций, в которых ошибка не обнаруживается, составляет iVj ~ JV2 + 2д, число взаимодействий,

1,0

>>

0,0 -•-•--——i-•-•-•-—■-•----1--1—

. 0,00 0,05 0,10 0,15

Вероятность битовой ошибки e

Рис. 2: Количество информации, утекающей злоумышленнику в зависимости от уровня ошибок при использовании базового протокола (ijp), протокола, предложенного в данной работе (/£), теоретико-информационного минимума (Щ1П) и результата моделирования предложенного протокола (/£), усредненное по результатам 50-ти запусков протокола на строках длиной 100000 бит.

обнаруживающих ошибку, равно Щ — 2Q.

Поскольку вся информация, которой законные пользователи обмениваются через открытый канал, становится доступной злоумышленнику и может быть им использована для раскрытия секретного ключа, можно предполагать, что эта информация может рассматриваться как информация, утекающая злоумышленнику. Доля информации, которую протокол предоставляет злоумышленнику, является важной характеристикой протокола. Известно, что нижняя граница для количества информации, утекающей к злоумышленнику, составляет = nh (еР/п).

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

токола на каждой итерации утекает один бит четности для каждого из из JW блоков и [log&W] бит для каждого из блоков, в которых обнаружена ошибка. На втором этапе один бит становится доступным злоумышленнику для каждой итерации, не выявляющей ошибку, и 1 + [log fc^] бит — в каждой итерации, обнаруживающей ошибку. Общее количество информации, которую получает злоумышленник в процессе обнаружения и исправления ошибок, составляет

*.........

'1° = £ +1°£ k^ef) + Щ + Ni

i=l

1 + log -

На рис. 2 показано сравнение количества Информации, доступной злоумышленнику, при применении протокола исправления ошибок, предложенного Бен-нетом и Сэлвейлом, по сравнению с теоретическим минимумом. Отношение количества информации, доступной злоумышленнику, к теоретико-информационному минимуму отлично от единицы даже при очень малых значениях вероятности битовой ошибки с, поскольку обмен четностями блоков происходит и в отсутствие ошибок в ключевой последовательности. При изменении уровня ошибок от 2% до 10%, отношение /|с/увеличивается от 1.2 до 1.4, что указывает на то, что протокол позволяет получать Еве на 20% — 40% информации больше, чем теоретический минимум. (При построении сравнения использовались следующие параметры протокола: д = 0.5 и Л^ = 30, длина ключевой последовательности составляла п = 105 бит.)

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

Протокол 1 Шаг алгоритма г = 1

1. Формирование рабочих блоков, на которых будет осуществляться поиск ошибки. Количество блоков щ. Упорядоченное множество номеров блоков, содержащих нечетное число ошибок, /Сг = 0. Число обработанных блоков на этапе г: = 0.

2. Определение номера этапа для блоков которого необходимо выполнять

поиск ошибки: г или первый этап, для которого К? Ф 0. Определение

номера рабочего блока к, в котором необходимо искать ошибку — первый

номер блока из К.У (если КУ ф %) или па (если п^ + 1 > щ, то г = г + 1 и переход к п. 1, иначе = п^ + 1).

3. Поиск ошибки в блоке с номером к. Если ошибочный бит I обнаружен, то , для всех этапов т < г, для которых 1Г < Па- + 1: К.Т — (К7 и 1Г) \ (Кг П ¡г), где 1Т - номер блока на этапе г, содержащего бит I. Переход к п. 2.

Пусть на этапе г > 1 в блоке К^1 законные участники обнаружили ошибочный бит I. Алиса и Боб исправляют бит I во всех блоках предыдущих этапов протокола. Далее, произведя поиск ошибки в блоке первого этапа, содержащего бит /, они обнаруживают ошибочный бит I'. Это означает, что во всех блоках 1 < ,7 < г и во всех блоках К^, q < г> Алиса и Боб могут исправить ошибочный бит. Если на этапе ] бит Г попадет в тот же блок, что и бит; I, то это не привнесет вклад в дополнительный поиск ошибки, поскольку у Алисы и Боба этот блок будет иметь одинаковую четность (исправлены два бита I и I'). Если па этапе г второй ошибочный бит V попадет в блок с номером д > у, то это также не привнесет вклад в поиск ошибки, связанной с обработкой блока К ¡'К

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

из этапов ~ 1 + е|=1 ^ Е (1 - • При обнаружении

3=1 4

одной ошибки в рабочем блоке текущего этапа протокола пользователи "дополнительно" исправляют — 1 ошибок. На рис. 3 представлены зависимость числа исправляемых ошибок в строках при обнаружении ошибки в блоке от его номера и зависимость числа ошибок в строках от номера обрабатываемого блока.

На первом этапе алгоритма исправления ошибок для каждого блока Алиса и Боб сравнивают четности, что требует обмена битами четности. Общее количество битов четности, которыми обмениваются Алиса и Боб, составляет бит. Для каждого блока, в котором Алиса и Боб обнаруживают ошибку, они применяют бинарный поиск, который требует обмена взаимодействий Алисы и Боба. На этапе г > 1 Алиса и Боб, как и на первом этапе, сравнивают четности битов блоков текущего этапа протокола исправления ошибок, но в отличие от базового протокола, не все биты, которыми обмениваются пользователи, дают вклад в утечку информации злоумышленнику. При поиске парных ошибок в уже обработанных блоках их четности известны, и в случае нахождения в них ошибок на предыдущих шагах протокола известны четности отдельных его частей. Это заключение уменьшает число бит, дающих вклад в общую информацию Евы о просеянном ключе. При обработке блока К^1 число бит, утекающих Еве может быть ограничено сверху: /¡с. < ^ _ 25р.')) + 2>М + дгМ ^(0 _ ^ | где _ вероятность обнаружения ошибки в блоке Первое слагаемое связано с проверкой четности

блоков этапа г, а второе слагаемое связано с обнаружением ошибок на текущем этапе и последующих Л^1'"' пар ошибок, которые обнаруживаются на этапах 2 < г, так что к^ <

40

30

■з га о.

5> 20

0

1 10

■г

/=■1

2000

500 1000 1500 2000

Обрабатываемый блок, (¡-IVе" + V

Рис. 3: Зависимость Л^''"' и числа ошибок в просеянном ключе от номера обрабатываемого блока.

На рис. 2 показана зависимость количества Информации, доступной злоумышленнику, от начального уровня ошибок в ключевой последовательности. До уровня начальной вероятности битовой ошибки в 15% предложенный алгоритм открывает злоумышленнику не более, чем на 20% больше, чем это возможно теоретически, что в два раза лучше, чем у известного, и позволяет исправлять ошибки в ключевой последовательности, содержащих до 25% ошибок, при этом, не компрометируя ключевую последовательность полностью.

В третьей главе рассматривается доказательство безусловной секретности протоколов квантового распределения ключей, использующих интерактивное согласование.

В работе Ло и Чау показано, что если Алиса и Боб обладают набором пар кубитов (ЭПР-пар), находящихся в максимально перепутанном состоянии с ка-

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

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

В процедуре одностороннего очищения перепутывания каждый локальный оператор, который применяют Алиса и Боб, является либо оператором X типа, либо Z типа. Если все операторы коммутируют друг с другом и не зависят от результата предыдущих измерений, то появляется возможность перемещения всех М^х измерений после М^г измерений. Возможность разделения исправления битовых и фазовых ошибок приводит к тому, что Алиса и Боб могут разделить протокол согласования ключа па этапы, которые могут рассматриваться независимо друг от друга. Односторонняя схема очищения перепутывания, которая допускает разделение исправления битовых и фазовых ошибок, может быть приведена при помощи использования КШС-кодов (Калдербанк, Шор, Стин) к схеме согласования ключа, используемой в протоколе ВВ84.

Если битовые ошибки в просеянном ключе исправляются при помощи линейного кода С\, проверочная матрица которого равна Я1, а фазовые ошибки исправляются при помощи кода С^ , где С2 С Сь то операторы ф^У1*1^ и

® коммутируют. Проверочная матрица кода Сг имеет вид ^ ^ ) > гДе

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

В двухсторонней схеме очищения перепутывания Алиса и Боб используют

интерактивное взаимодействие, представленное в виде классических сообщений (которыми участники обмениваются через открытый канал) результатов проведения локальных общих измерений. При использовании интерактивной схемы согласования ключа Алиса и Боб разбивают просеянный ключ на блоки, для каждого из которых они применяют бинарный поиск ошибки, сравнивая четности отдельных его подмножеств. Это соответствует проведению ряда операций билатерального СКОТ в ¿-базисе. Предположим, Алиса и Боб измеряют Z® Z над двумя ЭПР-парами путем применения операции билатерального С^ЮТ: Алиса применяет логический элемент СКОТ, используя в качестве контрольного кубита кубит первой ЭПР-пары, а в качестве 'кубита-мншени — кубит второй пары. Боб производит аналогичное действие в том же базисе над своими кубитами. Затем Алиса и Боб открыто сравнивают результаты и в случае наличия ровно одной битовой ошибки получают противоположные результаты. В результате проведения этой операции над набором ЭПР-пар, Алиса и Воб получают множество ЭПР-пар, уровень битовой ошибки в которых ниже, чем начальный. Однако уровень фазовой ошибки в них оказывается большим, поскольку в квантовых лох-ических элементах СКОТ фазовые ошибки в кубите-мишени действуют обратно на контрольный кубит. Для исправления фазовых ошибок Алиса и Боб могли бы аналогичным образом производить X ® X измерения над парами ЭПР-пар. Для этого им следует произвести поворот базиса, в котором фазовые ошибки становятся битовыми. Это действие может быть выполнено при помощи операции Адамара. Затем Алиса и Боб снова выполняют операцию билатерального СКОТ и возвращают ЭПР-пары в исходный базис при помощи преобразования Адамара. Оставшаяся часть ЭПР-пар будет содержать меньшее количество битовых и фазовых ошибок, чем начальный набор. При использовании бинарного поиска ошибки Алисе и Бобу на некотором этапе приходится производить И измерение некоторого кубита (т.е. определять значение ошибочного бита). Если процедура согласования ключа затем должна ис-иравить фазовую ошибку соответствующего кубита, то она должна содержать X компоненту для него. Разделение исправления битовых и фазовых ошибок в данном случае ограничивается локальной коммутативностью операторов, которые используются для исправления ошибок.

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

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

Предположим, что в результате применения протокола двухстороннего очищения перепутывания Алиса и Боб обладают п ЭПР-парами, в которых исправлены битовые ошибки. Для исправления фазовых ошибок Алиса и Боб согласовывают гхп матрицу проверки четности Яг некоторого линейного кода

п .

Далее Алиса и Боб вычисляют г операторов Мх,= ® (Х,-)( /-)'> и сравнивают измеренные значения и Значения М^ по отношению к ¿, г = 1,..., г дают г синдромов фазовой ошибки, и с помощью кода С2 Алиса и Боб исправляют фазовые ошибки. После выполнения этой операции Алиса и Боб обладают п ЭПР-парами, которые находятся в максимально перепутанном состоянии с высоким качеством (определяется протоколом очищения перепутывания и кодом С2 и может быть сделано сколь угодно близким к единице). Согласно теореме Ло-Чау, законные участники могут произвести измерения в вычислительном г-базисс для получения секретного ключа, информация злоумышленника о котором будет пренебрежимо мала.

Для получения секретного ключа Алиса и Боб производят 2 измерения над каждым кубитом ЭПР-пар и получают одинаковые строки ш. В качестве матрицы усиления секретности Алиса и Боб используют пхг матрицу проверки четности <3 дуального к С2 кода и получают г-битный секретный ключ Полученный таким образом протокол ВВ84 с интерактивным согласованием ключа является безусловно секретным, поскольку соответствует с точки зрения утечки информации протоколу квантового распределения ключа с очищением перепутывания.

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

Результаты моделирования на ЭВМ находятся в хорошем соответствии с полученной во второй главе оценкой. На рис. 2 показана зависимость количества

Работа Год Протокол Расстояние, Интенсивность Скорость генерации, Вероятность битовой Утечки информации

канал А бит/с ошибки, % г гЕС 1Е г-/Iе

Бевнет и др. 1992 ВВ84 32 см, РБ 0.12 3.3 4.0 78.73 26.78 51.95

Якобе и др. 1906 ВВ84 150 м, РЭ 0.20 1000 2.0 87.36 15.36 72.00

Баттлер и др. 1998 В92 205 м, РЭ 0.70 50 6.0 55.88 36.70 19.18

Якобе и др. 1995 В92 1 км, ОР 0.30 6000 0.4 94.03 03.92 90.11

Мюллер и др. 1996 В92 23 км, ОР 0.12 15 3.4 81.54 23.53 58.01

Риборди и др. 1998 ВВ84 23 км, ОР 0.10 210 1.0 93.93 08.60 85.33

Хыогс и др. 2000 В92 24 км, ОР 0.40 5 1.6 85.06 ,12.72 72.34

Таблица 1: Характеристики различных реализаций протоколов квантового распределения ключа и результаты согласования чернового ключа. Канал РЭ — свободное пространство, ОР — оптическое волокно.

информации, утекающей злоумышленнику при исправлении ошибок в зависимости от вероятности битовой ошибки.

Проведены оценки по количеству утечки информации при использовании предложенного алгоритма в различных используемых системах протокола квантового распределения ключа. Результаты данных исследований приведены в табл. 1.

В заключении сформулированы основные результаты, полученные в диссертационной работе:

• Исследованы интерактивные методы обработки информации для протоколов квантовой криптографии и построены статистические оценки их качества.

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

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

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

• Выполнено моделирование предложенной схемы исправления ошибок, произведены оценки использования предложенного метода для реальных квантово-криптографических систем (id Quantique, MagiQ Technologies и др.).

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

Основные публикации по теме диссертации

1. Курицын К.Л. Современные системы квантового распределения ключа // Проблемы информационной безопасности, Компьютерные системы, 4, 2006.

2. Курицын К.А. Безусловная секретность протокола распределения квантового ключа в схемах с интерактивным согласованием // Седьмая научная сессия аспирантов ГУАП: Сб. докл. в 2 ч. 4.1. Технические науки, - СПб.: СПбГУАП, 2004.

3. Курицын К.А. Секретность протоколов распределения квантового ключа с интерактивным согласованием // Проблемы информационной безопасности, Компьютерные системы, 5, 2003.

4. Курицын К.А. Безусловная секретность протокола распределения квантового ключа // Методы и технические средства обеспечения безопасности. Материалы конференции, Санкт-Петербург, 26-27 ноября 2003.

5. Курицын К.А. Схема согласования секретного ключа для кйантовой криптографии // Шестая научная сессия аспирантов ГУАП: Сб. докл. в 2 ч. 4.1. Технические науки, - СПб.: СПбГУАП, 2003.

6. Kuritsyn К. Secret-key agreement by public discussion // Quantum Computation and Learning. Proc. of Int. Workshop, Riga, Latvia, 25-26 May 2002.

7. Kuritsyn K. Interactive scheme of secret key reconciliation // "Quantum informatics", Proc. of SPIE, Proc. of the Symposium on quantum informatics «QI-2002», Lipki, 1-3 October 2002.

8. Курицын К.А. Протокол согласования секретного ключа // Пятая научная сессия аспирантов ГУАП: Сб. докл. в 2 ч. 4.1. Технические науки, -СПб.: СПбГУАП, 2002.

9. Курицын К.А., Савельев М.Ф. Согласование секретного ключа через открытый канал // Проблемы информационной безопасности, Компьютерные системы, 3, 2001.

10. Курицын К.А. Открытое обсуждение при согласовании секретного ключа // Методы и технические средства обеспечения безопасности. Тезисы докладов, Санкт-Петербург, 8-9 октября 2001.

11. Курицын К.А. Сравнительный анализ протоколов квантовой криптографии // Четвертая научная сессия аспирантов ГУАП: Сб. докл. в 2 ч. 4.1. Технические науки, - СПб.: СПбГУАП, 2001.

Формат 60x84 1416 .Бумага офсетная. Печать офсетная. Тираж 1р0 экз. Заказ лИ8Ц

Редакционно-нздагалыжий центр ГУАП 190000, Санкт-Петербург, Б. Морская ул., 67

Введение

1. Алгоритмы обработки информации для протоколов квантовой криптографии

1.1. Введение.

1.2. Квантовый канал

1.2.1. Квантовое распределение ключа с одиночными частицами

1.2.2. Квантовое распределение ключа с помощью перепутанных состояний.

1.3. Открытый канал.

1.3.1. Исправление ошибок

1.3.2. Усиление секретности.

1.4. Экспериментальные реализации.

1.5. Выводы по главе.

2. Разработка и исследование каскадного алгоритма обработки квантовой информации

2.1. Протокол согласования ключа.

2.1.1. Интерактивная схема обработки информации.

2.1.2. Алгоритм обработки информации, основанный на каскадной схеме.

2.1.3. Аиализ базового интерактивного алгоритма.

2.1.4. Анализ интерактивного алгоритма, основанного на каскадной схеме.

2.2. Выводы по главе.

3. Оценка качества протокола согласования ключа 90 3.1. Введение.

3.1.1. Критерий секретности.

3.2. Секретность протокола против некогерентных атак.

3.3. Секретность протокола против когерентных атак.

3.3.1. Качество перепутывания.

3.3.2. Коды, исправляющие квантовые ошибки и КШС-коды

3.3.3. Протокол на основе КШС-кода.

3.3.4. Протокол на основе перепутанных состояний.

3.3.5. Выделение перепутывания.

3.3.6. Приведение протокола с очищением перепутывания к протоколу ВВ84.

3.4. Выводы по главе.

4. Моделирование

4.1. Количественные оценки для реальных применений.

4.2. Моделирование.

4.3. Выводы по главе.

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

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

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

Работами, положившими начало развитию раздела квантовой информации, называемому квантовой криптографией, стали статьи Визнера (Wiesner) [1], Беннета (Bennett) и Брассара (Brassard), Экерта (Ekert), Дойча (Deutch), Мер-мина (Mermin) и др. В 1984 году сотрудничество Беннета и Брассара, которые основывались на идее Визнера, привело к появлению первого протокола "квантового распределения ключа" [2]. Их основная идея состояла в том, чтобы использовать неортогональные квантовые состояния для распределения ключа, поскольку такие состояния не могут быть клонированы потенциальным злоумышленником. В этой работе они использовали четыре различных состояния квантовых частиц, и поэтому их схема получила название схемы с четырьмя состояниями. В 1991 году Экерт, основываясь на идеях Дойча, предложил использовать квантовую нелокальность для криптографических целей [3]. В соответствии с его предложениями Беннетом, Брассаром и Мермином была представлена схема квантового распределения ключа [4]. Их версию схемы Экерта часто называют ЭПР схемой (Эйнштейн, Подольский, Розен). Другая важная работа [5], выполненная позднее Беннетом, показала, что квантовая схема распределения ключа может быть реализована с использованием только двух неортогональных состояний. Эта схема получила название схемы с двумя состояниями. Обе эти схемы могут быть использованы для реализации протокола распределения закрытого ключа по открытому каналу, получившего название протокола квантового распределения ключа.

Каждый из известных протоколов квантового распределения ключа включает в себя два этапа:

• передача квантовых частиц по квантовому каналу;

• открытую передачу информации о полученной/переданной последовательности квантов по дискретному (в частности, двоичному) каналу.

Эффективным протоколом является тот, который в квантовом канале обеспечивает безусловную секретность [6] передачи информации, в открытом канале — минимальную среднюю взаимную информацию между легальными пользователями протокола и злоумышленником (утечку информации), и при этом для своей реализации требует минимального количества вычислений.

Практический интерес к квантовой криптографии заключается в следующем: математической базой современной криптографии (криптографии с открытыми ключами) являются задачи, которые в терминах теории сложности алгоритмов принадлежат классу МР, т.е. являются "трудными" [7, 8, 9, 10]. Сегодня алгоритмы и протоколы, построенные на основе этих задач, обладают вычислительной секретностью. По крайней мере часть из них обеспечивает высокий уровень защиты информации в различных ситуациях: распределения закрытых ключей по открытым каналам, обеспечения секретности, аутентификации и целостности информации. Однако стремительное развитие вычислительной техники, интенсивные исследования в области построения эффективных алгоритмов решения задач из класса NP (в частности NP-пoлныx задач), результаты теории квантовых вычислений могут сделать реальным решение "трудных" задач с полиномиальной сложностью в обозримом будущем [11]. Надежность систем квантовой криптографии определяется не вычислительной сложностью какой-либо "трудной" задачи, а основополагающим принципом квантовой мехаг ники: всякое измерение, выполненное над квантовой системой, меняет ее состояние и тем самым обнаруживается.

Основными проблемами при разработке протоколов квантового распределения ключа являются

• высокая вероятность ошибки (порядка нескольких процентов) в последовательности, переданной по квантовому каналу, что значительно превышает уровень ошибок в обычных коммуникациях;

• необходимость исправлять ошибки двух типов: символьные и фазовые. Применение помехоустойчивых кодов, исправляющих такого рода ошибки (например, кодов над СР(4)), приводит к увеличению числа вычислений, требуемых для реализации протокола, и может привести к увеличению утечки информации из-за высокой избыточности.

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

Целью настоящего исследования является построение эффективного алгоритма обработки информации в открытом канале для протокола квантового распределения ключа (согласования), а также анализ надежности протокола квантового распределения ключа на основе предложенного алгоритма.

В соответствии с поставленной целью были определены следующие задачи:

1. Исследование алгоритмов открытого согласования ключа в протоколах квантового распределения;

2. Разработка и анализ интерактивного алгоритма обработки информации в открытом канале;

3. Анализ надежности протокола квантового распределения с использованием предложенного алгоритма (доказательство безусловной секретности протокола);

4. Количественные оценки эффективности предложенного алгоритма.

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

Научная новизна результатов, полученных в диссертации, заключается в том, что в ней впервые:

1. Проведен анализ интерактивных алгоритмов обработки информации для протоколов квантовой криптографии и построены количественные оценки эффективности таких протоколов.

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

3. Произведены количественные оценки утечки информации и эффективности предложенного протокола.

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

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

Научные положения, выносимые на защиту.

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

2. Количественные оценки для интерактивных схем согласования в протоколах квантового распределения ключа.

3. Доказательство безусловной секретности эквивалентного протокола квантового распределения ключа с предложенным алгоритмом обработки.

4. Результаты анализа эффективности протокола с использованием предложенного алгоритма.

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих российских и международных конференциях:

• IX Российской научно-технической конференции "Методы и технические средства обеспечения безопасности информации" — Санкт-Петербург, Россия, 2001;

• EURESCO conference on Quantum Information — San Feliu de Guixols, Spain, 2002;

• International Workshop on Quantum Computation and Learning — Riga, Latvia, 2002;

• International Symposium "Quantum informatics-2002" — Zvenigorod, Russia, 2002;

• XI Российской научно-технической конференции "Методы и технические средства обеспечения безопасности информации" — Санкт-Петербург, Россия, 2003;

• ежегодных научных сессиях аспирантов — Санкт-Петербург, Россия, 2001— 2003;

• XIV Российской научно-технической конференции "Методы и технические средства обеспечения безопасности информации" — Санкт-Петербург, Россия, 2006.

Основные результаты работы неоднократно обсуждались на научном семинаре лаборатории квантовой информации, С-ПбГУАП.

Публикации. По теме диссертации опубликовано 11 работ, из них б статей в научных журналах и сборниках научных статей, 5 тезисов докладов на научных конференциях.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений. Диссертация изложена на

4.3. Выводы по главе

В данной главе проведено моделирование предложенного во второй главе алгоритма согласования ключа. Результаты моделирования подтвердили правильность аналитических выводов (4.2). Проведены оценки по количеству утечки информации при использовании предложенного алгоритма в различных используемых системах протокола квантового распределения ключа. Результаты данных исследований приведены в табл. 4.2.

1. С.Н. Bennett and G. Brassard "Quantum cryptography: public key distribution and coin tossing". 1. Proc. IEEE Int. Conference on Computers, Systems and Signal Processing. IEEE (1984).

2. Д. Бауместер, А. Экерт, and А. Цайлингер "Физика квантовой информации". М. Постмаркет (2002).

3. S. Wiesner "Conjugate Coding". SIGACT News, 15, 78 (1983).

4. A.K. Ekert "Quantum cryptorgraphy based on Bell's theorem". Phys. Rev. Lett., 67, 661 (1991).

5. C.H. Bennett, G. Brassard, and N.D. Mermin "Quantum Cryptography without Bell's theorem". Phys. Rev. Lett., 68, 557 (1992).

6. C.H. Bennett "Quantum cryptography using any two nonorthogonal states". Phys. Rev. Lett., 68, 3121 (1992).

7. C.E. Shannon "Communication Theory of Secrecy Systems". Bell Syst. Tech. J., 28, 656-715 (1949).

8. W. Diffie and M. Hellman "New Directions in Cryptrography". IEEE Trans. Inf. Theory, 22, 644-654 (1976).

9. M.R. Garey and D.S. Johnson "Computers and Intractability, A Guide to the Theory of NP- Completeness" (1979).

10. A. Salomaa "Computation and automata". Encyclopedia of mathematics and its applications, 25, (1989).

11. A. Galindoy and M.A. Martin-Delgadoz "Information and Computation: Classical and Quantum Aspects". Reviews of Modern Physics to apperar (2001). Online. Los Alamos preprint arhive: quant-ph/0112105.

12. P.Shor "Proc. of 35th Annual Symposium on the Foundations of Computer Science". 124 (1994). Extended Abstract.

13. J. von Neumann "Mathematical Foundations of Quantum Mechanics". Princeton Univ. Press (1955).

14. A.C. Холево "Некоторые оценки количества информации, передаваемого квантовым каналом связи". Пробл. пер. инф., 9,(3) 3-11 (1973).

15. А.С. Холево "Границы для количества информации, передаваемого квантовым каналом связи". Пробл. пер. инф., 9,(3) 110 (1973).

16. Е. В. Davies "Information and quantum measurement". IEEE Trans. Inf. Theory, 24, 596 (1978).

17. L.B. Levitin. Proc. of the Workshop on Phys. of Сотр.: PhysComp 92, volume 74, 210. IEEE Computer Science (1993).

18. C.W. Helstrom "Quantum Detection and Estimation Theory". Academic Press, New York (1976).

19. A. Peres "Quantum Theory: Concepts and Methods". Kluwer Academic Publishers (1995).

20. B. Schumacher "Quantum coding". Phys. Rev. A, 51,(4) 2738 (1995).

21. R. Josza and B. Schumacher "A new proof of the quantum noiseless coding theorem". J. Mod. Opt., 41, 2343 (1994).

22. A. Peres and W.K. Wootters "Optimal detection of quantum information". Phys. Rev. Lett., 66, 1119 (1991).

23. S.L. Braunstein and C.M. Caves 'Wringing out better Bell inequalities". Phys. Rev. Lett., 72, 3439 (1994).

24. C.A. Fuchs and C.M. Caves "Ensemble-dependent bounds for accesible information in quantum mechanics". Phys. Rev. Lett., 73, 3047 (1994).

25. C.M. Caves and P.D. Drummond "Quantum limits of bosonic communication rates". Rev. Mod. Phys., 66, 481 (1994).

26. W.K. Wootters and W.H. Zurek "A single quantum can not be cloned". Nature (London), 299, 802 (1982).

27. C.H. Bennett, F. Bessette, G. Brassard, L. Salvail, and J. Smolin "Experimental Quantum Cryptography". J. Cryptoi, 5, 3-28 (1992).

28. C.H. Bennett, G. Brassard, S. Breidbart, and S. Wiesner "Quantum Cryptography, or unforgeable subway tokens". In Proc. Crypto 82, 267-275 (1982).

29. C. Marand and P.D. Townsend "Quantum key distribution over distances as long as 30 km". Opt. Lett., 20,1695 (1995).

30. A. Muller, H. Zbinden, and N. Gisin "Underwater quantum coding". Nature (London), 378, 449 (1995).

31. B. Huttner, N. Imoto, N. Gisin, and T. Mor "Quantum cryptography with coherent states". Phys. Rev. A, 51, 1863 (1995). Online. Los Alamos preprint arhive: quant-ph/9502020.

32. H.P. Yuen "Quantum amplifiers, quantum duplicators and quantum cryptography". Quan. Sem. Opt., 8, 939 (1996).

33. C.H. Bennett, G. Brassard, and J.M. Robert "Privacy amplification by public discussion". Siam J. Comp., 17, 210 (1988).

34. C.H. Bennett, G. Brassard, C. Crépeau, and U.M. Maurer "Generalized Privacy Amplification". In IEEE Int. Symph. on Information Theory, June 27 — July 1, Norway (1994).

35. В. Huttner and А.К. Ekert "Information gain in quantum eavesdropping". J. Mod. Opt., 41, 2455 (1994). Online. Los Alamos preprint arhive: quant-ph/9904038.

36. A.K. Ekert, J.G. Rarity, P.R. Tapster, and G.M. Palma "Practical quantum cryptography based on two-photon interferometry". Phys. Rev. Lett., 69, 1293 (1992).

37. J.F. Clauser, M.A. Home, A. Shimony, and R.A. Holt "Proposed experiment to test local hidden-variable theories". Phys. Rev. Lett., 23, 880 (1969).

38. C. Macchiavello "Universal transformations for infinite dimensional quantum systems". Phys. Rev. Lett, 246, 385 (1998).

39. К. Шеннон "Работы no теории информации и кибернетике". М. Изд. ин. лит. (1963).

40. J.L. Carter and M.N. Wegman "Universal classes of hash functions". Journal of Computer and System Sciences, 18,143-154 (1979).

41. A. R6nye "On measures of entopy and information". Proceedings of 4th Berkley Symphosium on Mathematical Statistics and Probability, 1, 547-561 (1961).

42. G. Ribordy, J.D. Gautier, H. Zbinden, and N. Gisin "Performance of InGaAsInP avalanche photodiodes as gatedmode photon counters". Appl. Opt., 37, 2272 (1998).

43. A. Muller, J. Breguet, and N. Gisin "Experimental demonstration of quantum cryptography using polarized photons in optical fibre over more than 1 km". Europhys. Lett., 23, 383 (1993).

44. R.Y. Chiao and Y.S. Wu "Practical quantum cryptography based on two-photon interferometry". Phys. Rev. Lett., 57, 933 (1986).

45. B.C. Jacobs and J.D. Franson "Quantum cryptography in free space". Opt. Lett., 21, 1854 (1996).

46. W.T. Buttler, R.J. Hughes, P.G. Kwiat, S.K. Lamoreaux, G.G. Luther, G.L. Morgan, J.E. Nordholt, C.G. Peterson, and C.M. Simmons "Free-Space

47. Quantum Key Distribution". Phys. Rev. A, 57, 2379-2382 (1998). Online. Los Alamos preprint arhive: quarit-ph/9805071.

48. P.D. Townsend, S.J.D. Phoenix, K.J. Blow, and S.M. Barnett "Design of QC systems for passive optical networks". El. Lett., 30, 1875-1876 (1994).

49. G. Ribordy, J.D. Gautier, N. Gisin, O. Guinnard, and H. Zbinden "Automated plug and play quantum key distribution". El. Lett., 34, 2116-2117 (1998). Online. Los Alamos preprint arhive: quant-ph/9812052.

50. J.D. Franson and B.C. Jacobs "Operational system for quantum cryptography". El. Lett., 31, 232 (1995).

51. J.G. Rarity, P.C.M. Owens, and P.R. Tapster "Quantum randomnumber generation and key sharing". Phys. Rev. Lett., 73, 1923 (1994).

52. W. Tittel, J. Brendel, B. Gisin, T. Herzog, H. Zbinden, and N. Gisin "Experimental demonstration of quantum correlations over more than 10 kilometers". Phys. Rev. A, 57, 3229 (1998). Online. Los Alamos preprint arhive: quant-ph/9707042.

53. W. Tittel, J. Brendel, H. Zbinden, and N. Gisin "Violation of Bell inequalities by photons more than 10 km apart". Phys. Rev. Lett., 81, 3563 (1998). Online. Los Alamos preprint arhive: quant-ph/9806043.

54. P.G. Kwiat, H. Weinfurter, T. Herzog, and A. Zeilinger "Interaction-free measurement". Phys. Rev. Lett., 74, 4763 (1995).

55. Y.H. Kim, M.V. Chekhova, S.P. Kulik, M. Rubin, and Y.H. Shih "Interferometric Bell states preparation using femtosecond pulse pumped spontaneous parametric down-conversion". Phys. Rev. A, 63, 062301 (2001).

56. Y.H. Kim, S.P. Kulik, and Y. Shih "Bell states preparation using pulses nondegenerate two-photon entanglement". Phys. Rev. A, 63, 060301 (2001).

57. G. Weihs, T. Jennewein, C. Simon, H. Weinfurter, and A. Zeilinger "Violation of Bell's inequality under strict Einstein locality conditions". Phys. Rev. Lett., 81, 5039-5043 (1998). Online. Los Alamos preprint arhive: quant-ph/9810080.

58. G. Brassard and L. Salvail "Secret-Key Reconciliation by Public Discussion". In Eurocrypt '93, Lofthus, Norway (1993).

59. W.T. Buttler, R.J. Hughes, S.K. Laraoreaux, G.L. Morgan, J. E. Nordholt, and C.G. Peterson "Daylight quantum key distribution over 1.6 km". Phys. Rev. Lett., 84, 5652-5655 (2000). Online. Los Alamos preprint arhive: quant-ph/0001088.

60. R.J. Hughes, G.L. Morgan, and C.G. Peterson "Quantum key distribution over a 48km optical fibre network". J. Mod. Opt., 47, 533-547 (2000).

61. W.T. Buttler, S.K. Lamoreaux, J.R. Torgerson, G.H. Nickel, C.H. Donahue, and C.G. Peterson "Fast, efficient error reconciliation for quantum cryptography" (2003). Online. Los Alamos preprint arhive: quant-ph/0203096.

62. D.E. Knuth "Seminumerical Algorithms". Addison-Wesley, Reading (1969).

63. M. N. Wegman and J.L. Carter "New hash functions and their use in authentication and set equality". J. Comp. Syst. Sciences, 22, 265 (1981).

64. G. Gilbert and M. Hamrick "Practical Quantum Cryptography: A Comprehensive Analysis (Part One)". Technical report, MITRE (2000). Online. Los Alamos preprint arhive: quant-ph/0009027.

65. H.-K. Lo "Method for decoupling error correction from privacy amplification". New Journal of Physics, 5, 36.1-36.24 (2003).

66. D. Mayers "Quantum key distribution and string oblivious transfer in noisy channels". In Advances in Cryptology — Proc. Crypto'96, 343. Springer, New York (1996).

67. D. Mayers "Unconditional security in quantum cryptography". J. Assoc. Comp. Mach48, 351-406 (2001).

68. E. Biham, M. Bqyer, P.O. Boykin, T. Mor, and Roychowdhury "A proof of security of quantum key distribution". In Proc. 32nd Annual ACM Symp. on Theory of Computing, 715. ACM, New York (2000).

69. M. Ben-Or. In presentation at Introductory Workshop in Quantum Computation (2002). {OnlineJ: http://zeta.msri.org/calendar/talks/Talklnfo/1416/show talk.

70. H.-K. Lo and H.F. Chau "Unconditional security of quantum key distribution over arbitrarily long distances". Science, 283, 2050-2056 (1998). Online. Los Alamos preprint arhive: quant-ph/9803006.

71. C.H. Bennett, D.P. DiVincenzo, J.A.Smolin, and W.K. Wootters "Mixed State Entanglement and Quantum Error Correction". Phys. Rev. A, 54, 3824 (1996). OnlineJ Los Alamos preprint arhive: quant-ph/9604024.

72. C.H. Bennett, G. Brassard, S. Popescu, B. Schumacher, J.A. Smolin, and W.K. Wootters "Purification of noisy entanglement and faithful teleportation via noisy channels". Phys. Rev. Lett., 76, 722-725 (1996).

73. P.W. Shor and J. Preskill "Simple proof of security of the BB84 quantum key distribution scheme". Phys. Rev. Lett., 85, 441-444 (2000).

74. H.-K. Lo "Method for decoupling error correction from privacy amplification" (2002). Online. Los Alamos preprint arhive: quant-ph/0201030.

75. B.A. Slutsky, R. Rao, P.-C. Sun, and Y.Fainman "Defense frontier analysis of quantum cryptographic systems". Phys. Rev. A, 57, 2383 (1998).

76. C. Gilbert and M. Hamrick "Constraints on Eavesdropping on the BB84 Protocol" (2001). Online. Los Alamos preprint arhive: quant-ph/0106034.

77. F.J. MacWilliams and N.J.A. Sloan 'The Theory of Error-Correcting Code". Amsterdam: North-Holland (1977).

78. D. Mayers "Unconditionally Secure Quantum Bit Commitment is Impossible". Phys. Rev. Lett., 78, 3414-3417 (1997).

79. D. Mayers "Unconditional security in Quantum Cryptography" (1998). Online. Los Alamos preprint arhive: quant-ph/9802025.

80. P.O. Boykin "Information Security and Quantum Mechanics: Security of Quantum Protocols". Ph.d. thesis (2002). Online. Los Alamos preprint arhive: quant-ph/0210194.

81. A.M. Steane "Error correcting codes in quantum theory". Phys. Rev. Lett., 77, 793-797 (1996).

82. A.R. Calderbank and P.W. Shor "Good quantum error-correcting codes exist". Phys. Rev. A, 54, 1098-1105 (1996). Online. Los Alamos preprint arhive: quant-ph/9512032.

83. N. Liitkenhaus "Estimates for practical quantum cryptography". Phys. Rev. A, 59, 3301-3319 (1999). Online. Los Alamos preprint arhive: quant-ph/9806008.

84. A. Muller, H. Zbinden, and N. Gisin "Quantum cryptography over 23km in installed under-lake telecom fiber". Europhys. Lett., 33, 335 (1996).

85. J.I. Cirac and N. Gisin "Coherent eavesdropping strategies for the four state quantum cryptography protocol". Phys. Rev. A, 299, 1 (1997).

86. G. Gilbert, M. Hamrick, and F.J. Thayer "Privacy Amplification in Quantum Key Distribution Pointwise Bound versus Average Bound". Technical report, MITRE (2001). Online. Los Alamos preprint arhive: quant-ph/0108013.

87. C.A. Fuchs and J. van de Graaf "Cryptographic distinguishability measures for quantum-mechanical states" (1997). Online. Los Alamos preprint arhive: quant-ph/9712042.

88. C.H. Bennett, G. Brassard, С. Сгёреаи, and U.M. Maurer "Generalized Privacy Amplification". IEEE Trans. Inf. Theory, 41, 1915-1923 (1995).

89. A. Steane "Multiple Particle Interference and Quantum Error Correction" (1996). Online. Los Alamos preprint arhive: quant-ph/9601029.i. В.Д. Колесник and E.T. Мирончиков "Декодирование циклических кодов". М.: Связь (1968).

90. Дж. Мак-Вильямс and Дж. Слоэн "Теория кодов, контролирующих ошибки". М.: Связь (1979).

91. К.А. Курицын "Сравнительный анализ протоколов квантовой криптографии". Четвертая научная сессия аспирантов ГУАП: Сб. докл. в 2 ч. 4.1. Технические науки, СПб.: СПбГУАП (2001).

92. К.А. Курицын "Современные системы квантового распределения ключа". Проблемы информационной безопасности, Компьютерные системы (2006). (принято к публикации).

93. К. Kuritsyn "Secret-key agreement by public discussion". Quantum Computation and Learning. Proc. of Int. Workshop, Riga, Latvia. Springer, New York (2002).

94. К.А. Курицын "Схема согласования секретного ключа для квантовой криптографии". Шестая научная сессия аспирантов ГУАП: Сб. докл. в 2 ч. 4.1. Технические науки, СПб.: СПбГУАП (2003).

95. К.А. Курицын "Открытое обсуждение при согласовании секретного ключа". Методы и технические средства обеспечения безопасности. Тезисы докладов. 8-9 октября 2001 (2001).

96. К.А. Курицын "Interactive scheme of secret key reconciliation". "Quantum informatics", Proc. of SPIE, Proc. of the Symposium on quantum informatics <QI-2002>. Lipki, 1-3 October 2002 (2002).

97. К.А. Курицын and М.Ф. Савельев "Согласование секретного ключа через открытый канал". Проблемы информационной безопасности, Компьютерные системы, 3, (2001).

98. К.А. Курицын "Протокол согласования секретного ключа". Пятая научная сессия аспирантов ГУАП: Сб. докл. в 2 ч. 4.1. Технические науки, -СПб.: СПбГУАП (2002).

99. К.А. Курицын "Секретность протоколов распределения квантового ключа с интерактивным согласованием". Проблемы информационной безопасности, Компьютерные системы, 5, (2003).

100. К.А. Курицын "Безусловная секретность протокола распределения квантового ключа в схемах с интерактивным согласованием". Седьмая научная сессия аспирантов ГУАП: Сб. докл. в 2 ч. 4.1. Технические науки, СПб.: СПбГУАП (2004).

101. К.А. Курицын "Безусловная секретность протокола распределения квантового ключа". Методы и технические средства обеспечения безопасности. Материалы конференции. Санкт-Петербург, 26-27 ноября 2003 (2003).