Исследование стойкости квантово-криптографических протоколов распространения ключей тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

На правах рукописи

Тимофеев Андрей Владимирович

Исследование стойкости квантово-криптографических протоколов распространения ключей

01 01 05 — Теория вероятностей и математическая статистика

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

003164535

Москва - 2008

Работа выполнена на кафедре квантовой информатики факультета вычислительной математики и кибернетики Московского государственного университета имени М.В Ломоносова

Научный руководитель. доктор физико-математических наук,

член-корреспондент Академии криптографии РФ

Молотков С.Н.

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

академик Академии криптографии РФ, профессор механико-математического факультета МГУ имени М В Ломоносова Сидельников Владимир Михайлович

кандидат физико-математических наук, старший научный сотрудник Академии криптографии РФ Арбеков Игорь Михайлович

Ведущая организация Физико-технологический институт

Российской академии наук

Защита диссертации состоится 29 февраля 2008 г. В 11 ч. 00 мин. на заседании диссертационного совета Д 501.00144 Московского государственного университета имени М.В,Ломоносова по адресу 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК, аудитория 685

С диссертацией можно ознакомиться в библиотеке факультета ВМиК Московского государственного университета имени М В.Ломоносова

С текстом автореферата можно ознакомиться на официальном сайте факультета ВМиК Московского государственного университета имени М В Ломоносова http.//www es msu su в разделе «наука» - «работа диссертационных советов» -«Д 501.001.44»

Автореферат разослан 29 января 2008 г

/ Ученый секретарь диссертационного совета ' профессор „ ,/?ЛТрифонов Н П

ipCf^f

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

Объект исследования и актуальность темы

Квантовая криптография, или распространение секретных ключей, в принципе позволяет реализовать абсолютно стойкие (не дешифруемые подслушивателем даже теоретически) системы шифрования с одноразовыми ключами Секретность ключей в квантовой криптографии основана на фундаментальных запретах квантовой механики, а именно, на том обстоятельстве, что пара наблюдаемых, которым отвечают некоммутирующие операторы, не может быть достоверно одновременно различима, что является следствием соотношений неопределенности Гейзенберга В квантовой криптографии в качестве таких наблюдаемых выступают матрицы плотности информационных состояний, соответствующих классическим битам О и 1 Для чистых состояний одновременная ненаблюдаемость (достоверная неразличимость) матриц плотности эквивалентна неортогональности информационных квантовых состояний Сказанное означает, что не существует измерений, которые с вероятностью единица позволяют различать одно из пары неортогональных состояний и так, чтобы после измерения система оказалась в исходном состоянии, в котором она была до измерения Таким образом, любое измерение, если оно дает информацию о передаваемых состояниях, неизбежно приводит к их возмущению, что позволяет детектировать любые попытки подслушивания в канале связи Другими словами, подслушивание (соответственно возмущение состояний) передаваемых состояний должно неизбежно приводить к изменению статистики результатов измерений на приемном конце по сравнению со статистикой результатов измерений на невозмущенных состояниях Искажение квантовых состояний возникает в неидеальном квантовом канале, что также приводит к изменению статистики результатов измерений В квантовой криптографии принципиально невозможно отличить изменение статистики результатов по сравнению с идеальным случаем, возникающих за счет шума в канале или от действий подслушивателя, поэтому любые изменения статистики приходится относить на действия подслушивателя

Если бы законы квантовой механики позволяли обнаруживать только сам факт возмущения передаваемых состояний, то это было бы бесполезно

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

В квантовой криптографии кроме квантового канала связи (в реальных условиях это либо оптоволокно, либо открытое пространство), по которому передаются квантовые состояния, необходим также открытый классический канал связи Классический открытый канал связи необходим для выяснения легитимными пользователями изменений статистики отсчетов и коррекции ошибок в первичном ключе, переданном по квантовому каналу связи Единственное требование, которое предъявляется к классическому каналу связи состоит в том, что передаваемая открыто и доступная всем, включая подслушивателя, классическая информация не могла быть изменена подслушивателем - сохраняла целостность (так называемый unjammable channel) Такой открытый классический канал является математической идеализацией, поскольку подобных каналов в природе не существует Для сохранения целостности открыто передаваемых классических данных в реальных условиях необходимо использовать процедуры аутентификации и контроля целостности данных Для подобных процедур в свою очередь требуется секретный ключ

Если в качестве открытого классического канала используется, например, интернет, то для целей аутентификации возможна генерация ключей по схеме Хеллмана-Диффи Если же для открытого классического канала используется та же самая оптоволоконная линия, что и для квантового канала связи, то генерация ключей для аутентификации по схеме Хеллмана-Диффи оказывается принципиально неприемлемой из-за очевидной, так называемой атаки "man ш the middle" В такой ситуации требуется небольшой стартовый ключ один раз при первом сеансе При последующих сеансах этот ключ выбрасывается, и для аутентификации и сохранения целостности данных, передаваемых по классическому каналу, используется часть ключа, сгенерированного по квантовому каналу в предыдущем сеансе обмена Оставшаяся большая часть ключа, используется собственно

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

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

Подход с небольшим стартовым ключом является более предпочтительным, поскольку при этом возможно свести к минимуму число раундов обмена по открытому каналу связи в процессе "чистки" и усиления секретности ключа (privacy amplification)

Основная задача теории сводится к выяснению длины секретного ключа, который может быть получен при наблюдаемых изменениях статистики результатов измерений на приемном конце по сравнению со статистикой на невозмущенных состояниях Как правило величиной, которая характеризует отклонение статистики измерений от идеальной, является величина вероятности ошибки Точнее, вероятности того, что переданный бит был 0, а зарегистрирован как 1, и наоборот Хотя возможны и другие критерии для обнаружения изменения статистики

Первым этапом любого квантового протокола распределения ключей является передача и детектирование квантовых состояний После передачи квантовых состояний легитимные пользователи оценивают вероятность ошибки (отклонение статистики отсчетов от идеальной)

Оценка вероятности ошибки получается путем сравнения через открытый канал части переданной последовательности по квантовому кана-

лу, б дальнейшем раскрытая часть отбрасывается

Следующий этап состоит в коррекции ошибок в нераскрытой части последовательности у легитимных пользователей посредством обмена информацией через открытый канал связи Обычно легитимных пользователей называют Алиса и Боб, а подслушивателя - Ева (от английского Eavesdropper) В результате коррекции ошибок остается последовательность бит меньшей длины и одинаковая у Алисы и Боба "Одинаковая" в данном контексте означает, что их последовательности совпадают с вероятностью, сколь угодно близкой к единице (например, 1 — 2~m ~ 1 — Ю-70 при т = 200, величина параметра т выбирается легитимными пользователями) Напомним, что число атомов в видимой части Вселенной оценивается как 1077)

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

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

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

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

Целью диссертационной работы является:

1 Исследование криптографической стойкости двух основных протоколов квантового распределения ключей В92 и ВВ84 с учетом коллективной атаки подслушивателя на передаваемые квантовые состояния,

2 Определение величины критической ошибки <3с в первичных ключах на приемной стороне, до которой возможно получение общего секретного ключа легитимными пользователями,

3 Оценка длины финального секретного ключа, который можно получить при наблюдаемой вероятности ошибки < Сдс в первичных ключах,

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

5 Разработка компьютерных алгоритмов и программ для распределенной коррекции ошибок

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

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

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

1 Построена явная атака на передаваемый при помощи квантовых состояний ключ для протокола ВВ84, достигающая теоретического предела ошибки « 11%, до которой возможно распределение ключей,

2 Дана оценка длины секретного ключа, которую можно получить при наблюдаемой вероятности ошибки <2 < <2с в первичных ключах, для двух основных квантовых протоколов распределения ключей ВВ84 и В92,

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

4 Разработаны алгоритмы и компьютерные программы для распределенной коррекции ошибок

Публикации и апробирование Результаты диссертации докладывались на семинаре ВМиК МГУ "Квантовая информатика" (руководители - акад К А Валиев, проф Ю И Ожигов, проф С Н Молотков), на семинаре Физико-технологического института Российской академии наук (ФТИАН) "Квантовые компьютеры" (руководитель - акад К А Валиев), на 10 научно-технической конференции по криптографии (Москва 2006 год), на конференциях Квантовая информатика - 2007 и Квантовая информатика - 2005

По теме диссертации опубликовано 6 работ Структура и объем работы

Диссертация состоит из введения, шести глав, приложения и списка литературы Объем работы 125 страниц

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

представлены положения, выносимые на защиту и описана структура диссертации

В первой главе приведено описание квантового криптографического протокола В92 и различных стратегий подслушивания

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

В третьей главе исследуется криптографическая стойкость основного квантового протокола распределения ключей - ВВ84 Для данного протокола ранее была найдена (Mayers, Shor, Preskill) точная величина критической ошибки Однако эти доказательства являются фактически теоремами существования, констатирующими, что при Q > Qc ~ 11% Алиса и Боб не могут получить общий секретный ключ При этом явная стратегия Евы, которая приводит к данной ошибке, неизвестна Точнее говоря, неизвестна оптимальная стратегия подслушивания, которая дает Еве максимум информации о ключе при минимально возможной производимой ей ошибкой у Боба

Более менее ясно, что при такой стратегии Ева должна использовать квантовую память и коллективные измерения над всей последовательностью квантовых состояний Это убеждение возникает из того обстоятельства, что для случая индивидуальных измерений над передаваемыми состояниями, оптимальная стратегия известна и построена явно Но при такой стратегии Евы критическая ошибка оказывается Qc « 15%, что выше точной границы

Кроме того, оставался открытым вопрос о том, что происходит в области ошибок 11% < Qc < 15% Или иначе говоря, какие стратегии Евы будут приводит к критической ошибке в "диапазоне" стратегий (коллективная атака - индивидуальная атака)

В третьей главе стратегия, на которой достигается теоретический предел критической ошибки Qc « 11%, построена явно Кроме того, прояснен вопрос, что происходит в области ошибок 11% < Q < 15% Показано,

что существует бесконечный набор стратегий подслушивания Евы, который приводит к ошибкам в интервале 11% < <5 < 15% Установлена связь бесконечного набора стратегий с бесконечным набором классических пропускных способностей квантового канала связи Данное явление не имеет классического аналога Причем оказывается, что различные атаки внутри бесконечного набора отличаются только на стадии измерений Если Ева может проводить коллективные измерения сразу над всей последовательностью квантовых состояний, то реализуется оптимальная стратегия, приводящая к критической ошибке в 11% Если Ева может производить только индивидуальные измерния, то достигается ошибка в 15% Если Ева может делать измерения не более, чем над к состояниями сразу (1 < к < оо), то критическая ошибка <ЭС(11%) < (¿^ < <ЭС(15%)

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

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

Одной и важных задач является поиск эффективных процедур распределенной коррекции ошибок

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

и

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

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

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

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

разных проходах, достаточно сложно До сих пор, насколько нам известно, полный анализ не был выполнен

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

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

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

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

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

Публикации по теме диссертации

ICH Молотков, А В Тимофеев, Явная атака на ключ в квантовой криптографии (протокол ВВ84), достигающая теоретического предела ошибки Qc ~ 11%, Письма в Журнал экспериментальной и тео-ретичесой физики, т 85, вып 10, 634 (2007)

2 А В Тимофеев, С Н Молотков, О каскадном методе коррекции ошибок в первичных ключах в квантовой криптографии, сохраняющем конфиденциальность, Письма в Журнал экспериментальной и теоре-тичесой физики, т82, вып 12, 868 (2005)

ЗАВ Тимофеев, Д И Помозов, А П Маккавеев, С Н Молотков, О структуре открытого классического канала связи в квантовой криптографии коррекция ошибок, целостность и аутентичность, Журнал экспериментальной и теоретической физики, т 131, вып 5, 771 (2007)

4 А П Маккавеев, С Н Молотков, Д И Помозов, А В Тимофеев, О практических методах "чистки" ключей в квантовой криптографии, Журнал экспериментальной и теоретической физики, т 128, вып 2, 263 (2005)

5 А Р Makkaveyev, S N Molotkov, DI Pomozov, A V Timofeyev, Practical error-correction procedures in quantum cryptography, Proc of SPIE vol 6264, 62640F, (2006)

6 Молотков С H , Тимофеев А В , О каскадном методе коррекции ошибок в первичных ключах в квантовой криптографии, Тезисы докладов 10 научно-технической конференции по криптографии, посвященной 85-летию образования Криптографической Службы России, Москва 2006 год, Академия криптографии Российской Федерации, секция 13, с 56

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01 12 99 г Подписано к печати 29 01 2008 г Формат 60x90 1/16 Уел печ л 1,0 Тираж 100 экз Заказ 028 Тел 939-3890 Тел/Факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им М.В Ломоносова, 2-й учебный корпус, 627 к

Введение

1 Квантовое распределение ключей на двух неортогональных состояниях (протокол В92)

1.1 Информационные состояния и измерения

1.2 Стратегии подслушивания.

2 Длина секретного ключа в шенноновском пределе

2.1 Индивидуальная атака.

2.2 Коллективная атака.

3 Явная атака на ключ в квантовой криптографии (протокол ВВ84), достигающая теоретического предела ошибки Qc ри 11%

3.1 Общие сведения о протоколе ВВ84.

3.2 Атака подслушивателя на ключ.

3.3 Измерения на приемной стороне.

3.4 Коррекция ошибок легитимными пользователями.

3.5 Индивидуальные измерения подслушивателя.

3.6 Коллективные измерения подслушивателя.

3.7 Область критических ошибок 11% < Qc < 15%

3.8 Выводы.

4 Усиление секретности

4.1 Теорема об усилении секретности.

4.2 Длина финального секретного ключа.

4.3 Выводы.

5 Практические методы коррекции ошибок

5.1 Требования к процедурам коррекции ошибок в квантовой криптографии

5.2 "Чистка" первичного ключа при помощи БЧХ кодов (Bose-Chaudhuri-Hocquenghem)

5.2.1 Вычисление ошибки подслушивателя после "чистки" ключа БЧХ кодами

5.3 "Чистка" первичного ключа при помощи кодов Хэмминга (Hamming).

5.4 Протокол Cascade.

5.4.1 Исходные данные.

5.4.2 Результат.

5.4.3 Алгоритм.

5.4.4 Статистика.

5.5 Удаление битов четности.

5.5.1 Исходные данные.

5.5.2 Результат.

5.5.3 Алгоритм.

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

5.6 Выводы.

6 Система квантовой криптографии

6.1 Оптоволоконная реализация протокола В92.

6.1.1 Информационные однофотонные состояния.

6.1.2 Преобразование состояний на передающей станции.

6.1.3 Преобразование состояний на приемной станции.

6.1.4 Измерения на приемной стороне.

6.2 Открытый классический канал связи.

6.3 Передача сообщений.

6.4 Генерация сырого ключа.

6.5 Обработка ключа

6.5.1 Описание.

6.5.2 Сетевое взаимодействие.

6.5.3 Случайные числа.

6.5.4 Раскрытые биты четности.

6.5.5 Параметры "чистки".

6.5.6 Определение начальной стадии процесса.

6.5.7 Синхронизация.

6.5.8 Перестановка битов.

6.5.9 Каскадная процедура коррекции ошибок в первичных ключах.

6.5.10 Сравнение ключей.

6.5.11 Выбрасывание раскрытых битов.

6.5.12 Хэширование "очищенных" ключей.

6.5.13 Возврат ключа.

Объект исследования и актуальность темы.

Квантовая криптография [1, 2], или распространение секретных ключей, в принципе позволяет реализовать абсолютно стойкие (не дешифруемые подслушивателем даже теоретически) системы шифрования с одноразовыми ключами [3, 4]. Секретность ключей в квантовой криптографии основана на фундаментальных запретах квантовой механики [5], а именно, на том обстоятельстве, что пара наблюдаемых, которым отвечают некоммутирую-щие операторы, не может быть достоверно одновременно различима, что является следствием соотношений неопределенности Гейзенберга. В квантовой криптографии в качестве таких наблюдаемых выступают матрицы плотности информационных состояний, соответствующих классическим битам 0 и 1. Для чистых состояний одновременная ненаблюдаемость (достоверная неразличимость) матриц плотности эквивалентна неортогональности информационных квантовых состояний [6]. Сказанное означает, что не существует измерений, которые с вероятностью единица позволяют различать одно из пары неортогональных состояний и так, чтобы после измерения система оказалась в исходном состоянии, в котором она была до измерения. Таким образом, любое измерение, если оно дает информацию о передаваемых состояниях, неизбежно приводит к их возмущению, что позволяет детектировать любые попытки подслушивания в канале связи. Другими словами, подслушивание (соответственно возмущение состояний) передаваемых состояний должно неизбежно приводить к изменению статистики результатов измерений на приемном конце по сравнению со статистикой результатов измерений на невозмущенных состояниях. Искажение квантовых состояний возникает в неидеальном квантовом канале, что также приводит к изменению статистики результатов измерений. В квантовой криптографии принципиально невозможно отличить изменение статистики результатов по сравнению с идеальным случаем, возникающих за счет шума в канале или от действий подслушивателя, поэтому любые изменения статистики приходится относить на действия подслушивателя.

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

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

Если в качестве открытого классического канала используется, например, интернет, то для целей аутентификации возможна генерация ключей по схеме Хеллмана-Диффи [7]. Если же для открытого классического канала используется та же самая оптоволоконная линия, что и для квантового канала связи, то генерация ключей для аутентификации по схеме Хеллмана-Диффи оказывается принципиально неприемлемой из-за очевидной, так называемой атаки "man in the middle". В такой ситуации требуется небольшой стартовый ключ один раз при первом сеансе. При последующих сеансах этот ключ выбрасывается, и для аутентификации и сохранения целостности данных, передаваемых по классическому каналу, используется часть ключа, сгенерированного по квантовому каналу в предыдущем сеансе обмена. Оставшаяся большая часть ключа, используется собственно для шифрования данных. Если для аутентификации и сохранения целостности данных используются процедуры на основе ГОСТа, то длина стартового ключа составляет 256 бит. При этом в результате работы протокола передачи ключа обмена может быть получен новый секретный ключ по квантовому каналу гораздо более длинный, чем исходный.

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

Подход с небольшим стартовым ключом является более предпочтительным, поскольку при этом возможно свести к минимуму число раундов обмена по открытому каналу связи в процессе "чистки" и усиления секретности ключа (privacy amplification).

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

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

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

Следующий этап состоит в коррекции ошибок в нераскрытой части последовательности у легитимных пользователей посредством обмена информацией через открытый канал связи. Обычно легитимных пользователей называют Алиса и Боб, а подслушивателя - Ева (от английского Eavesdropper). В результате коррекции ошибок остается последовательность бит меньшей длины и одинаковая у Алисы и Боба. "Одинаковая" в данном контексте означает, что их последовательности совпадают с вероятностью, сколь угодно близкой к единице (например, 1 — 2~т ~ 1 — Ю-70 при т = 200, величина параметра т выбирается легитимными пользователями). Напомним, что число атомов в видимой части Вселенной оценивается как 1077).

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

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

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

1. Исследование криптографической стойкости двух основных протоколов квантового распределения ключей В92 и ВВ84 с учетом коллективной атаки подслушивателя на передаваемые квантовые состояния;

2. Определение величины критической ошибки Qc в первичных ключах на приемной стороне, до которой возможно получение общего секретного ключа легитимными пользователями;

3. Оценка длины финального секретного ключа, который можно получить при наблюдаемой вероятности ошибки Q < Qc в первичных ключах;

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

5. Разработка компьютерных алгоритмов и программ для распределенной коррекции ошибок.

Краткое содержание диссертации.

В первой главе приведено описание квантового криптографического протокола В92 и различных стратегий подслушивания. 9

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

В третьей главе исследуется криптографическая стойкость основного квантового протокола распределения ключей - ВВ84. Для данного протокола ранее была найдена точная величина критической ошибки [26],[28]. Однако доказательства [26],[28] являются фактически теоремами существования, констатирующими, что при Q > Qc ~ 11% 1 Алиса и Боб не могут получить общий секретный ключ. При этом явная стратегия Евы, которая приводит к данной ошибке, неизвестна. Точнее говоря, неизвестна оптимальная стратегия подслушивания, которая дает Еве максимум информации о ключе при минимально возможной производимой ей ошибкой у Боба.

Более менее ясно, что при такой стратегии Ева должна использовать квантовую память и коллективные измерения над всей последовательностью квантовых состояний. Это убеждение возникает из того обстоятельства, что для случая индивидуальных измерений над передаваемыми состояниями, оптимальная стратегия известна и построена явно. Но при такой стратегии Евы критическая ошибка оказывается Qc ~ 15%, что выше точной границы.

Кроме того, оставался открытым вопрос о том, что происходит в области ошибок 11% < Qc < 15%. Или иначе говоря, какие стратегии Евы будут приводит к критической ошибке в "диапазоне" стратегий (коллективная атака - индивидуальная атака).

В третьей главе стратегия, на которой достигается теоретический предел критической ошибки Qc т 11%, построена явно. Кроме того, прояснен вопрос, что происходит в области ошибок 11% < Q < 15%. Показано, что существует бесконечный набор стратегий подслушивания Евы, который приводит к ошибкам в интервале 11% < Q < 15%. Установлена связь бесконечного набора стратегий с бесконечным набором классических пропускных способностей квантового канала связи. Данное явление не имеет классического аналога. Причем оказывается, что различные атаки внутри бесконечного набора отличаются только на стадии измерений. Если Ева может проводить коллективные измерения сразу над всей последовательностью квантовых состояний, то реализуется оптимальная стратегия, приводящая к критической ошибке в 11%. Если Ева может производить только индивидуальные измерния, то достигается ошибка в 15%. Если Ева может делать измерения не более, чем над к состояниями сразу (1 < к < оо), то критическая ошибка Qc(ll%) < Q^ < Qc(15%).

Критическая ошибка зависит от способа исправления ошибок. Упомянутые критиче

3нак та используется для краткости, поскольку значение Qc определяется как корень некоторого трансцендентного уравнения.

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

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

Одной и важных задач является поиск эффективных процедур распределенной коррекции ошибок.

После исправления ошибок Алисой и Бобом у них возникают одинаковые битовые строки ("очищенный" ключ). Однако информация Евы об "очищенном" клююче все еще является конечной, и заведомо не экспоненциально малой по параметру секретности. Для получения финального секретного ключа необходимо сжатие (хеширование) очищенного ключа при помощи универсальных функций хеширования второго рода [20] (Wegman, Carter), которые сами являются случайными величинами. Причем степень сжатия определяется как величиной ошибки в первичном ключе, так и используемой процедурой коррекции ошибок. Исследованию этих вопросов посвящена четвертая глава.

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

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

11 достаточно мало битов в "очищенном" ключе (например, при вероятности ошибки в 10% в первичном ключе в "очищенном" ключе остается не более 10% от исходной длины).

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

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

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

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

Защищаемые положения.

1. Построена явная атака на передаваемый при помощи квантовых состояний ключ для протокола В В 84, достигающая теоретического предела ошибки Qc « 11%, до которой возможно распределение ключей;

2. Дана оценка длины секретного ключа, которую можно получить при наблюдаемой вероятности ошибки Q < Qc в первичных ключах, для двух основных квантовых протоколов распределения ключей ВВ84 и В92;

3. Предложен метод сохранения конфиденциальности для каскадного метода коррекции ошибок в первичных ключах;

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

Научная новизна и практическая значимость.

12

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

Получены оценки длины ключа для двух основных квантовых протоколов распределения ключей В92 и ВВ84.

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

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

Апробация работы и публикации.

Результаты работы докладывались и обсуждались на следующих конференциях:

1. Международная конференция "Quantum Informatics - QI-2007", Москва, Россия, 2007 г.;

2. 10 Научно-техническая конференция по криптографии, посвященная 85-летию образования Криптографической Службы России, Москва 2006 г., Академия Криптографии Российской Федерации, Секция 13.

3. Международная конференция "Quantum Informatics - QI-2005", Москва, Россия, 2005 г.;

13

Основные результаты диссертации опубликованы в работах:

1) С.Н.Молотков, А.В.Тимофеев, Явная атака на ключ в квантовой криптографии (протокол ВВ84), достигающая теоретического предела ошибки Qc рз 11%, Письма в Журнал экспериментальной и теоретичесой физики, т.85, вып.10, 634 (2007).

2) А.В.Тимофеев, С.Н.Молотков, О каскадном методе коррекции ошибок в первичных ключах в квантовой криптографии, сохраняющем конфиденциальность, Письма в Журнал экспериментальной и теоретичесой физики, т.82, вып.12, 868 (2005).

3) А.В.Тимофеев, Д.И.Помозов, А.П.Маккавеев, С.Н.Молотков, О структуре открытого классического канала связи в квантовой криптографии: коррекция ошибок, целостность и аутентичность, Журнал экспериментальной и теоретической физики, т. 131, вып.5, 771 (2007).

4) А.П.Маккавеев, С.Н.Молотков, Д.И.Помозов, А.В.Тимофеев, О практических методах "чистки" ключей в квантовой криптографии, Журнал экспериментальной и теоретической физики, т. 128, вып.2, 263 (2005).

14

1. S.Wiesner, Conjugate coding , S1.ACT News, 15, 78 (1983).

2. C.H.Bennett, G.Brassard, Quantum Cryptography: Public Key Distribution and Coin Tossing, Proc.of IEEE Int. Conf. on Comput. Sys. and Sign. Proces., Bangalore, India, December 1984, p.175.

3. G.S.Vernam, Cipher printing telegraph systems for secret wire and radio telegraphic communications, J. Amer. Inst. Elect. Eng., 55, 109 (1926).

4. C.E.Shannon, Communication theory of secrecy systems, Bell Syst. Tech. Jour., 28, 658 (1949).

5. W.K.Wootters, W.H.Zurek, A single quantum cannot be cloned Nature, 299, 802 (1982).

6. C.H.Bennett, Quantum Cryptography Using Any Two Nonorthogonal States , Phys. Rev. Lett., 68, 3121 (1992);

7. W.Diffi, M.E.Hellman, New directions in cryptography, IEEE Trans, on Information Theory, IT-22, 644 (1976).

8. A.K.Ekert, B.Huttner, G.M.Palma, A.Peres, Eavesdropping on Quantum-Cryptographical Systems , Phys. Rev., A50, 1047 (1994).

9. H.E.Brandt, J.M.Meyers, S.J.Lomonaco Jr., Aspects of Entangled Translucent Eavesdropping in Quantum Cryptography , Phys. Rev., A56,4456 (1997).

10. C.E.Shannon, Mathematical Theory of Communication, Bell Syst. Tech. Jour., 27, 397; 27, 623 (1948).

11. Р.Галлагер, Теория информации и надежная связь, Москва, Советское радио (1974).

12. C.W.Helstrom, Quantum Detection and Estimation Theory, Academic Press, New York, San Francisco, London, (1976).

13. J.Wolfowitz, The Coding Messages Subjected to Chance Errors, Illinois J. of Math., 1, 591 (1957).124

14. А.С.Холево, Введение в квантовую теорию информации, серия Современная математическая физика, вып. 5, МЦНМО, Москва, 2002;

15. R.Jozsa, B.Schumacher, A new proof of the quantum noiseless coding theorem , J. Mod. Optics. 41, 2343 (1994).

16. P.Hausladen, R.Jozsa, B.Schumacher, M.Westmoreland, W.K.Wootters, Classical information capacity of a quantum channel , Phys. Rev. A54, 1869 (1996).

17. B.Schumacher, M.D.Westmoreland, Sending classical information via noisy quantum channels , Phys. Rev. A 56, 131 (1997).

18. D.Maurer, Practical error-correction procedures in quantum cryptography , IEEE Trans. Inf. Theory, 39, 733 (1993).

19. C.H.Bennett, G.Brassard, C.Crepeau, U.Maurer, Generalized privacy amplification, IEEE Transaction on Information Theory, 41, 1915 (1995).

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

21. C.H.Bennett, F.Bessette, G.Brassard, L.Salvail, J.Smolin, Experimental quantum, cryptography, Journal of Cryptology, 5, 3 (1992).

22. G.Brassard, L.Salvail, Secret Key Reconcilation by Public Discussion, Lecture Notes in Computer Science, 765, 410 (1994).

23. E.J.Mac Williams, N.J.A.Sloane, The Theory of Error-Correcting Codes, North-Holland Publ. Company, (Amsterdam, New York, Oxord), 1977.

24. W.W.Peterson, E.J.Weldon, Error-Correcting Codes, The MIT Press, Cambridge, Massachusetts, London, England, (1972).

25. B.Julsgaard, J.Sherson, J.I.Cirac, J.Flurasek, E.S.Polzik, Experimental demonstration of quantum memory for light, Nature, 432, 482 (2004).

26. D.Mayers, Unconditional security in Quantum Cryptography, arXiv:quant-ph/9802025.

27. E.Biham, M.Boyer, P.O.Boykin, T.Mor, V.Roychowdhury, A Proof of the Security of Quantum Key Distribution, arXiv:quant-ph/9912053.125

28. P.W.Shor, J.Preskill, Simple Proof of Security of the BB84 Quantum Key Distribution Protocol, arXiv: quant-ph/0003004.

29. I.Csiszar. J.Korner, Broadcast channels with confidential messages, IEEE Trns. Inf. Theory, 24, 339 (1978).

30. C.A.Fuchs, N.Gisin, R.Griffiths, Chi-Sheng Niu, A.Peres, Optimal Eavesdropping in Quantum Cryptography, Phys. Rev., A56 1163 (1997).

31. C.E.Shannon, Mathematical Theory of Communication, Bell Syst. Tech. Jour., 27, 397; 27, 623 (1948).

32. А.С.Холево, Проблемы передачи информации. 8, 63 (1972); 15, 3 (1979); Успехи математических наук. 53, 193 (1998);

33. А.В.Тимофеев, С.Н.Молотков, О каскадном методе коррекции ошибок в первичных ключах в квантовой криптографии, сохраняющем конфиденциальность, Письма в ЖЭТФ, 82 868 (2005).

34. R.Griffiths, Chi-Sheng Niu, Optimal eavesdropping in quantum cryptography. II. A quantum circuit, Phys. Rev., A56 1173 (1997).

35. P.Shor, Capacities of Quantum Channels and How to Find Them, arXiv:quant-ph/0304102.

36. Gilles Brassard, Louis Salvail, Secret-Key Reconciliation by Public Discussion, EUROCRYPT 1993: 410-423.

37. W. T. Buttler, S. K. Lamoreaux, J. R. Torgerson, G. H. Nickel, Fast, Efficient Error Reconciliation for Quantum Cryptography, arXiv: quant-ph/0203096

38. Chip Elliott, Alexander Colvin, David Pearson, Oleksiy Pikalo, John Schlafer, Henry Yeh, Current status of the DARPA Quantum Network, arXiv:quant-ph/0503058

39. Дональд Кнут. Искусство программирования, т. 1, "Вильяме", Москва, 2000.

40. C.Cachin, Dissertation of Swiss Federal Institute of Technology of Ziirich, Entropy Measures and Unconditional Security in Cryptography, Diss. ETH No.12187 (1997).

41. Т.Кормен, Ч.Лейзерсон, Р.Ривест, Алгоритмы: построение и анализ, МЦНМО, Москва, 2004.