Квантовый компьютер и квантовая криптография: перспективы

07.03.2018

Квантовый скачок #

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

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

Основой квантового компьютера является некоторое количество кубит. В отличие от классического бита, кубит может находится не только в двух основных состояниях, но и в бесконечном числе “промежуточных” состояний - так называемая квантовая суперпозиция. По окончании процесса вычислений измерение состояния кубита дает классическую информацию: либо 0, либо 1. За счет квантовой суперпозиции (свойство квантовой системы одновременно находиться в двух взаимоисключающих состояниях) большие объемы данных могут обрабатываться одновременно (квантовый параллелилизм), что потенциально может позволить квантовым компьютерам превзойти классические. Еще фундаментальным свойством кубита является квантовая запутанность. Это свойство кубита, когда квантовые состояния двух или большего числа объектов оказываются взаимозависимыми.

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

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

Трудоемкость определения ключа длины n бит некоторого шифра методом тотального перебора можно оценить величиной порядка 2ⁿ операций шифрования на классическом компьютере. Трудоемкость нахождения прообраза криптографической хэш-функции с длиной хэш-кода n бит методом тотального перебора также оценивается величиной порядка 2ⁿ операций вычисления значения хэш-функции на классическом компьютере. Считается, что указанные задачи могут быть решены на квантовом компьютере с использованием порядка 2^n/2 операций шифрования или вычисления значения хэш-функции соответственно.

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

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

Квантовый компьютер: перспективы реализации #

Существует несколько подходов к физической реализации квантового компьютера. Но можно констатировать, что на данный момент ни один из них не привел к успеху. Объявления о создании 53-кубитном или даже 72-кубитного квантового компьютера (кубит – аналог бита классического компьютера) как правило вызывают недоверие специалистов. Физической реализации квантового компьютера препятствует множество причин, основной из которых, наверное, является квантовая декогеренция (необратимое взаимодействие квантовой системы с окружающей средой). Это означает, что либо квантовую систему следует максимально изолировать от окружающей среды, либо осуществлять вычисления быстрее, чем время, за которое влияние декогеренции становится существенным.

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

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

Квантовые каналы связи: перспективы #

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

Квантовые каналы связи для распределения/выработки общего ключа уже неоднократно реализованы на практике. Линии связи могут простираться на несколько сот километров. Ряд компаний осуществляет продажу систем квантового распределения ключа (id Quantique, MagiQ Technologies, SmartQuantum, Quintessence Labs, QApp). Крупные системы квантового распределения ключа развернуты в Вене и Токио. В России создан Российский Квантовый Центр и над проблематикой как постквантовой криптографии, так и квантового распределения ключей работают многие компании.

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

Вспомогательная литература #

1. М. Нильсен, И. Чанг, Квантовые вычисления и квантовая информация, М., «Мир», 2006.

2. Peter W. Shor, Algorithms for quantum computation: discrete logarithms and factoring., in Shafi Goldwasser (editor), 35th annual IEEE symposium on the foundations of computer science. Proceedings of the IEEE symposium held in Santa Fe, NM, November 20-22, 1994, IEEE, 1994. ISBN 0-8186-6580-7 (1994), 124-134.

3. Peter W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing 26 (1997), 1484-1509.

4. Christof Zalka, Fast versions of Shor’s quantum factoring algorithm (1998). URL:http://arxiv.org/abs/quant-ph/9806084.

5. Lov K. Grover, A fast quantum mechanical algorithm for database search, in , Proceedings of the twenty-eighth annual ACM symposium on the theory of computing, held in Philadelphia, PA, May 22-24, 1996, Association for Computing Machinery, 1996. ISBN 0-89791-785-5 (1996), 212-219.

6. Lov K. Grover, Quantum mechanics helps in searching for a needle in a haystack, Physical Review Letters 79 (1997), 325-328.

7. Lov K. Grover, Terry Rudolph, How significant are the known collision and element distinctness quantum algorithms?, Quantum Information & Computation 4 (2003), 201-206. URL: http://arxiv.org/abs/quant-ph/0309123.

8. Michel Boyer, Gilles Brassard, Peter Hoyer, Alain Tapp, Tight bounds on quantum searching (1996). URL: http://arxiv.org/abs/quant-ph/9605034v1.

9. Gilles Brassard, Peter Hoyer, Alain Tapp, Quantum cryptanalysis of hash and claw-free functions, in Claudio L. Lucchesi, Arnaldo V. Moura (editors), LATIN'98: theoretical informatics. Proceedings of the 3rd Latin American symposium held in Campinas, April 20-24, 1998, Lecture Notes in Computer Science, 1380, Springer, 1998. ISBN 3-540-64275-7 (1998), 163-169.