Квантовые компьютеры: надежды и реальность

 

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

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

 

Для начала напомним, что квантовым компьютерам начало положили два основных открытия, за которые их авторы удостоились Нобелевской премии. В 1918 году Макс Планк открыл квант, а Альберт Эйнштейн в 1921 году фотон. [1], [2]. Идея создания квантового компьютера зародилась в 1980 году, когда было доказано об истинности квантовой теории. А идеи начали воплощаться в практику только в 1998 году. Массовые, и при этом достаточно результативные работы, проводятся только в последние 15 лет. Основные принципы понятны, но с каждым шагом вперед возникает все больше проблем, разрешение которых занимает достаточно много времени, хотя этой проблемой занимается очень много лабораторий во всем мире. Требования к такому компьютеру очень большие, так как точность измерений должна быть очень высокой и нужно свести к минимуму количество внешних воздействий, каждое из которых будет искажать работу квантовой системы.

Простые компьютеры, которые мы используем ежедневно, используют «биты» для хранения информации — 1 и 0 — и строки из этих нулей и единиц, представляющих определенную цифру или букву.

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

Таким образом, обыденный компьютер с двумя битами имеет возможность кодировать информацию лишь только в четырёх вероятных композициях: 00, 01,10,11. Квантовый компьютер имеет возможность брать на себя все эти четыре композиции в одно и тоже время. Это позволяет ему обрабатывать экспоненциально больше информации, чем могут простые компьютеры.

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

1)                 направление спинов частиц, составляющих основу атома;

2)                 наличие или отсутствие куперовской пары в установленном месте пространства;

3)                 в каком состоянии находится внешний электрон;

4)                 различные состояния фотона.

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

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

Материалы и методы

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

Обсуждение

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

Wi-fi, GPS, и все возможные виды компьютеров от дата-центров до ноутбуков, планшетов, смартфонов. И всё это нуждается в защите. Они все снабжены системой шифрования, защищающей информацию от чтения и изменения посторонними. Но всей защищенности могут положить конец квантовые компьютеры.

Возможно, квантовый компьютер мог бы быть у каждого заинтересованного хакера дома, но есть определенные проблемы при создании полноценного квантового компьютера. Ключевая проблема в том, чтобы поддержать кубиты в состоянии запутанности, потому что каждая квантовая система то и дело норовит упасть в традиционную, лишенную неопределенности. Здесь невозможно не упомянуть многострадального кота Шредингера, который не имеет возможности быть живым и мертвым одновременно, а в квантовом компьютере это поразительное состояние должно поддерживаться достаточное время для прогноза задачи и измерения результатов. Как правило речь идет о наносекундах, в наилучших системах — единицах секунд. Сложность задачи растёт с ростом числа кубитов. Для решения задач по взлому шифров необходим квантовый компьютер с 500–2000 кубитов, в то время как сейчас существующие системы оперируют с единицами кубитов (рекорд -14 кубитов). Таким образом, взлом вашего SSL-сертификата на квантовом компьютере сегодня еще невозможен, но, возможно, будет реален уже через пять лет.

На фоне вышеперечисленных сложностей, с которыми сталкиваются практически все разработчики, довольно вызывающе смотрятся физиков фирмы D — Wav, которая реализует квантовые компьютеры из 512 кубит. Почти все специалисты опровергают, собственно, что у D — Wave вышел настоящий квантовый компьютер, потому что он реализован на эффекте квантового отжига. Не смотря на всё компьютер D — Wave решает определенный класс задач оптимизации явно квантовыми методами, то есть честно выполняет свою работу. Он не приспособлен для решения многих других «квантовых» задач, что признают и создатели, но практическую пользу уже приносит. Google планирует решать на компьютере задачи машинного обучения, а Lockheed Martin на ряде экспериментов убедились, что компьютер способен находить ошибки в программном коде сложнейших приложений, управляющих истребителями F-35. Правда, компьютер D-Wave плохо приспособлен для вышеописанных задач по факторизации, поэтому не представляет особой угрозы для современных криптоалгоритмов. Угроза лежит в иной плоскости — работающий квантовый компьютер стимулирует большие компании и государства более активно вкладываться в разработки, ускоряя появление других видов квантовых компьютеров, которые способны подбирать криптоключи. [3]

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

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

В отличие от квантовых компьютеров, квантовые криптосистемы уже давно не являются лабораторной инновацией. Хотя первые научные работы на эту тему появились тоже на рубеже 70–80-х годов ХХ века, до практического воплощения дело дошло быстрее. Первые лабораторные тесты прошли в 1989 году, а уже в конце 90-х функционировали коммерческие системы квантовой передачи ключей на расстояние от 20 до 50 км. Такие организации, как id Quantique и MagiQ Technologies, продают готовые системы передачи криптоключей по обыкновенному оптоволоконному кабелю. Эти системы достаточно просты для установки обычным специалистом по прокладке компьютерных сетей. Соответственно, кроме различного рода военных и правительственных организаций их взяли на вооружение крупные коммерческие организации, банки и даже FIFA.

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

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

В-третьих, хакеры от науки обнаружили, что, «ослепляя» фотодетекторы мощным лазером, можно манипулировать их показаниями, что позволяет фальсифицировать данные в системах квантового распределения ключей. Правда, эти уязвимости относятся к недостаткам реализации, а не концепции, они вполне устранимы в будущем. Но уже произошедшие взломы лишь демонстрируют, что квантовые системы тоже не являются панацеей и защита передачи данных, если и перейдет из рук математиков в руки физиков, останется острой проблемой на многие годы вперед. Ну и наконец, маленькая, но серьезная проблема — в отличие от имеющихся технологий, квантовые системы еще долго останутся нишевыми и не будут десятками установлены в каждой квартире, как это сегодня обстоит с Wi-Fi, GSM и прочими. А значит, математиков рано списывать со счетов — классические криптосистемы, работающие с любым каналом связи, останутся востребованными еще многие десятилетия. Просто для них придется подобрать математические алгоритмы, непосильные квантовым компьютерам.

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

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

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

“Я искренне волновался, что мы не будем вовремя готовы в срок”, сказал Мишель Моска, соучредитель Института квантовых вычислений в Университете Ватерлоо в Канаде и главный исполнительный директор evolutionQ занимающийся кибербезопасностью.

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

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

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

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

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

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

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

PQCRYPTO, европейский консорциум квантовой криптографии исследователей в науке и промышленности, выпустила предварительный доклад, рекомендуя криптографические методы, которые устойчивы к квантовым компьютерам. Он выступает за систему Мак-Элиса, которая сопротивляется атакам с 1978 года, для криптографии с открытым ключом.

Криптографические методы

1) Симметричное шифрование

Симметричные системы, как правило, не влияют на алгоритм Шора, но они страдают от Алгоритма Гровера. Под ударом Гровера, лучшая защита ключевой длины n 2n/2

Так, AES 128 предлагает только 264 пост-квантовой безопасности. PQCRYPTO рекомендует тщательно проанализированы шифры с 256-битными ключами для достижения 2128 пост-квантовой безопасности:

                      AES- 256 [6].

                      Salsa20 [7] с 256-битным ключом.

2) Симметричной аутентификации

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

               GCM [8] используя 96-битный одноразовый номер и 128-битный аутентификатор.

               Poly1305 [9].

3) Шифрование с открытым ключом

Для шифрования с открытым ключом используемые в настоящее время алгоритмы, основанные на RSA и ECC легко нарушаются квантовыми компьютерами.

PQCRYPTO рекомендует следующие параметры, включенные в McBits [11] Для достижения 2128 пост-квантовой безопасности:

                      McEliece с бинарными Goppa используя коды длины N = 6960, размерность К = 5413 и добавление т = 119 ошибок.

4) С открытым ключом подписи

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

PQCRYPTO рекомендует следующие две системы на основе хэш- 2128 для достижения пост- квантовой безопасности:

          XMSS [12] с любым из параметров, указанных в XMSS требует поддержания государством.

          SPHINCS -256. [13] SPHINCS является лицом без гражданства.

Вывод

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

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

Квантовый скачок движется. И мы должны быть готовы.

 

Литература:

 

1.      Планк М.Единство физической картины мира. М., 1966.
2.      Эйнштейн А., Инфельд Л. Эволюцияфизики. — М.: Наука, 1965. — С. 241.
3.      Vance, Ashlee. «D-Wave qubits in the era of Quantum Computing». The Register, February 13, 2010.
4.      J. A. Jones, M. Mosca. Implementation of Quantum Algorithm on NMR Quantum Computer. J. Chem.Soc., 1998, v. 109, N5, pp.1648–1653.
5.      П. Шор. Полиномиальные по времени алгоритмы разложения числа на простые множители и нахождение дискретного алгоритма для квантового компью-тера. Сборник. «Квантовый компьютер и квантовые вычисления» вып.2 Ижевск,1999ю с 200–247.
6.      Joan Daemen and Vincent Rijmen. The Design of Rijndael: AES — The Advanced Encryption Standard. Information Security and Cryptography. Springer, 2002.
7.      Daniel J. Bernstein. The Salsa20 Family of Stream Ciphers. In Matthew J. B. Robshaw and Olivier Billet, editors, New Stream Cipher Designs — The eSTREAM Finalists,volume 4986 of Lecture Notes in Computer Science, pages 84{97. Springer, 2008.| Initial recommendations of long-term secure post-quantum systems
8.      David A. McGrew and John Viega. The Security and Performance of the Galois/Counter Mode of Operation (Full Version). Cryptology ePrint Archive, Report 2004/193, 2004.https://eprint.iacr.org/2004/193.9.
9.      Daniel J. Bernstein. The Poly1305-AES Message-Authentication Code. In Henri Gilbert and Helena Handschuh, editors, Fast Software Encryption: 12th International Workshop, FSE 2005, Paris, France, February 21–23, 2005, Revised Selected Papers, volume 3557 of Lecture Notes in Computer Science, pages 32{49. Springer, 2005.
10. Daniel J. Bernstein, Tung Chou, and Peter Schwabe. McBits: Fast Constant-Time CodeBased Cryptography. In Guido Bertoni and Jean-Sebastien Coron, editors, Cryptographic Hardware and Embedded Systems — CHES 2013–15th International Workshop, Santa Barbara, CA, USA, August 20–23, 2013. Proceedings, volume 8086 of Lecture Notes in Computer Science, pages 250{272. Springer, 2013.
11. Johannes A. Buchmann, Erik Dahmen, and Andreas Hulsing. XMSS — A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions. In BoYin Yang, editor, Post-Quantum Cryptography — 4th International Workshop, PQCrypto 2011, Taipei, Taiwan, November 29 — December 2, 2011. Proceedings, volume 7071 of Lecture Notes in Computer Science, pages 117{129. Springer, 2011.
12. Daniel J. Bernstein, Daira Hopwood, Andreas Hulsing, Tanja Lange, Ruben Niederhagen, Louiza Papachristodoulou, Michael Schneider, Peter Schwabe, and Zooko WilcoxO'Hearn. SPHINCS: Practical Stateless Hash-Based Signatures. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology — EUROCRYPT 2015–34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Soa, Bulgaria, April 26–30, 2015, Proceedings, Part I, volume 9056 of Lecture Notes in Computer Science, pages 368{397. Springer, 2015.