Квантовая криптография простыми словами (гостевой пост Романа Душкина). Другие примеры включают
ЛЕКЦИЯ 17. Квантовая криптография
17.1. Проблема распределения ключа в классической криптографии и пути ее решения.
17.2. Физические основы квантового распределения ключа: теорема о запрете копирования и неразличимость неортогональных состояний. Общая схема протокола КРК.
17.3. Основные свойства поляризованных фотонов. Некоторые сведения из теории квантовых измерений. Сопряженные базисы. Три сопряженных базиса для поляризованных фотонов.
17.4. Протокол ВВ84. Сырой и просеянный ключ. Коррекция ошибок и усиление секретности - на примере протокола BB84. Подслушивание в протоколе ВВ84. Стратегия перехватчик-ретранслятор. Стратегия “задержанного выбора”. Активный подслушиватель и схема аутентификации Вегмана-Картера. Недостатки протокола ВВ84.
17.5. Протокол ВВ92. Его преимущества и недостатки по сравнению с ВВ84.
17.6. ЭПР протокол (протокол А.Экерта) - если есть время.
На предыдущей лекции были сформулированы две проблемы современной классической криптографии: распределение ключей и аутентификация. Вторая проблема, похоже, имеет разрешение (абсолютно защищенное) лишь при личной встрече владельцев ключа. Первая проблема – распределение ключа в классической криптографии решается с помощью криптографии с открытым ключом или двухключевых (асимметричных) протоколов. Такое ее решение назовем математическим , поскольку используется некий алгоритм, основанный на односторонних функциях с секретом, когда вычисление функции в одну сторону оказывается простым, а нахождение обратной функции занимает огромное количество вычислительных ресурсов. В частности, стойкость криптографических систем RSA и Эль-Гамаля основываются на том, что факторизация больших чисел требует экпоненциального по числу знаков факторизуемого числа N операций. Это значит, что при увеличении разряда числа на один (прибавление еще одной цифры к факторизуемому числу) умножает время, необходимое для факторизации на фиксированный множитель. При увеличении числа, задача быстро становится вычислительно не решаемой. Таким образом, в настоящий момент, защищенность двухключевых криптосистем основывается на медленности технического прогресса.
В одной из следующих лекций мы будем рассматривать алгоритм факторизации чисел, предложенный П.Шором. Этот алгоритм основан на параллельном методе вычислений, который можно осуществить в квантовом компьютере. Такой алгоритм позволяет принципиально изменить скорость факторизации – теперь она определяется полиномиальными по числу N временными затратами.
Другой путь решения проблемы распределения ключа основан на физических закономерностях. Он реализуется в квантовой криптографии. Основные аргументы в таком методе криптографии восходят к двум утверждениям:
Неизвестное квантовое состояние невозможно копировать;
Без возмущения невозможно извлечь информацию о неортогональных квантовых состояниях.
Последнее утверждение можно перефразировать: в общем случае любое измерение, выполняемое подслушивателем, приведет к изменению состояния носителя информации.
Далее будут рассмотрены основные протоколы квантовой криптографии. Строго говоря, речь будет идти не о новом типе криптографии в целом, а лишь о новом методе распределения ключа. Этот метод, вообще говоря, должен быть дополнен надлежащим протоколом аутентификации – абоненты должны идентифицировать друг друга до начала общения – об этом не следует забывать, говоря о преимуществах квантовой криптографии! На сегодняшний день единственный способ решения проблемы аутентификации состоит в обмене коротким секретным ключом при встрече абонентов. Квантовая криптография дает физический способ распределения ключа большого размера , который затем можно использовать в симметричных (одноключевых) протоколах. Поэтому, будучи до конца последовательным, следует говорить о квантовой криптографии как о протоколе увеличения секретного ключа (Quantum Secret Growing protocol ) .
Итак, общая схема квантового распределения ключа следующая.
Алиса посылает квантовое состояние, реализованное, например, в виде кванта света, Бобу. Подслушивание, как физический процесс, представляет собой серию экспериментов, выполняемых злоумышленником над перехваченными квантами. Поскольку акт подслушивания изменяет квантовое состояние носителя информации, то Алиса и Боб могут это установить с помощью определенных процедур уже по открытому каналу связи. Итак, протокол квантового распределения ключа должен включать в себя:
Установление синхронизации;
По крайней мере двух пользователей – Алису и Боба;
Канал для обмена квантовыми состояниями или квантовый канал связи ;
Открытый канал связи, который используется для проверки искажения посылаемых состояний.
Если после обмена сообщениями по открытому каналу пользователи убеждаются, что квантовые состояния не возмущены, то они включают хорошо известный протокол одноразового блокнота (код Вернама) используя распределенный секретный ключ. Если обнаруживается возмущение квантовых состояний, то сеанс связи либо прерывается, либо начинается заново.
Замечание. Открытый канал рассматривается как такой канал связи, который доступен любому желающему. Единственное ограничение, которые мы пока введем на открытый канал – чтобы подслушиватель был пассивным . В случае активного подслушивателя пользователи могут осуществлять распределение ключа, но при условии, что изначально они владели некоторой секретной информацией, распределенной между ними и если подслушиватель не настолько активен, чтобы перехватывать всю посланную информацию (атака раздельных миров или с человеком посередине).
Идея, впервые высказанная Визнером, Беннетом и Брассардом состоит в том, что пассивный подслушиватель не может достоверно различить неортогональные состояния (назовем их ), если он не знает базиса, в котором те были приготовлены. Предположим, что Ева настраивает свой измеряющий прибор в неком исходном состоянии . Ее цель – отличить состояния не возмущая их. Ее действия будут описываться следующими унитарными преобразованиями над входными состояниями (см. лекцию 6);
(17.1)
(17.2)
Унитарность сохраняет скалярное произведение, поэтому
откуда следует, что
Это означает, что конечное состояние измерительного прибора Евы одно и то же. Ева не возмутила квантовых состояний, но она и не получила никакой информации о них, в силу (17.4).
Мы рассматривали и более общее измерение, когда Ева возмущает исходные состояния:
. (17.5)
Тогда в результате действий подслушивателя:
, (17.6)
. (17.7)
И опять, в силу унитарности, получаем:
(17.8)
Наилучшая ситуация с точки зрения Евы возникает, когда скалярное произведение принимает минимальное значение. Это происходит при
(поскольку ). При этом она получает максимальную возможность различить два состояния своего прибора, но два исходно неортогональные состояния становятся неразличимыми (17.9).
Квантовое кодирование информации впервые было предложено в работах Стефана Визнера, а также Чарльза Беннета и Жиля Брассарда. С.Визнер рассматривал т.н. «квантовые деньги», т.е. деньги, которые в принципе невозможно подделать. Кроме того, он предложил способ распределения двух или трех сообщений, при котором чтение одного из них уничтожало бы информацию, содержащуюся в других. Ч.Беннет и Ж.Брассард предложили реалистичный протокол распределения ключа. Также они обсуждали криптографические схемы типа протокола жеребьевки.
ПРОТОКОЛ BB 84 [ 5 ]
Этот протокол был предложен Ч.Беннетом и Ж.Брассаром в 1984 г. Для распределения ключа они рассматривали неортогональные состояния фотонов.
В оригинальной работе Ч.Беннет и Ж.Брассард рассматривали поляризационные состояния света в качестве квантовых систем, лежащих в основе протокола распределения ключа.
Основные свойства поляризованных фотонов.
Приготовить поляризованный свет можно, пропуская пучок света через какое-нибудь поляризационное устройство, например, призму Глана-Томсона. Ослабляя затем этот свет, можно в принципе, с некоторой вероятностью получить состояния типа смеси вакуумного и однофотонного фоковского:
(17.10)
где , а m и n представляют числа фотонов в двух ортогональных поляризационных модах. Хотя поляризация является непрерывно меняющейся величиной, принцип неопределенности запрещает извлечение более одного бита информации при измерении единичного фотона. Так, если свет, поляризованный вдоль оси a, направляется на поляризационный фильтр, ориентированный вдоль оси b, то отдельные фотоны проявляют дихотомность свойств и ведут себя вероятностным образом, поскольку могут быть либо пропущены с вероятностью , либо поглощены с сопряженной вероятностью . Детерминированность свойств отдельных фотонов, согласно такой интерпретации, возникает, лишь когда две оси параллельны (достоверное пропускание), либо скрещены (достоверное поглощение). Если же оси не перпендикулярны, так что некоторые фотоны пропускаются, то казалось бы, что можно извлечь дополнительную информацию об угле a, поместив поляроид в прошедший пучок под неким третьим углом. Однако это не так, поскольку прошедшие сквозь первый поляроид фотоны имеют определенную поляризацию b, т.е. они полностью утратили информацию о начальной поляризации a. Другой путь извлечения более одного бита информации из отдельного фотона состоит в приготовлении копий такого состояния и последующего их измерения. Однако такой путь запрещен no-cloning теоремой.
Напоминание из теории измерения (см.Лекцию 8)
Формально квантовая механика описывает внутреннее состояние системы с помощью вектора состояния y, имеющего единичную длину в линейном пространстве Н , определенном на поле комплексных чисел (гильбертово пространство). В этом пространстве определено скалярное произведение векторов:
, (17.11)
где символ «*» означает комплексное сопряжение. Каждое физическое измерение М , которое может быть выполнено над системой, соответствует разложению гильбертова пространства на ортогональные подпространства, причем на каждое подпространство приходится по одному результату измерений. Таким образом, число возможных исходов измерений ограничено размерностью d гильбертова пространства. Соответственно при наиболее полных измерениях гильбертово пространство раскладывается на d одномерных подпространств.
Пусть M k является проекционным оператором в k -ое подпространство измерения М . Тогда тождественный оператор I есть просто сумма проекционных операторов:
Из определения вектора состояния известно, что если система, находящаяся в состоянии y, подвергается измерению М , ее поведение становится вероятностным: исход к-ого измерения описывается вероятностью , которая на векторном языке означает квадрат длины проекции вектора состояния в подпространство M k . После измерения система переходит в новое состояние (постулат фон Неймана) , которое является просто единичным вектором в направлении проекции старого вектора состояния в подпространство M k . Согласно этому постулату, измерение оставляет вектор состояния неизменным, (т.е. результат измерения является предопределенным, детерминированным) лишь, когда начальный вектор состояния лежал целиком в одном из ортогональных подпространств, характеризующих измерение.
Гильбертово пространство отдельного поляризованного фотона является двухмерным пространством (d
= 2). Следовательно, поляризационное состояние фотона полностью может быть описано с помощью линейной комбинации, скажем, двух единичных векторов 
и . Например, линейно поляризованный фотон под углом a к горизонтальному направлению, описывается вектором 
. Измеряя такой фотон в вертикально-горизонтальном (лабораторном базисе) получим горизонтально поляризованный фотон с вероятностью и вертикально поляризованный фотон с вероятностью . В этом смысле два вектора и представляют собой разложение двухмерного гильбертова пространства в два ортогональных одномерных пространства. Эти два вектора будем назвать линейным прямоугольным базисом
.
Альтернативным базисом того же гильбертова пространства является т.н. диагональный базис, образованный векторами 
и 
.
Определение. Вообще, два (рассмотренных) базиса называются сопряженными ( conjugated , mutually unbiased ) , если каждый вектор одного базиса имеет проекции одинаковой длины на все вектора другого базиса. Это означает, что система, приготовленная в некоем состоянии, представленном векторами одного базиса, будет вести себя совершенно случайным образом (потеряет всю запасенную информацию) будучи измеренной в сопряженном базисе. Математически это требование записывается как
Вообще же, в знаменателе выражения (*) должна стоять размерность гильбертова пространства.
Говоря о двухмерном гильбертовом пространстве, необходимо отметить, что существует третий базис, сопряженный линейному и диагональному – т.н. циркулярный базис, образованный право- и лево-циркулярно поляризациями:
, 
. Однако для описание протокола распределения ключа нам потребуются лишь первые два базиса.
Описание протокола распределение ключа.
В традиционных протоколах с открытым ключом используются односторонние функции с секретом (повторное дискретное возведение в степень) без предварительного распределения секретной информации между пользователями. В квантовом протоколе квантовый канал используется для передачи некоторого массива случайных битов квантовых информации (кубитов), открытый канал – для обсуждения, см. табл.1.
Вводится синхронизация между действиями Алисы и Боба, т.е. каждый из них знает наверняка, в какой момент времени посылается состояние;
Алиса выбирает случайный массив битов (чередование 0 или 1 в моменты, оговоренные синхронизационным протоколом);
Алиса выбирает случайную последовательность (поляризационных) базисов – чередование либо линейного, либо диагонального (L, D);
Алиса посылает Бобу последовательность фотонов, кодируя поляризацию каждого фотона, исходя из массива битов и поляризационного базиса: каждый фотон имеет определенную поляризацию и описывается одним из четырех базисных векторов . Будем полагать, что значение бита «0» отвечает за состояния , а «1» – за состояния ;
Боб принимает (измеряет) посланные Алисой фотоны в одном из двух базисов. Причем выбор базиса – случаен. Боб интерпретирует результаты своих измерений в бинарном представлении, т.е. пользуясь тем же правилом, что и Алиса: «0» и «1» . Заметим, что как следует из теории измерений, Боб полностью теряет информацию о состоянии фотона, поляризованного в лабораторном базисе (H-V ), измеряя его в диагональном базисе (+45-45) и наоборот. Следовательно, Боб получает достоверную информацию о состоянии фотонов только в половине всех случаев – когда выбранный им базис совпал с базисом Алисы, т.е. когда измерение дает детерминированный результат. Если подслушивания не было, то в оставшейся половине случаев Алиса и Боб имеют некоррелировынные результаты. Следовательно, в среднем, Боб получает массив битов с 25%-ым содержанием ошибок. Этот массив называется сырым ключом . Кроме того, будем учитывать тот факт, что часть фотонов теряется при передаче. Практически, уровень технических ошибок в квантовых протоколах на сегодняшний день составляет несколько процентов (в отличие от уровня , достижимого в современных оптотелекоммуникационных линиях связи). Этот уровень называется Quantum Bit Error Rate (QBER).
Происходит обсуждение результатов измерений по открытому каналу связи, причем и Алиса и Боб предполагают, что их могут подслушать, но не перехватить или изменить результаты. Сперва, они определяют, какие из фотонов были зарегистрированы Бобом. Затем, определяют, в каких случаях Боб угадал базис. Боб сообщает базис, в котором производилось измерение, но не сообщает сам результат. При этом теряется 50% информации – когда Боб неверно угадал базис. Если сообщение не подслушивалось, то Алиса и Боб делают вывод, что биты, закодированные этими фотонами, переданы правильно . Заметим, что по открытому каналу информация о случайной последовательности битов, посылаемых Алисой, не передается – вывод делается только на основе теории квантовых измерений! Каждый из переданных таким образом фотонов в правильном базисе несет один бит информации, а именно был ли он поляризован вертикально или горизонтально в лабораторном базисе или под углами плюс-минус 45 град. - в диагональном базисе. В итоге у Боба остается более короткий массив битов, который называется просеянным ключом .
Затем, Алиса и Боб проверяют, были ли попытки подслушивания во время распределения ключа. Для этого они сравнивают некоторые биты, которые, как они считают, были распределены правильно, по открытому каналу связи. Позиции битов по шкале синхронизационного протокола, должны выбираться случайно, скажем, сравнивая каждый третий бит. В этом случае обнаружение подслушивания имеет высокую вероятность и состоит в том, что Алиса и Боб имеют разные биты. Если сравнение не обнаруживает разницы, то Алиса и Боб делают вывод, что распределение ключа произошло с высокой степенью надежности (все же имеется вероятность не обнаружить подслушивания, но при этом, у подслушивателя окажется мало информации).
Последний шаг протокола квантовой криптографии состоит в том, чтобы используя классические алгоритмы, исправить ошибки
и уменьшить информацию, доступную Еве. Последняя процедура называется усилением секретности
(privacy amplification). Простейшая процедура коррекции ошибок
состоит в следующем. Алиса случайно выбирает пары битов и производит над ними операцию XOR. Боб выполняет такую же операцию над соответствующими своими битами. Если результат совпадает, они сохраняют первый из двух битов и уничтожают второй – поскольку сама процедура происходит по открытому каналу и результат доступен Еве. Если результаты отличаются – оба бита выкидываются (на практике используется более сложный алгоритм). После этой процедуры Алиса и Боб имеют одинаковые копии ключа, но у Евы все же может остаться некоторая информация о нем. Возникает необходимость в ее уменьшении – вступает в силу протоколы
усиления секретности
. Эти классические протоколы работают следующим образом. Алиса опять выбирает случайно пары битов и вычисляет их сумму по модулю 2 (XOR). Но в отличие от процедуры коррекции ошибок, она не сообщает это значение. Она лишь оглашает какие биты были выбраны, например, 103 и 539. Затем Алиса и Боб заменяют два бита на результат операции XOR. Таким образом Алиса и Боб укорачивают их ключи. Если Еве доступна лишь часть информации о двух битах, то ее информация о результате выполнения операции XOR будет еще меньше. Рассмотрим, например, случай, когда Еве известен только первый бит и ничего не известно про второй. Тогда она вообще ничего не знает про результат операции XOR. Если же Ева знает значения каждого из битов с вероятностью, скажем, 60%, то вероятность того, что она угадает значение операции XOR будет только 
(сумма вероятностей того, что оба бита угатаны неправильно и правильно, соответственно). Такую процедуру можно повторить несколько раз. Подчеркнем, что на этих этапах (выполнения протоколов коррекции ошибок и усиления секретности) работают исключительно классические протоколы, использующие открытые каналы связи. Итак, если вероятность ошибок не превосходит некоторой критической величины (в нерелятивистских схемах предел, по-видимому, составляет < 11% что определяется потерями в оптическом волокне), то далее возможна коррекция ошибок в нераскрытой части при помощи классических кодов и дальнейшее сжатие ключа (privacy amplification) для получение результирующего секретного ключа.
Включается абсолютно стойкий протокол одноразового блокнота через открытый канал связи.
Весь протокол повторяется каждый раз при необходимости посылки очередного сообщения.
Заметим, что на практике для передачи квантовых битов и обмена классическими сообщениями можно использовать один и тот же канал связи.
Замечание. Потери оптического волокна в окнах телеком составляют примерно: 1.55 мкм 0.2 дБ/км (0.2=10lgI 2 /I 1 , I 2 /I 1 =1.047); 1.31 мкм 0.35 дБ/км;
0.8 мкм 2 дБ/км.
Подслушивание в протоколе BB 84
Из-за того, что по квантовому каналу передается случайная смесь двух базисов, любая попытка подслушивания приводит к риску изменения поляризационного состояния фотона. Это приведет к различию в значениях битов Алисы и Боба, если измерения проводились в совпадающих базисах. Например, в некотором смысле, оптимальная стратегия подслушивания состоит в том, что Ева перехватывает все фотоны в квантовом канале, производит свои измерения только в одном из двух базисов (или вообще, только в одном) и ретранслирует исходы (т.н. стратегия перехватчик-ретранслятор ). Затем она пересылает Бобу (ретранслирует) другой кубит в состоянии, соответствующем результату ее измерения. Это не противоречит теореме о запрете копирования. В половине всех случаев Ева правильно угадает базис и, следовательно, Алиса-Боб не распознают ее присутствие. Однако, в другой половине случаев Ева неверно угадывает базис, поэтому она перешлет Бобу правильный кубит лишь в с вероятностью 50% (mutially unbiased bases). Этот кубит будет обнаружен Алисой-Бобом, в половине от этого числа случаев, т.к. они получат некоррелированные результаты (выявляется в протоколе коррекции ошибок). В итоге при использовании этой стратегии, Ева получает 50% информации - в случае угадывания базиса - в то время как Алиса-Боб получают 25% ошибочных битов в просеянном ключе, т.е. после выкидывания исходов в неправильных базисах. Этот случай подслушивания легко регистрируется. В другом варианте этой стратегии подслушивания Ева применяет ее только к каждому десятому биту. В этом случае она получает доступ к 5 процентам информации, в то время как Алиса и Боб обнаруживают 2.5%. Заметим, что рассмотренный случай активного подслушивателя в квантовом канале не взламывает протокола.
Вообще, анализируя ситуацию на этапе, когда Алиса и Боб имеют просеянный ключ и учитывая возможное присутствие Евы, можно сказать, что существует некоторая корреляция между классической информацией, доступной легитимным пользователям (Алисе и Бобу) и подслушивателем – Евой. Такая ситуация типична для классических криптографических протоколов. Чтобы анализировать ее количественно, вводится функция распределения , где все участники протокола – Алиса Боб и Ева описываются случайными параметрами , соответственно. Предположим, что такое совместное распределение вероятностей (классическое) существует. При этом Алиса и Боб обладают лишь маргинальным распределением . Задача состоит в том, чтобы ограничить доступную Еве информацию. Для данного распределения пока неизвестен критерий, дающий секретный ключ, распределенный между Алисой и Бобом или - условная энтропия. Однако существует некая граничная мера даваемая разностью между взаимной шенноновской информацией Алисы и Боба и взаимной информацией Евы 
:
Эта оценка показывает, что установление секретного ключа возможно, если Боб обладает большей информацией, чем Ева !
В приведенной только что аргументации есть слабое звено – мы предполагали, что Ева выполняет атаку до того, как Алиса и Боб включили процедуру коррекции ошибок. Формально это означает, что совместное распределение существует. Однако Ева может дождаться окончания протокола коррекции ошибок и только затем провести атаку. Такой вид атак называется «стратегией задержанного выбора »
Для нейтрализации активного подслушивателя в открытом канале можно воспользоваться схемой аутентификации Вегмана-Картера. В этой схеме Алиса и Боб должны изначально иметь небольшой секретный ключ, установленный, например, при личной встрече. С помощью такого ключа устанавливается нечто вроде «контрольной суммы» или метки, зависящей от каждого бита сообщения. Подслушиватель, который не знает ключа, имеет низкую вероятность сгенерировать правильную метку. Таким образом, метка устанавливает легитимность сообщения, а ее изменение указывает на попытку подслушивания.
Рассмотренный протокол ВВ84 является типичным и иллюстрирует основные принципы квантового распределения ключа. На его примере мы также рассмотрели некоторые протоколы коррекции ошибок, усиления секретности и стратегии подслушивателя. Рассмотрим некоторые другие протоколы квантовой криптографии.
Замечание. К очевидным недостаткам квантового распределения ключа следует отнести чисто практическую сложность их реализации. Квантовые состояния очень хрупки и подвержены сильному влиянию окружения, кроме того, они не могут быть усилены (простыми способами). Говоря о криптографических приложениях, пока не ясно как осуществить цифровую подпись или ability to settle disputes before judge.
ПРОТОКОЛ В92 [ 7 ]
Рассуждения, приведенные выше, основывались на том факте, что любое измерение неортогональных состояний, которое не возмущает их, в то же время не дает о них никакой информации (т.е. информации, позволяющей различить их). В 1992 году Ч.Беннет и Ж.Брассард предложили протокол распределения ключа, основанный на передаче только двух неортогональных состояний квантовой системы вместо четырех.
Рассмотрим два неортогональных состояния и , таких, что . Пусть и - два проектора в подпространства ортогональные состояниям и , соответственно. Заметим, что эти два оператора не коммутируют и что их индексы переставлены по отношению к соответствующим состояниям. Нетрудно убедиться, что оператор Р 0 уничтожает состояние :
но дает ненулевой результат при действии на :
В последнем соотношении фигурирует величина 
- вероятность ненулевого исхода. Аналогичные соотношения справедливы и для оператораР 1
.
Распределение ключей происходит следующим образом.
1. Устанавливается синхронизация моментов посылки состояний.
2. Алиса приготавливает и посылает Бобу случайную бинарную последовательность квантовых состояний и , где, например, , а .
3. Боб, независимо от Алисы, случайным образом решает, какой из двух операторов Р 0 или Р 1 применить к полученной последовательности состояний.
4. Затем Боб по открытому каналу сообщает Алисе номера синхронизационной шкалы, для которых он получил положительный результат. При этом он не сообщает, какой из двух операторов он использовал. Остальные события игнорируются
5. Если подслушивания не было, то оставленные события, составляющие приблизительно, -ую часть от общего числа испытаний, должны быть коррелированы. Заметим, что для поляризационного кодирования состояний “0 о ”и “45 о ”эта величина равна 1/2. Таким образом, если Алиса посылала , а Боб измерял Р 0 , если Алиса посылала , то Боб измерял Р 1 .
6. Перед тем, как Алиса и Боб установят секретный ключ, они должны провести процедуру коррекции ошибок и усиления секретности, действуя, например, так же как и в протоколе ВВ84. Жертвуя некоторыми битами, они убеждаются в идентичности некоторого их числа. Протокол иллюстрируется в таблице 2.
Итак, наше базовое предположение о невозможности извлечения однозначной информации об неортогональных состояниях без их возмущения, позволило ввести более простой, по сравнению с ВВ84, протокол. Однако, на практике, реализация такого протокола не нашла широкого применения. Дело в том, что все-таки существуют способы различимости двух неортогональных состояний, ценой некоторых потерь. Идея и соответствующие демонстрационные эксперименты основаны на том, что измерение, выполняемое в базисе, ортогональном, например, состоянию , однозначно выделяет такое состояние, в том смысле, что только состояние не пройдет через поляроид, ориентированный горизонтально. Другое же состояние пройдет через горизонтальный поляроид с 50%-ми потерями.
ЭПР-ПРОТОКОЛ [ 6 ]
В 1991 году А.Экерт предложил протокол основанный на перепутанных состояниях. Впоследствии оказалось, что этот протокол является разновидностью ВВ84, однако в обзорах по квантовым способам распределения ключа, как правило, он фигурирует отдельно. Примечательно также, что казалось бы, абсолютно умозрительные рассуждения, приведшие Эйнштейна, Подольского и Розена к их известному парадоксу, а также идеи, высказанные Дж.Беллом, все-таки нашли свое практическое воплощение. Сам А.Экерт, формулируя суть протокола, отмечал, что здесь «распределение ключа зависит от полноты квантовой механики». Под полнотой понимается тот факт, что квантовое описание обеспечивает максимально возможную информацию о рассматриваемой системе. Экспериментальная реализация рассматриваемого протокола, во всяком случае в принципиальном смысле, мало отличается от установок по наблюдению нарушения неравенств Белла. Можно сказать, что при распределении ключа вводится квантовый канал, где сам ключ существует без какого-либо «элемента реальности», связанного с этим ключом. В этом смысле он защищен полнотой квантовой механики.
Канал состоит из источника перепутанных фотонов, находящихся в синглетном состоянии. Частицы разлетаются вдоль оси z в направлениях к легитимным пользователям – Алисе и Бобу. Каждый из них получает по одной частице или половинке перепутанной пары. Затем Алиса и Боб выполняют измерение над свой частицей, ориентируя поляризационные призмы вдоль трех направлений: для Алисы – а i , для Боба – b j (i , j = 1, 2, 3 ). Конкретно, измеряя углы от вертикальной оси:
(17.16)
(17.17)
Алиса и Боб выбирают ориентацию призм случайно и независимо друг от друга для каждой пары перепутанных частиц. Каждое измерение дает результат либо +1, либо –1, т.е. срабатывает один из двух детекторов, установленных в выходных модах поляризационной призмы Алисы и Боба. Параметризованный таким образом сигнал представляет один (для одной частицы) бит информации.
где аргументы в корреляционных функциях Р означают выбранное направление. Например, означает вероятность того, что при данных установках поляризационных призм a i , b j Алиса получила результат «-1», а Боб «+1». Можно показать, что величина Е принимает значения
Для двух пар одинаковых ориентаций анализаторов (поляризационных призм)
квантово-механические предсказания дают полную антикорреляцию результатов, полученных Алисой и Бобом:
Следуя Клаузеру, Хорну, Шимони и Хольту можно ввести наблюдаемую величину - наблюдаемую Белла, составленную из корреляционных коэффициентов (17.18):
которая равна
После того, как перепутанные частицы поступили к Алисе и Бобу, те могут объявить по открытому каналу связи ориентации анализаторов, которые были выбраны случайным образом при каждом измерении. Затем, результаты измерений разделяются на две группы. К первой группе относятся результаты, полученные при разных ориентациях анализаторов, т.е., приводящие к (21). Ко второй – при одинаковых. Не учитываются те результаты, когда частица Алисы или Боба по каким-то причинам не была зарегистрирована вообще. Затем Алиса и Боб сообщают результат, который они получили только для первой группы измерений. Это позволяет им установить то значение S , которое для невозмущенных состояний частиц должно оказаться равным (21). В свою очередь последнее утверждение дает основание легитимным пользователям считать, что результаты, относящиеся ко второй группе измерений, антикоррелированы и могут быть преобразованы в секретный набор битов – сырой ключ .
Подслушиватель не может воспользоваться информацией, перехватывая перепутанные частицы, поскольку самой информации там нет. Считается, что она появляется в результате измерений, выполняемых Алисой. По Экерту измерение Алисы приготавливает состояние частицы Боба, хотя более последовательно было бы утверждать, что эта информация закодирована в корреляционных функциях Р и величине Е .
Литература
W. Diffie and M.E. Hellman, IEEE Trans. Inf. Theory IT-22, 644 (1977).
R. Rivest, A. Shamir, and L. Adleman, "On Digital Signatures and Public-Key Cryptosystems" , MIT Laboratory for Computer Science, Technical Report, MIT/LCS/TR-212 (January 1979).
P.W. Shor, Proceedings of the 35th Annual Symposium on the Foundations of Computer Science (IEEE Computer Society, Los Alamos, CA, 1994) p. 124.
C.H. Bennett, G. Brassard, and A.K. Ekert, "Quantum cryptography" , Scientific American, October 1992, p. 50.
S. Wiesner, SIGACT News 15 , 78 (1983); original manuscript written circa 1970. C.H. Bennett and G. Brassard, in "Proc. IEEE Int. Conference on Computers, Systems and Signal Processing", IEEE, New York (1984). C.H. Bennett, F. Bessette, G. Brassard, L. Salvail, and J. Smolin, "Experimental quantum cryptography," J. Cryptology 5 , 3 (1992).
A.K. Ekert, Phys. Rev. Lett. 67 , 661 (1991); A.K. Ekert, J.G. Rarity, P.R. Tapster, and G.M. Palma, Phys. Rev. Lett. 69 , 1293 (1992).
C.H. Bennett, Phys. Rev. Lett. 68 , 3121 (1992).
A. Muller, J. Breguet, and N. Gisin, Europhys. Lett. 23 , 383 (1993).
P.R. Tapster, J.G. Rarity and P.C.M. Owens, Phys. Rev. Lett. 73 , 1923 (1994).
P D. Townsend, J.G. Rarity, and P.R. Tapster, Electron. Lett. 29 , 1291 (1993).
D.Mayers, A.Yao, Unconditional Security in Quantum Cryptography, quant-ph/9802025.
E.Biham, M.Boyer, P.O.Boykin, T.Mor, V.Roychowdhury, A Proof of the Security of Quantum Key Distribution, quant-ph/9912053.
P.W.Shor, J.Preskill, Simple Proof of Security of the BB84 Quantum Key Distribution Protocol, quant-ph/0003004.
Эти наборы значений углов не являются единственными.
Квантовая физика предлагает абсолютно новый способ защиты информации. Зачем он нужен, разве сейчас нельзя проложить защищенный канал связи? Безусловно, можно. Но уже созданы и в тот момент, когда они станут распространены повсеместно, современные будут бесполезны, так как эти мощные компьютеры смогут взламывать их за доли секунды. Квантовая связь позволяет шифровать информацию при помощи фотонов — элементарных частиц.
Такие компьютеры, получив доступ к квантовому каналу, так или иначе изменят настоящее состояние фотонов. И попытка получить информацию приведет к ее повреждению. Скорость передачи информации, конечно, ниже, по сравнению с другими, ныне существующими каналами, например, с телефонной связью. Но квантовая связь обеспечивает гораздо больший уровень секретности. Это, естественно, очень большой плюс. Особенно в современном мире, когда киберпреступность растет с каждым днем.
Квантовая связь для "чайников"
Когда-то голубиная почта была вытеснена телеграфом, в свою очередь, телеграф вытеснило радио. Конечно, оно сегодня, но появились другие современные технологии. Всего десять лет назад Интернет не был распространен так, как сегодня и доступ к нему было получить достаточно сложно — приходилось ехать в интернет-клубы, покупать весьма дорогие карточки и т. д. Сегодня без Интернета мы не проживаем ни часа, и с нетерпением ждем 5G.
Но очередной новый стандарт связи не решит задачи, которые стоят сейчас перед организацией обмена данными при помощи Интернета, получения данных со спутников из поселений на других планетах и т. п. Все эти данные должны быть надежно защищены. А организовывать это можно при помощи так называемой квантовой запутанности.
Что же такое квантовая связь? Для "чайников" объясняют это явление как связь разных квантовых характеристик. Она сохраняется даже тогда, когда частицы разнесены друг от друга на большое расстояние. Зашифрованный и переданный при помощи квантовой запутанности ключ, не предоставит никакой ценной информации взломщикам, которые попытаются его перехватить. Все, что они получат — это другие цифры, так как состояние системы, при внешнем вмешательстве, будет изменено.
Но создать всемирную систему передачи данных не удавалось, так как уже через несколько десятков километров сигнал затухал. Спутник, запущенный в 2016 г., поможет реализовать схему квантовой передачи ключей на расстояния больше 7 тыс. км.
Первые успешные попытки использования новой связи
Самый первый протокол квантовой криптографии был получен в 1984 г. Сегодня эта технология успешно используется в банковской сфере. Известные компании предлагают созданные ими криптосистемы.
Квантовая линия связи осуществляется на стандартном оптоволоконном кабеле. В России первый защищенный канал был проложен между отделениями "Газпромабанка" в Новых Черемушках и на Коровьем валу. Общая длина равняется 30,6 км, ошибки при передаче ключа возникают, но их процент минимален — всего 5%.
Китай запустил спутник квантовой связи
Первый в мире подобный спутник был запущен в Китае. Ракета Long March-2D стартовала 16 августа 2016 г. с космодрома Цзю-Цюань. Спутник весом 600 кг будет 2 года летать по солнечно-синхронной орбите, высотой 310 миль (или 500 км) в рамках программы "Квантовые эксперименты в космическом масштабе". Период обращения аппарата вокруг Земли равняется полутора часам.
Спутник квантовой связи называется Micius, или "Мо-Цзы", в честь философа, который жил в V в.н.э. и, как принято считать, первым проводил оптические эксперименты. Ученые собираются изучить механизм и провести между спутником и лабораторией в Тибете.
Последняя передает квантовое состояние частицы на заданное расстояние. Для реализации этого процесса нужна пара запутанных (иначе говоря, сцепленных) частиц, находящихся на расстоянии друг от друга. Согласно квантовой физике, они способны улавливать информацию о состоянии партнера, даже находясь далеко друг от друга. То есть можно оказывать воздействие на частицу, которая находится в далеком космосе, воздействуя на ее партнера, который находится рядом, в лаборатории.
Спутник будет создавать два запутанных фотона и отправлять их на Землю. Если опыт будет удачным, он ознаменует собой начало новой эры. Десятки подобных спутников смогут не только обеспечить повсеместное распространение квантового интернета, но и квантовую связь в космосе для будущих поселений на Марсе и на Луне.
Зачем нужны такие спутники
Но зачем вообще нужен спутник квантовой связи? Разве уже существующих обычных спутников не достаточно? Дело в том, что эти спутники не будут заменять обычные. Принцип квантовой связи состоит в кодировании и защите существующих обычных каналов передачи данных. С ее помощью, например, уже обеспечивалась безопасность во время проведения парламентских выборов в 2007 году в Швейцарии.
Некоммерческая исследовательская организация Баттельский мемориальный институт, проводит обмен информацией между отделениями в США (штат Огайо) и в Ирландии (Дублин) используя квантовую запутанность. Принцип ее основан на поведении фотонов — элементарных С их помощью кодируется информация и отправляется адресату. Теоретически, даже самая аккуратная попытка вмешательства, оставит след. Квантовый ключ изменится сразу же, и хакер, предпринявший попытку, получит бессмысленный символьный набор. Поэтому все данные, которые будут передавать через эти каналы связи, невозможно перехватить или скопировать.
Спутник поможет ученым тестировать распределение ключа между наземными станциями и самим спутником.
Квантовая связь в Китае будет реализована благодаря оптоволоконным кабелям, общей протяженностью 2 тыс. км и объединяющих 4 города от Шанхая до Пекина. Серии фотонов бесконечно передаваться не могут, и чем больше расстояние между станциями, тем выше шанс того, что информация будет повреждена.
Пройдя какое-то расстояние, сигнал затухает, и ученым, для того чтобы поддерживать корректную передачу информации, нужен способ обновления сигнала спустя каждые 100 км. В кабелях это достигается с помощью проверенных узлов, в которых ключ анализируется, копируется новыми фотонами и идет дальше.
Немного истории
В 1984 г. Брассард Ж. из Монреальского университета и Беннет Ч. из IBM предположили, что фотоны можно использовать в криптографии для получения защищенного фундаментального канала. Ими была предложена простая схема квантового перераспределения шифровальных ключей, которая была названа ВВ84.
Схема эта использует квантовый канал, по которому информация между двумя пользователями передается в виде поляризованных квантовых состояний. Подслушивающий их хакер может попытаться измерить эти фотоны, но он не может это сделать, как сказано выше, не внеся в них искажения. В 1989 г. в Исследовательском центре IBM Брассард и Беннет создали первую в мире работающую квантово-криптографическую систему.
Из чего состоит квантово-оптическая криптографическая система (КОКС)
Основные теххарактеристики КОКС (коэффициент ошибок, скорость передачи данных и т.п.) определены параметрами образующих канал элементов, которые формируют, передают и измеряют квантовые состояния. Обычно КОКС состоит из приемной и передающей частей, которые связаны каналом передачи.
Источники излучения разделяются на 3 класса:
- лазеры;
- микролазеры;
- светоизлучающие диоды.
Для передачи оптических сигналов в качестве среды используют волоконно-оптические светодиоды, объединенные в кабели разной конструкции.
Природа секретности квантовой связи
Переходя от сигналов, в которых передаваемая информация кодируется импульсами с тысячами фотонов, к сигналам, в которых на один импульс, в среднем, приходится их меньше единицы, в действие вступают квантовые законы. Именно использование этих законов с классической криптографией позволяет достигать секретности.
Принцип неопределенности Гейзенберга применяется в квантово-криптографических аппаратах и благодаря ему любые попытки изменения в квантовой системе вносят в нее изменения, и формация, полученная в результате подобного измерения, определяется принимаемой стороной как ложная.
Дает ли квантовая криптография 100% гарантию от взлома?
Теоретически дает, но технические решения не совсем надежны. Злоумышленники стали использовать лазерный луч, с помощью которого они ослепляют квантовые детекторы, после чего те перестают реагировать на квантовые свойства фотонов. Иногда используются многофотонные источники, и взломщики могут получать возможность пропускать один из них и измерять идентичные.
Квантовая криптография - метод защиты коммуникаций, основанный на принципах квантовой физики . В отличие от традиционной криптографии , которая использует математические методы, чтобы обеспечить секретность информации , квантовая криптография сосредоточена на физике, рассматривая случаи, когда информация переносится с помощью объектов квантовой механики . Процесс отправки и приёма информации всегда выполняется физическими средствами, например, при помощи электронов в электрическом токе, или фотонов в линиях волоконно-оптической связи . Подслушивание может рассматриваться как изменение определённых параметров физических объектов - в данном случае, переносчиков информации.
Технология квантовой криптографии опирается на принципиальную неопределённость поведения квантовой системы, выраженную в принципе неопределённости Гейзенберга - невозможно одновременно получить координаты и импульс частицы, невозможно измерить один параметр фотона, не исказив другой.
Используя квантовые явления можно спроектировать и создать такую систему связи, которая всегда может обнаруживать подслушивание. Это обеспечивается тем, что попытка измерения взаимосвязанных параметров в квантовой системе вносит в неё нарушения, разрушая исходные сигналы, а значит, по уровню шума в канале легитимные пользователи могут распознать степень активности перехватчика.
Энциклопедичный YouTube
1 / 5
✪ Что такое квантовая криптография и криптовалюта? Нестандартная модель.
✪ Квантовая криптография - Сергей Кулик
✪ Квантовая криптография
✪ А.С. Трушечкин. Математика квантовой механики
✪ Квантовые технологии №7: криптография и связь
Субтитры
История возникновения
Впервые идея защиты информации с помощью квантовых объектов была предложена Стивеном Визнером в 1970 году. Спустя десятилетие Чарльз Беннет (IBM) и Жиль Брассар (Монреальский университет), знакомые с работой Визнера, предложили передавать секретный ключ с использованием квантовых объектов. В 1984 году они предположили возможность создания фундаментально защищённого канала с помощью квантовых состояний. После этого ими была предложена схема (BB84), в которой легальные пользователи (Алиса и Боб) обмениваются сообщениями, представленными в виде поляризованных фотонов, по квантовому каналу.
Описанный алгоритм носит название протокола квантового распределения ключа BB84 . В нём информация кодируется в ортогональные квантовые состояния. Помимо использования ортогональных состояний для кодирования информации, можно использовать и неортогональные состояния (например, протокол B92).
Алгоритм Беннета
В 1991 году Чарльзом Беннетом был предложен следующий алгоритм для выявления искажений в переданных по квантовому каналу данных:
- Отправитель и получатель заранее оговаривают произвольность расположения битов в строках, что определяет произвольный характер положения ошибок.
- Все строки разбиваются на блоки длины k. Где k выбирается так, чтобы минимизировать вероятность ошибки.
- Отправитель и получатель определят четность каждого блока, и сообщают её друг другу по открытому каналу связи. После этого в каждом блоке удаляют последний бит.
- Если четность двух каких-либо блоков оказалось различной, отправитель и получатель производят итерационный поиск неверных битов и исправляют их.
- Затем весь алгоритм выполняется заново для другого (большего) значения k. Это делается для того, чтобы исключить ранее незамеченные кратные ошибки.
- Чтобы определить все ли ошибки были обнаружены, проводится псевдослучайная проверка. Отправитель и получатель открыто сообщают о произвольной перестановке половины бит в строках, а затем вновь открыто сравнивают четности (Если строки различны, четности обязаны не совпадать с вероятностью 0,5). Если четности отличаются, отправитель и получатель производят двоичный поиск и удаляют неверные биты.
- Если различий не наблюдается, после n итераций отправитель и получатель будут иметь одинаковые строки с вероятностью ошибки 2 -n .
Физическая реализация системы
Рассмотрим схему физической реализации квантовой криптографии . Слева находится отправитель, справа - получатель. Для того, чтобы передатчик имел возможность импульсно варьировать поляризацию квантового потока, а приёмник мог анализировать импульсы поляризации, используются ячейки Поккельса . Передатчиком формируется одно из четырёх возможных состояний поляризации. На ячейки данные поступают в виде управляющих сигналов. Для организации канала связи обычно используется волокно, а в качестве источника света берут лазер.
На стороне получателя после ячейки Поккельса расположена кальцитовая призма, которая должна расщеплять пучок на две составляющие, улавливаемые двумя фотодетекторами (ФЭУ), а те, в свою очередь, измеряют ортогональные составляющие поляризации. Вначале необходимо решить проблему интенсивности передаваемых импульсов квантов, возникающую при их формировании. Если в импульсе содержится 1000 квантов, существует вероятность того, что 100 из них будут отведены криптоаналитиком на свой приёмник. После чего, проводя анализ открытых переговоров, он сможет получить все необходимые ему данные. Из этого следует, что идеален вариант, когда в импульсе количество квантов стремится к одному. Тогда любая попытка перехватить часть квантов неизбежно изменит состояние всей системы и соответственно спровоцирует увеличение числа ошибок у получателя. В этой ситуации следует не рассматривать принятые данные, а заново повторить передачу. Однако, при попытках сделать канал более надёжным, чувствительность приёмника повышается до максимума, и перед специалистами встаёт проблема «темнового» шума. Это означает, что получатель принимает сигнал, который не был отправлен адресантом. Чтобы передача данных была надёжной, логические нули и единицы, из которых состоит двоичное представление передаваемого сообщения, представляются в виде не одного, а последовательности состояний, что позволяет исправлять одинарные и даже кратные ошибки.
Для дальнейшего увеличения отказоустойчивости квантовой криптосистемы используется эффект Эйнштейна - Подольского - Розена , возникающий в том случае, если сферическим атомом были излучены в противоположных направлениях два фотона. Начальная поляризация фотонов не определена, но в силу симметрии их поляризации всегда противоположны. Это определяет тот факт, что поляризацию фотонов можно узнать только после измерения. Криптосхема на основе эффекта Эйнштейна - Подольского - Розена, гарантирующая безопасность пересылки, была предложена Экертом. Отправителем генерируется несколько фотонных пар, после чего один фотон из каждой пары он откладывает себе, а второй пересылает адресату. Тогда если эффективность регистрации около единицы и на руках у отправителя фотон с поляризацией «1», то у получателя будет фотон с поляризацией «0» и наоборот. То есть легальные пользователи всегда имеют возможность получить одинаковые псевдослучайный последовательности. Но на практике оказывается, что эффективность регистрации и измерения поляризации фотона очень мала.
Практические реализации системы
В 1989 году Беннет и Брассар в Исследовательском центре IBM построили первую работающую квантово-криптографическую систему. Она состояла из квантового канала, содержащего передатчик Алисы на одном конце и приёмник Боба на другом, размещённые на оптической скамье длиной около метра в светонепроницаемом полутораметровом кожухе размером 0,5 × 0,5 м. Собственно квантовый канал представлял собой свободный воздушный канал длиной около 32 см. Макет управлялся от персонального компьютера , который содержал программное представление пользователей Алисы и Боба, а также злоумышленника. В том же году передача сообщения посредством потока фотонов через воздушную среду на расстояние 32 см с компьютера на компьютер завершилась успешно. Основная проблема при увеличении расстояния между приёмником и передатчиком - сохранение поляризации фотонов. На этом основана достоверность способа.
Созданная при участии Женевского университета компания GAP-Optique под руководством Николаса Гисина совмещает теоретические исследования с практической деятельностью. Первым результатом этих исследований стала реализация квантового канала связи с помощью оптоволоконного кабеля длинной 23 км, проложенного по дну озера и соединяющего Женеву и Нион. Тогда был сгенерирован секретный ключ, уровень ошибок которого не превышал 1,4 %. Но все-таки огромным недостатком этой схемы была чрезвычайно малая скорость передачи информации. Позже специалистам этой фирмы удалось передать ключ на расстояние 67 км из Женевы в Лозанну с помощью почти промышленного образца аппаратуры. Но и этот рекорд был побит корпорацией Mitsubishi Electric, передавшей квантовый ключ на расстояние 87 км, правда, на скорости в один байт в секунду.
Активные исследования в области квантовой криптографии ведут IBM, GAP-Optique, Mitsubishi , Toshiba , Национальная лаборатория в Лос-Аламосе , молодая компания MagiQ и холдинг QinetiQ , поддерживаемый британским министерством обороны. В частности, в национальной лаборатории Лос-Аламоса была разработана и начала широко эксплуатироваться опытная линия связи, длиной около 48 километров. Где на основе принципов квантовой криптографии происходит распределение ключей, и скорость распределения может достигать несколько десятков кбит/с.
В 2001 году Эндрю Шилдс и его коллеги из TREL и Кембриджского университета создали диод, способный испускать единичные фотоны. В основе нового светодиода лежит «квантовая точка » - миниатюрный кусочек полупроводникового материала диаметром 15 нм и толщиной 5 нм, который может при подаче на него тока захватывать лишь по одной паре электронов и дырок. Это дало возможность передавать поляризованные фотоны на большее расстояние. В ходе экспериментальной демонстрации удалось передать зашифрованные данные со скоростью 75 Кбит/с - при том, что более половины фотонов терялось.
В Оксфордском университете ставятся задачи повышения скорости передачи данных. Создаются квантово-криптографические схемы, в которых используются квантовые усилители. Их применение способствует преодолению ограничения скорости в квантовом канале и, как следствие, расширению области практического применения подобных систем.
Квантовый криптоанализ
Широкое распространение и развитие квантовой криптографии не могло не спровоцировать появление квантового криптоанализа, который в ряде случаев обладает, согласно теории, преимуществами перед обычным. Рассмотрим, например, всемирно известный и распространенный в наши дни алгоритм шифрования RSA (1977). В основе этого шифра лежит идея того, что на простых компьютерах невозможно решить задачу разложения очень большого числа на простые множители, ведь данная операция потребует астрономического времени и экспоненциально большого числа действий. Другие теоретико-числовые методы криптографии могут быть основаны на проблеме дискретного логарифмирования . Для решения этих двух проблем был разработан квантовый алгоритм Шора (1994), позволяющий найти за конечное и приемлемое время все простые множители больших чисел или решить задачу логарифмирования, и, как следствие, взломать шифры RSA и ECC . Поэтому создание достаточно крупной квантовой криптоаналитической системы является плохой новостью для RSA и некоторых других асимметричных систем. Необходимо только создание квантового компьютера, способного исполнить необходимый алгоритм.
По состоянию на 2012 год наиболее продвинутые квантовые компьютеры смогли разложить на множители числа 15 (в 150 тыс. попыток верный ответ был получен в половине случаев, в соответствии с алгоритмом Шора ) и 21.
Уязвимость реализаций квантовой системы
В 2010 году учёные успешно опробовали один из возможных способов атаки, показав принципиальную уязвимость двух реализаций криптографических систем, разработанных компаниями ID Quantique и MagiQ Technologies . И уже в 2011 году работоспособность метода была проверена в реальных условиях эксплуатации, на развёрнутой в Национальном университете Сингапура системе распространения ключей, которая связывает разные здания отрезком оптоволокна длиной в 290 м.
В эксперименте использовалась физическая уязвимость четырёх однофотонных детекторов (лавинных фотодиодов), установленных на стороне получателя (Боба). При нормальной работе фотодиода приход фотона вызывает образование электронно-дырочной пары, после чего возникает лавина, а результирующий выброс тока регистрируется компаратором и формирователем импульсов. Лавинный ток «подпитывается» зарядом, хранимым небольшой ёмкостью (≈ 1,2 пФ), и схеме, обнаружившей одиночный фотон, требуется некоторое время на восстановление (~ 1 мкс).
Если на фотодиод подавать такой поток излучения, когда полная перезарядка в коротких промежутках между отдельными фотонами будет невозможна, амплитуда импульса от одиночных квантов света может оказаться ниже порога срабатывания компаратора.
В условиях постоянной засветки лавинные фотодиоды переходят в «классический» режим работы и выдают фототок, пропорциональный мощности падающего излучения. Поступление на такой фотодиод светового импульса с достаточно большой мощностью, превышающей некое пороговое значение, вызовет выброс тока, имитирующий сигнал от одиночного фотона. Это и позволяет криптоаналитику (Еве) манипулировать результатами измерений, выполненных Бобом : она «ослепляет» все его детекторы с помощью лазерного диода, который работает в непрерывном режиме и испускает свет с круговой поляризацией, и по мере надобности добавляет к этому линейно поляризованные импульсы. При использовании четырёх разных лазерных диодов, отвечающих за все возможные типы поляризации (вертикальную, горизонтальную, ±45˚), Ева может искусственно генерировать сигнал в любом выбранном ею детекторе Боба .
Опыты показали, что схема взлома работает очень надёжно и даёт Еве прекрасную возможность получить точную копию ключа, переданного Бобу . Частота появления ошибок, обусловленных неидеальными параметрами оборудования, оставалась на уровне, который считается «безопасным».
Однако, устранить такую уязвимость системы распространения ключей довольно легко. Можно, к примеру, установить перед детекторами Боба источник одиночных фотонов и, включая его в случайные моменты времени, проверять, реагируют ли лавинные фотодиоды на отдельные кванты света.
Plug & Play
Практически все квантово-оптические криптографические системы сложны в управлении и с каждой стороны канала связи требуют постоянной подстройки. На выходе канала возникают беспорядочные колебания поляризации ввиду воздействия внешней среды и двойного лучепреломления в оптоволокне. Но недавно [когда? ] была сконструирована [кем? ] такая реализация системы, которую можно назвать Plug and Play («подключай и работай»). Для такой системы не нужна подстройка, а только синхронизация. Система построена на использовании зеркала Фарадея, которое позволяет избежать двойного лучепреломления и, как следствие, не требует регулировки поляризации. Это позволяет пересылать криптографические ключи по обычным телекоммуникационным системам связи. Для создания канала достаточно лишь подключить приёмный и передающий модули и провести синхронизацию.
Перспективы развития
Сейчас одним из самых важных достижений в области квантовой криптографии является то, что ученые смогли показать возможность передачи данных по квантовому каналу со скоростью до единиц Мбит/с. Это стало возможно благодаря технологии разделения каналов связи по длинам волн и их единовременного использования в общей среде. Что кстати позволяет одновременное использование как открытого, так и закрытого канала связи. Сейчас [ ] в одном оптическом волокне возможно создать около 50 каналов. Экспериментальные данные позволяют сделать прогноз на достижение лучших параметров в будущем:
- достижение скорости передачи данных по квантовому каналу связи в 50 Мбит/с, при этом единовременные ошибки не должны будут превышать 4 %;
- создание квантового канала связи длиной более 100 км;
- организация десятков подканалов при разделении по длинам волн.
На данном этапе квантовая криптография только приближается к практическому уровню использования. Диапазон разработчиков новых технологий квантовой криптографии охватывает не только крупнейшие мировые институты, но и маленькие компании, только начинающие свою деятельность. И все они уже способны вывести свои проекты из лабораторий на рынок. Все это позволяет сказать, что рынок находится на начальной стадии формирования, когда в нём могут быть на равных представлены и те и другие.
, № 37, 2007 ;
Вы читаете гостевой пост Романа Душкина (Blogspot , ЖЖ , Twitter). Также вас могут заинтересовать другие заметки за авторством Романа:
- Алгоритм Шора, его реализация на языке Haskell и результаты некоторых опытов ;
- Факторизация числа при помощи квантового алгоритма Гровера ;
- Квантовый зоопарк: карта отношений квантовых алгоритмов ;
- … и далее по ссылкам;
Если вы интересуетесь криптографией, попробуйте еще обратить внимание на заметки Эллиптическая криптография на практике и Памятка по созданию безопасного канала связи моего авторства.
Вся история криптографии основывается на постоянном противоборстве криптографов м криптоаналитиков. Первые придумывают методы сокрытия информации, а вторые тут же находят методы взлома. Тем не менее, теоретически показано, что победа в такой гонке вооружений всегда останется на стороне криптографов, поскольку имеется абсолютно невзламываемый шифр — одноразовый блокнот. Так же есть некоторые очень сложно взламываемые шифры, для получения скрытой информации без пароля из которых у криптоаналитика практически нет шансов. К таким шифрам относятся перестановочные шифры посредством решеток Кардано, шифрование при помощи редких текстов в виде ключей и некоторые другие.
Все перечисленные методы достаточно просты для применения, в том числе и одноразовый блокнот. Но все они обладают существенным недостатком, который называется проблемой распределения ключей . Да, одноразовый блокнот невозможно взломать. Но чтобы использовать его, необходимо иметь очень мощную инфраструктуру по распространению этих самых одноразовых блокнотов среди всех своих адресатов, с которыми ведется секретная переписка. То же самое касается и других подобных методов шифрования. То есть перед тем, как начать обмен шифрованной информацией по открытым каналам, необходимо по закрытому каналу передать ключ. Даже если ключом обмениваться при личной встрече, у криптоаналитика всегда имеются возможности по альтернативному способу добывания ключений (от ректального криптоанализа не защищен практически никто).
Обмен ключами при личной встрече — это очень неудобная штука, которая серьезно ограничивает использование абсолютно невзламываемых шифров. Даже государственные аппараты очень небедных государств позволяют себе это только для очень немногих серьезных людей, занимающих сверхответственные должности.
Однако, в конце концов, был разработан протокол обмена ключами, который позволил сохранять секрет при передаче ключа по открытому каналу (протокол Диффи-Хеллмана). Это был прорыв в классической криптографии, и по сей день этот протокол с модификациями, защищающими от атак класса MITM , используется для симметричного шифрования. Сам протокол основан на гипотезе о том, что обратная задача для вычисления дискретного логарифма является очень сложной. Другими словами, этот стойкость этого протокола зиждется только на том, что на сегодняшний день не существует вычислительных мощностей или эффективных алгоритмов для дискретного логарифмирования.
Проблемы начнутся тогда, когда будет реализован квантовый компьютер достаточной мощности. Дело в том, что Питер Шор разработал квантовый алгоритм , который решает не только задачу факторизации, но и задачу поиска дискретного логарифма. Для этого квантовая схема незначительно изменяется, а принцип работы остается тем же. Так что хитроумный изобретатель одним ударом убил двух криптографических зайцев — асимметричную криптографию RSA и симметричную криптографию Диффи-Хеллмана. Все пойдет прахом, как только на свет появится он, универсальный квантовый компьютер (не факт, что его еще нет; просто мы можем об этом даже и не знать).
Но модель квантовых вычислений как повергла криптографов в шок и трепет, так и дала им новую надежду. Именно квантовая криптография позволила придумать новый метод распределения ключей, в котором отсутствуют многие проблемы схемы Диффи-Хеллмана (например, простая атака MITM абсолютно не поможет в силу чисто физических ограничений квантовой механики). Более того, квантовая криптография устойчива и к квантовым алгоритмам поиска ключей, так как основана на совершенно ином аспекте квантовой механики. Так что сейчас мы изучим квантовый метод секретного обмена ключами по открытому каналу.
Одним и, наверное, единственным практическим успехом квантовой информатики на сегодняшний день стало появление квантовой криптографии. В настоящий момент существуют и коммерчески доступны устройства квантовой криптографии, созданные на описанных ниже принципах.
Задача криптографии заключается в защите от прослушивания сообщения при передаче его по незащищенному каналу. Решение заключается в том, что нужно предварительно обменяться секретными данными - ключом - и использовать его для передачи сообщения, применяя шифрование . Доказано, что такой подход может обеспечить абсолютную надежность при условии, что размер ключа не меньше размера самого передаваемого сообщения. Неудобство такого подхода очевидно, поэтому на практике применяется компромиссный метод, в котором ключ существенно меньше сообщения, но характер используемых криптопреобразований таков, что не существует алгоритма, позволяющего за приемлемое для взломщика время восстановить исходное сообщение из подслушанных им данных.
Пространство квантовых состояний
Квантовая система, находящаяся в состоянии А, изображается:
В случае, если состояние A = 0, то кет-вектор обозначают как и говорят, что в данном случае квантовая система не существует.
Представление системы в виде волновой функции эквивалентно представлению в виде вектора состояния , то есть:
Множество кет-векторов образует комплексное векторное пространство (определено умножение векторов на комплексные числа).
Следовательно, для любого комплексного числа α верно следующее утверждение:
Произвольный вектор пространства может быть представлен как линейная комбинация базисных векторов:
Суперпозиция квантовых состояний
Пусть и - представления произвольной квантовой системы в виде волновых функций , тогда суперпозицией данных функций называется такая волновая функция , что:
Для кет-векторов:
Пусть и - представления произвольной квантовой системы в виде кет-векторов, тогда суперпозицией данных векторов называется такой кет-вектор , что:
Сопряженное пространство
Каждому кет-вектору сопоставим сопряженный ему бра-вектор
Причем, если , то 
Множество бра-векторов образует сопряженное пространство состояний. Сопряженные пространства эквивалентны друг другу.
Скалярное произведение
Каждой паре векторов и по некоторому правилу сопоставим комплексное число - скалярное произведение
Если состояния изображаются волновыми функциями, то
Два вектора ортогональны, если 
В N-мерном прос-ве любая совокупность из N взаимно ортогональных векторов составляет линейно независимую систему и может использоваться в качестве (ортогонального) базиса. Такой базис называется ортонормированным, если нормирован каждый из базисных векторов. Набор векторов называют ортонормированным, если все вектора в нем единиичные и любые два различных вектора ортогональны, то есть для всех индексов i и j, причем
Различение квантовых состояний
Различимость квантовых состояний проще всего понять на примере игры с двумя участниками - Алисой и Бобом. Алиса выбирает состояние из некоторого фиксированного набора состояний, известного обоим участникам. Она передает состояние Бобу, цель которого - определить индекс i этого состояния.
Предположим, что состояния образуют ортонормированный набор. Тогда Боб может различить эти состояния с помощью квантового измерения, операторы которого задаются следующим образом: 
- по одному на каждый индекс i, плюс, дополнительный оператор измерения M0, равный квадратному корню из неотрицательного определенного оператора I:
Эти операторы удовлетворяют условию полноты , и если приготовлено состояние , то , то есть результат i получается с вероятностью 100%. Следовательно, можно с уверенностью утверждать, что можно различить ортонормированные состояния
Напротив, если состояния не образуют ортонормированного набора, то можно доказать, что не существует квантового измерения, различающего эти состояния. Идея заключается в том, что Боб будет делать измерение, описываемое операторами Mj, дающими результаты j. В зависимости от результата измерения Боб пыатется угадать, какому индексу i соответствовало исходное состояние. Для этого он использует некоторое правило (функцию i = f(j)). Причина, по которой Боб не может различить неортогональные состояния и состоит в следующем: раскладывается в сумму компоненты, параллельной вектору , и компоненты, ортогональной вектору . Пусть j - такой результат измерения, что f(j) = 1, то есть Боб определяет, что сначала система была в состоянии , если он получает в качестве результата j. Но поскольку у вектора есть составляющая, параллельная вектору , существует ненулевая вероятность того, что результат j был получен и в том случае, когда исходным было состояние .
Принципы безопасности квантового распределения ключа
Принцип неопределенности Гейзенберга
Безопасность основана на том, что если злоумышленник будет использовать несовпадающий базис, то состояние будет изменено.
Принцип обнаружения подслушивающего
Утверждение: при попытке различить два неортогональных квантовых состояния извлечение информации сопровождается возмущением сигнала.
Пусть и - неортогональные квантовые состояния, о которых Ева пытается получить информацию. Тогда процесс, который Ева использует для получения, представляет собой унитарное взаимодействие состояния или с вспомогательной системой, приготовленной в стандартном состоянии . Допуская, что этот процесс не нарушает ни одно из состояний получаем
Для Евы желательно, чтобы и были различными, с тем, чтобы она могла получить информацию о состоянии.
Однако, поскольку скалярные произведения сохраняются при унитарных преобразованиях, должны выполняться следующие равенства
откуда следует, что и должны совпадать. Таким образом, установление различия между и должно неизбежно нарушить, по меньшей мере, одно из этих состояний. Итак, проверяя переданные данные состояния на предмет нарушения, Алиса и Боб получают верхнюю оценку любого шума и подслушивания, которые имеют место в их канале связи.
Теорема о невозможности клонирования квантовых состояний
Предположим, что у нас есть квантовая машина с двумя слотами,
обозначенными как А и Б. Слот А, слот данных, вначале находится в неизвестном, но чистом квантовом состоянии . Это то самое состояние, которое должно быть скопировано в слот Б, целевой слот.
Предположим, что целевой слот изначально находится в некотором стандартном чистом состоянии . Следовательно, начальное состояние копирующего устройства имеет вид
Некоторое унитарное преобразование U производит процедуру копирования, которая в идеальном виде выглядит так:
Пусть данная процедура копирования выполняется для двух чистых состояний и . Тогда имеем,
Взяв скалярное произведение этих двух уравнений получим:
Но такое уравнение имеет только два решения: 0 и 1, поэтому либо = , либо и ортогональны. Следовательно, устройство копирования может копировать только те состояния, которые ортогональны друг другу и поэтому универсальное квантовое устройство копирования невозможно.
Потенциальное квантовое устройство копирования не может, например, копировать кубитовые состояния = и , поскольку эти состояния не ортогональны.
Принцип кодирования для протокола BB-84
Алиса начинает с двух строк a и b, каждая из которых содержит 
случайных классических битов. Затем она кодирует эти строки блоком кубитов по формуле:
где ak - k-тый бит a (и так же для b), а состояния задаются как
Полученные состояния отправляются Бобу. Боб измеряет принимаемые фотоны в одном из двух базисов, выбираемых независимо от Алисы, затем изменяет каждый кубит в базисе случайным образом. Для каждого переданного состояния Боб открыто сообщает в каком базисе проводилось измерение кубита . Алиса открыто вообщает в каких случаях ее базис совпал с базисом Боба. Если базисы совпали - бит оставляют. Если нет - игнорируют. В таком случае ключ прорежается примерно на 50%. Такой ключ называется "просеянным". В итоге Боб и Алиса имеют (при условии отсутствия подслушивания и шумов в канале связи) полностью коррелироавнную строку случайных битов.
В случае, если имело место прослушивание, по величине ошибки в канале связи Алиса и Боб могут оценить максимальное количество информации, доступное Еве. Считается, что в случае, если ошибка в канале не превышает 11%, то информация, доступная Еве, заведомо не превосходит взаимной информации между Алисой и Бобом, следовательно, передача данных возможна.
Важно отметить, что канал связи между Алисой и Бобом не должен быть конфиденциальным, но обязан быть аутентифицированным. То есть любой злоумышленник может получать из него информацию, но не может изменять её.
Квантовая криптография в применении к классической криптографии
Алгоритм Шора
Выберем q - степень двойки между и 2.
Предположим, что r|q (простой случай). Тогда применим операцию Уолша-Адамара к первому регистру Получем:
Вычислим mod n (тоже за логарифм):
Пронаблюдаем второй регистр, получим mod n для случайного s < r, а в первом - суперпозиция s, r+s, 2r+s, ..., q-r+s:
Снова применим операцию Уолша-Адамара:
Сумма в скобках не равна нулю в случае, если частное rb и q - целое число, то есть ненулевая амплитуда будет только у чисел, делящихся на q/r.
Пронаблюдав первый регистр получим случайное число вида cq/r. То есть с большой вероятностью (а точнее - порядка 1/(loglog(q)) c и r взаимно просты. Сократив получившуюся дробь получаем r.
Сложный случай: r |/q На последнем шаге все равно будет дробь типа b/q, но:
На интервале длины 1/q < 1/ будет не больше одной дроби со знаменателем меньше n. Эта дробь должна быть c/r.
Этот же алгоритм подойдет и для дискретного логарифма, ведь на самом деле ищется период элемента x некоторой коммутативной группы.
Если даны G =
Следовательно, алгоритм Шора применим ко всем коммутативной криптографии.
Алгоритм Гровера
Пусть дана булева функция . Цель: найти хотя бы один корень уравнения f(x) = 1. На классическом компьютере, если f - произвольна нам понадобится O(N) операций, где , то есть, полный перебор. Если f в конъюнктивой нормальной форме - то данная задача является NP-полной.
К сожалению, или к счастью, не известен квантовый(а классический тем более) для решения данной задачи за полиномиальное время. Но алгоритм Гровера позволяет получить квадратичное ускорение для полного перебора - за .
Описание алгоритма:
Используя n+1 кубит, мы приготавливаем первые n кубитов в суперпозицию всех возможных состояний, а последний в суперпозицию «нуля» и «единицы», но со «знаком минус» у «единицы». Тогда действуя раз оператором поворота, мы получаем состояние, при измерении которого с очень высокой вероятностью получаем решение уравнения.
Применение алгоритма:
Гроверовский «подскок амплитуды» является, по-видимому, фундаментальным физическим феноменом в квантовой теории многих тел. Например, его учет необходим для оценки вероятностей событий, которые кажутся «редкими». Процесс, реализующий схему GSA, приводит к взрывному росту первоначально пренебрежимо малой амплитуды, что способно быстро довести ее до реально наблюдаемых величин.
Алгоритм Гровера также может быть использован для нахождения медианы и среднего арифметического числового ряда. Кроме того, он может применяться для решения NP-полных задач путем исчерпывающего поиска среди множества возможных решений. Это может повлечь значительный прирост скорости по сравнению с классическими алгоритмами, хотя и не предоставляя «полиномиального решения» в общем виде.
Строго доказано, что время работы алгоритма Гровера для поиска информации в неупорядоченной базе данных равно корню квадратному от того времени, что необходимо для аналогичного поиска компьютеру классическому. Но, более того, квадратный корень – это вообще наилучший результат, который может быть теоретически достигнут.
Квантовые компьютеры
История развития квантовых компьютеров
Исследователям из Массачусетского технологического института удалось впервые распределить один кубит между тремя ядерными спинами в каждой молекуле жидкого аланина или молекулы трихлороэтилена. Такое распределение позволило использовать «запутанность» для неразрушающего анализа квантовой информации.
В марте ученые из Национальной лаборатории в Лос Аламосе объявили о создании 7-кубитного квантового компьютера в одной единственной капле жидкости.
Демонстрация вычисления алгоритма Шора специалистами из IBM и Стэнфордского университета на 7-кубитном квантовом компьютере.
В институте квантовой оптики и квантовой информации при Иннсбрукском университете впервые удалось создать кубайт (сочетание 8 кубитов) с помощью ионных ловушек.
Канадская компания D-Wave продемонстрировала первый 16-кубитный квантовый компьютер, способный решать целый ряд задач и головоломок, типа судоку.
С 2011 года D-Wave предлагает за $11 млн долларов квантовый компьютер D-Wave One с 128-кубитным чипсетом, который выполняет только одну задачу – дискретную оптимизацию.
Современные квантовые компьютеры
MagicQ
Основана в 1999 году в США для целей армии США и флота, NASA, DARPA, JTRS. В 2004 году на основе устройств Magic QPN 8505 в DARPA была создана первая в мире сеть с использованием квантовых технологий.
Квантовый канал объединил три ВУЗа, принимавших участие в разработке.
id Quantique
Компьютеры D-Wave
Компания D-Wave представила компьютерную систему, построенную на основе принципиально нового вида процессора. Система называется D-Wave One.
Процессор D-Wave One (кодовое имя Rainier) разработан для выполнение одной единственной математической операции - дискретной оптимизации. Это процессор специального назначения. В процессе разработки приложений D-Wave One используется только в тех частях программы, которые непосредственно решают задачу оптимизации. Остальные части приложения работают на традиционных системах.
Rainer решает задачу оптимизации используя квантовый отжиг (quantum annealing, QA), который относится к классу методов, основанных на использовании квантовых эффекты для поиска оптимального решения в кратчайшее время. Так как D-Wave One является квантовым компьютером, многие склонны думать, что разработка приложений для такой системы может быть действительно сложным делом. Основная сложность возникает из за необходимости объединить знания из областей, которые обычно не пересекаются, таких как квантовая физика и машинное обучение.
Проблемы перехода на квантовые компьютеры
Стоимость
Канадская компания D-Wave выпустила в продажу «первый в мире доступный коммерческий квантовый компьютер». Его цена составила 10 миллионов долларов, сообщает техноблог Engadget. Этот компьютер в состоянии оперировать 129 кубитами. Считается, что для решения некоторых практических задач, такого количества простых квантовых ячеек памяти, которые связаны между собой в единую систему, может оказаться вполне достаточно.
Изучение находится на раннем этапе
Серия тестов показала, что квантовый компьютер D-Wave, описанный выше, не дает никакого выигрыша в скорости по сравнению с компьютерами обычными, классическими. Попросту говоря, не только ученые, тестирующие D-Wave, пока не смогли увидеть ни одной реальной задачи, где квантовый компьютер мог бы убедительно продемонстрировать свое вычислительное превосходство, но даже сама компания-изготовитель понятия не имеет, что это может быть за задача.
Необходимость ограниченному числу пользователей
По мнению д-ра Питера Шора, несмотря на свою потенциальную мощь, квантовые компьютеры вовсе не обязательно будут выполнять все задачи быстрее классических компьютеров. В действительности, по его оценкам, работоспособный квантовый компьютер каждую из операций будет выполнять даже медленнее, чем компьютер обычный. И лишь для некоторых проблем, там, где исследователи обнаружили методы эффективного использования возможностей столь гигантских объемов хранимой информации, научившись выделять нужный ответ за сравнительно небольшое количество шагов (намного меньшее, чем в классических компьютерах) – появляется возможность существенно ускорить вычисления.
Сложность управления и обслуживания
Даже одна случайная молекула воздуха или другой малейший "шум" в системе способны выбивать кубиты из когерентной сцепленности.
Ошибки в ходе вычислений
Еще одна огромная трудность – это исправление ошибок, неизбежно возникающих в процессе вычислений. В столь тонком устройстве хранимые состояния могут непреднамеренно воздействовать друг на друга, в результате чего операции могут применяться не к тем квантовым битам.
Ограничения квантовой криптографии
- Требуется обязательное наличие выделенной линии вследствие ряда факторов:
- Квадратичное возрастание линий с возрастанием числа пользователей.
- Оптическая линия связи БЕЗ оптических усилителей.
Список литературы
Перейти к списку литературы по разделу "Квантовая криптография".
Андрюхин Б9-04 Покидова Б9-04