Введение к работе
Актуальность проблемы. Теория квантовой информации объединяет в себе идеи классической теории информации и квантовой физики. Наиболее продвинутыми на сегодняшний день в этой теории являются разделы, относящиеся к квантовым вычислениям и квантовой криптографии. Именно в этих разделах получены серьезные теоретические результаты. Что касается приложений этих результатов на практике, то наибольший прогресс достигнут в квантовой криптографии. Уже сегодня на рынке высоких технологий представлены устройства, позволяющие реализовать протоколы квантовой криптографии (в основном протоколы квантового распределения ключа) в реальных коммуникациях. Это означает, что теория квантовой информации имеет конкретное прикладное значение в области инфокоммуникационных технологий.
Типовыми задачами теории квантовой информации являются разработка и исследование различных алгоритмов обработки информации. В части квантовой криптографии речь, как правило, идет о таких алгоритмах обработки информации, которые позволяют обеспечить уменьшение средней взаимной информации между отправителем и получателем сообщения, которая доступна подслушивающему. В теории квантовой информации эту величину принято называть утечкой информации.
Следует заметить, что использование этих алгоритмов не ограничивается использованием их в протоколах квантовой криптографии или при обработке информации квантовыми вычислителями. В классической теории информации эти алгоритмы полезны для использования их в высокоскоростных системах с обратной связью, при построении алгоритмов обработки информации в системах и сетях связи. Однако, в настоящее время основной областью использования подобных алгоритмов обработки, информации являются протоколы квантовой информации.
Работами, положившими начало развитию раздела квантовой информации, называемому квантовой криптографией, стали статьи Визнера (Wiesner), Бен-нета (Bennett) и Брассара (Brassard), Экерта (Ekert), Дойча (Deutch), Мермина (Mermin) и др. В 1984 году сотрудничество Беннета и Брассара, которые основывались на идее Визнера, привело к появлению первого протокола "квантового распределения ключа". Их основная идея состояла в том, чтобы использовать неортогональные квантовые состояния для распределения ключа, поскольку такие состояния не могут быть клонированы потенциальным злоумышленником. В этой работе они использовали четыре различных состояния квантовых частиц, и поэтому их схема получила название схемы с четырьмя состояниями. В 1991 году Экерт, основываясь на идеях Дойча, предложил использовать квантовую нелокалыюсть для криптографичесюгх целей. В соответствии с его предложениями Беннетом, Брассаром и Мермином была представлена схема
'-,3
квантового распределения ключа. Их версию схемы Экерта часто называют ЭПР схемой (Эйнштейн, Подольский, 'Розен). Другая важная работа, выполненная позднее Беннетом, показала, что квантовая схема распределения ключа может быть реализована с использованием только двух пеоргоголальных состояний. Эта схема получила название схемы с двумя состояньями. Обе эти схемы могут быть использованы для реализации протокола распределения закрытого ключа по открытому каналу, получившего название протокола квантового распределения ключа.
Каждый из известных протоколов квантового распределения ключа включа
ет в себя два этапа: *
передача квантовых частиц по квантовому каналу;
открытую передачу информации о полученной/переданной последовательности квантов по дискретному (в частности, двоичному) каналу.
Эффективным протоколом является тот, который в квантовом канале обеспечивает безусловную секретность передачи информации, в открытом канале — минимальную среднюю взаимную информацию между легальными пользователями протокола и злоумышленником (утечку информации), и при этом для своей реализации требует минимального количества вычислений.
Практический интерес к квантовой криптографии заключается в следующем: математической базой современной криптографии (криптографии с открытыми ключами) являются задачи, которые в терминах теории сложности алгоритмов принадлежат классу NP, т.е. являются "трудными". Сегодня алгоритмы и протоколы, построенные на основе этих задач, обладают вычислительной секретностью. По крайней мере часть из них обеспечивает высокий уровень защиты информации в различных ситуациях: распределения закрытых ключей по открытым каналам, обеспечения секретности, аутентификации и целостности информации. Однако стремительное развитие вычислительной техники, интенсивные исследования в области построения эффективных алгоритмов решения задач из класса NP (в частности Л^Р-полных задач), результаты теории квантовых вычислений могут сделать реальным решение "трудных" задач с полиномиальной сложностью в обозримом будущем. Надежность систем квантовой криптографии определяется не вычислительной сложностью какой-либо "трудной" задачи, а основополагающим принципом квантовой механики: всякое измерение, выполненное над квантовой системой, меняет ее состояние и тем самым обнаруживается.
Основными проблемами при разработке протоколов квантового распределения ключа являются
высокая вероятность ошибки (порядка нескольких процентов) в последо
вательности, переданной по квантовому каналу, что значительно превы
шает уровень ошибок в обычных коммуникациях;
необходимость исправлять ошибки двух типов: символьные и фазовые. Применение помехоустойчивых кодов, исправляющих такого рода ошибки (например, кодов над 24), приводит к увеличению числа вычислений, требуемых для реализации протокола, и может привести к увеличению утечки информации из-за высокой избыточности^
В данной работе предлагаются и исследуются алгоритмы обработки информации, позволяющие реализовать интерактивный протокол квантового распределения ключа.
Цель и задачи исследования. Целью настоящего исследования является построение эффективного интерактивного алгоритма обработки информации и исследование его свойств, а также анализ надежности протокола квантового распределения ключа па основе предложенного алгоритма.
В соответствии с поставленной целью были определены следующие задачи:
Исследование алгоритмов обработки информации в протоколах квантового распределения ключа.
Разработка и анализ интерактивного алгоритма обработки информации для протоколов квантового распределения ключа, уменьшающего количество информации, доступной злоумышленнику.
Анализ качества протокола квантового распределения ключа при исполь -зовании в нем предложенного алгоритма обработки информации;
Получение количественных оценок качества предложенного алгоритма.
. Методы исследования. Для решения поставленных задач в работе использовались следующие методы: методы теории вероятности, теории информации, теории сложности алгоритмов, дискретной математики, комбинаторного анализа и математического моделирования.
Научная новизна работы. Выносимые на защиту результаты обладают существенной научной новизной и впервые получены в данной диссертационной работе. В частности:
1. Проведен анализ интерактивных алгоритмов обработки информации в протоколах
квантовой криптографии и построены количественные оценки
стойкости протоколов
Предложен интерактивный алгоритм обработки информации, который уменьшает количество утекающей злоумышленнику информации по сравнению с известными алгоритмами.
Произведены количественные оценки утечки информации и стойкости протокола квантового распределения ключа, в котором используется предложенный алгоритм обработки информации..
4. Показана возможность использования предложенного алгоритма в про
токоле квантового распределения ключа, обеспечивающего безусловную
секретность.
Теоретическая и практическая ценность. Предложенный алгоритм
обработки информации, позволяющий эффективно исправлять битовые
ошибки практически во всех используемых схемах квантового
распределения ключа, демонстрирует меньшее количество утекающей
информации по сравнению с существующими интерактивными
протоколами. Рассмотренный алгоритм с успехом может использоваться в
протоколах квантовой криптографии, для которой характерен высокий
уровень ошибки в ключах после квантовой передачи сигналов, и который
не нарушает безусловную секретность протоколов квантового
распределения ключа. *
На защиту выносятся следующие основные результаты:
Алгоритм обработки информации, использующий интерактивное взаимодействие участников.
Количественные оценки для алгоритма обработки информации в открытом канале в протоколах квантового распределения ключа.
Доказательство безусловной секретности эквивалентного протокола квантового распределения ключа с использованием интерактивного алгоритма.
Результаты анализа работы протокола распределения ключа в системе квантовой криптографии с использованием предложенного алгоритма обработки информации.
Апробация работы. Основные результаты работы докладывались и обсуждались па следующих российских и международных конференциях:
ГХ Российской научно-технической конференции "Методы и
технические средства обеспечения безопасности информации" —
Санкт-Петербург, Россия, 2001;
EURESCO conference on Quantum Information—San Feliu de Guixols, Spain,
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 наименования.
