Даже в 2016 году статьи о квантовых компьютерах создавали неопределенность в отношении безопасности данных в случае, если можно будет построить достаточно мощные квантовые компьютеры. Эта статья попытается пролить свет на ситуацию.
Что такое квантовые вычисления?
Квантовые вычисления — это применение принципов квантовой механики для выполнения вычислений. В частности, квантовые вычисления используют квантовые состояния субатомных частиц, такие как суперпозиция и запутанность, для создания квантовых компьютеров. Применительно к квантовым компьютерам достаточной мощности определенные алгоритмы могут выполнять вычисления намного быстрее, чем классические компьютеры, и даже решать проблемы, недоступные нынешним вычислительным технологиям. В результате наблюдается повышенный интерес со стороны правительств и промышленности по всему миру к разработке квантовых компьютеров. Недавние достижения в области квантовых вычислений, такие как процессор IBM Quantum Heron, значительно улучшили снижение ошибок, демонстрируя быстрый прогресс в этой области. Появление IBM Quantum System Two, оснащенной этими передовыми процессорами, знаменует собой скачок к практическим квантово-ориентированным суперкомпьютерам.
Классические и квантовые вычисления
Классические вычисления полагаются на биты, представляющие единицы и нули через электрические токи в цепях, для решения сложных задач. Квантовые вычисления, использующие кубиты, подобные тем, что используются в IBM Quantum Heron, превосходят классические вычисления по вычислительной мощности за счет улучшенного исправления ошибок и стабильности кубитов. Кубиты, в отличие от битов, могут существовать в суперпозиции, воплощая одновременно и единицу, и ноль. Эта возможность позволяет одному кубиту представлять два состояния одновременно, и с каждым дополнительным кубитом представимые состояния удваиваются экспоненциально («2^n» для n кубитов). Например, квантовый компьютер с десятью кубитами может представлять 1024 состояния, в отличие от 10 бит в классических вычислениях. Квантовая запутанность — сложное и до конца не изученное явление — позволяет кубитам соединяться между собой, повышая эффективность вычислений. Используя как суперпозицию, так и запутанность, квантовые компьютеры работают в многомерных пространствах, выполняя параллельные вычисления, в отличие от последовательного подхода в классических вычислениях. Эти расширенные вычислительные возможности позволяют квантовым компьютерам решать проблемы, выходящие за рамки классических компьютеров, например, точное моделирование молекулярных взаимодействий в химических реакциях. Это имеет далеко идущие последствия для науки и техники, включая возможность решать проблемы гораздо быстрее, чем классические компьютеры, что влияет на такие области, как криптография.Как квантовые вычисления могут влиять на криптографию?
Как обсуждалось выше, криптография основана на существовании трудноразрешимых математических проблем, что не означает, что они неразрешимы, но что время и ресурсы, необходимые для их обращения, делают их практически безопасными.
Квантовые вычисления изменяют эту экосистему, сводя к минимуму время, необходимое для решения таких проблем, за счет применения определенных алгоритмов.
Например, алгоритм, открытый , наряду с применением алгоритмов, подобных алгоритму Шора, в контексте передовых квантовых процессоров, таких как Quantum Heron от IBM, подчеркивают насущную потребность в квантовоустойчивых криптографических системах.
«В 1994 году Питер Шор из Bell Laboratories показал, что квантовые компьютеры, новая технология, использующая физические свойства материи и энергии для выполнения вычислений, могут эффективно решить каждую из этих проблем, тем самым делая бессильными все криптосистемы с открытым ключом, основанные на таких предположениях. Таким образом, достаточно мощный квантовый компьютер поставит под угрозу многие формы современной коммуникации — от обмена ключами до шифрования и цифровой аутентификации».
Короче говоря, квантовый компьютер достаточной мощности может полностью вывести из строя инфраструктуру открытых ключей, что приведет к необходимости реорганизации всей экосистемы кибербезопасности.
Недавние применения постквантовой криптографии наблюдаются в потребительских сферах, например, поддержка Chrome алгоритма PQC, что указывает на практическое влияние квантовых вычислений на современные криптографические системы.
Но это еще не все. Другой алгоритм, на этот раз может представлять угрозу для симметричной криптографии, хотя и не такую серьезную, как у Шора. Применительно к достаточно мощному квантовому компьютеру алгоритм Гровера позволяет взламывать симметричные ключи с четырехкратной скоростью по сравнению с классическими вычислениями. Значительное улучшение, которому можно противостоять, используя ключи большего размера и поддерживая текущий уровень безопасности.
Скоро ли появятся квантовые вычисления?
Физика доказала, что квантовые вычисления возможны. Теперь это инженерная проблема, хотя и очень сложная. При создании квантовых компьютеров используются самые современные технологии, такие как, среди прочего, сверхтекучие жидкости и сверхпроводники. Задача создания стабильной и масштабируемой квантово-механической системы огромна, и она заставляет команды по всему миру идти разными путями. Существует несколько типов квантовых компьютеров, включая модель квантовой схемы, квантовую машину Тьюринга, адиабатический квантовый компьютер, односторонний квантовый компьютер и различные квантовые клеточные автоматы. Наиболее широко используется квантовая схема.
Существенная проблема любой модели квантовых компьютеров заключается в том, что по своей природе кубиты теряют статус суперпозиции после измерения и, следовательно, очень чувствительны к внешнему вмешательству. Следовательно, кубитам сложно поддерживать свое квантовое состояние. Некоторые решения включают использование ионных ловушек, но полное устранение внешних помех, вероятно, недостижимо. В результате одной из наиболее важных проблем при создании квантовых компьютеров является надежный механизм исправления ошибок.
Благодаря недавним прорывам, таким как достижения IBM в области квантовых вычислений, эта область вышла за рамки теоретических моделей и перешла к более практичным и мощным квантовым системам, приближая квантовую эру, чем предполагалось ранее.
В целом картина такова, что прорыв может произойти прямо сейчас, или может потребоваться несколько лет, прежде чем будет создан рабочий прототип с достаточной вычислительной мощностью. Уже существует несколько прототипов, наиболее известным из которых является IBM Q System One, но их вычислительная мощность все еще слишком мала, чтобы быть проблемой для криптографических систем. Ни в коем случае, конечно, сообществу кибербезопасности нельзя расслабляться. Даже если бы у нас была эффективная схема постквантовой безопасности, миграция всей экосистемы на этот новый стандарт - огромная задача. Следовательно, предпринимаются некоторые попытки подготовиться к постквантовой эре.
Перспективные технологии постквантовой эры
По мере того, как мы приближаемся к широкому применению квантовых технологий, о чем свидетельствуют такие достижения, как Quantum System Two от IBM, возникает необходимость в квантовоустойчивом PKI становится все более актуальной по мере распространения технологии квантовых вычислений. Ниже мы попытаемся обобщить наиболее перспективные технологии и дать краткий обзор текущих коллективных проектов по созданию постквантовой криптографии, а также проблем, которые предстоит решить.
Семейства постквантовых алгоритмов
Исследования последних 15-20 лет доказали существование алгоритмов, устойчивых к квантовым атакам. Ниже мы даем краткое описание наиболее многообещающих семейств алгоритмов, которые могут обеспечить решение для обеспечения безопасности в постквантовом мире.
Криптография на основе кода
Последние разработки в этой области криптографии на основе кодов используют коды, исправляющие ошибки, для построения криптографии с открытым ключом. Впервые он был предложен Робертом МакЭлисом в 1978 году и является одним из старейших и наиболее исследованных алгоритмов асимметричного шифрования. Схема подписи может быть построена на основе схемы Нидеррайтера, двойственного варианта схемы МакЭлиса. Криптосистема МакЭлиса до сих пор сопротивлялась криптоанализу. Основная проблема исходной системы — большой размер закрытого и открытого ключей.
Криптография на основе хеша
С ростом внедрения в практические приложения криптография на основе хэша представляет собой многообещающий подход постквантовой криптографии к цифровым подписям. Хэш-функции — это функции, которые сопоставляют строки произвольной длины со строками фиксированной длины. Это одна из старейших схем шифрования с открытым ключом, и их оценки безопасности против классических и квантовых атак хорошо известны. Хэш-функции уже являются одним из наиболее широко используемых криптографических инструментов. Было известно, что их можно было использовать в качестве единственного инструмента для построения криптографии с открытым ключом в течение длительного времени. Кроме того, криптография на основе хэша является гибкой и может соответствовать различным ожиданиям по производительности. С другой стороны, схемы подписи на основе хэша в основном сохраняют состояние, а это означает, что закрытый ключ необходимо обновлять после каждого использования; в противном случае безопасность не гарантируется. Существуют схемы на основе хэша, которые не сохраняют состояние, но они реализуются за счет более длинных подписей, более значительного времени обработки и необходимости подписавшего отслеживать некоторую информацию, например, сколько раз ключ был использован для создания подписи.
Латексная криптография
В настоящее время рассматривается возможность более совершенных криптографических решений. Криптография на основе решетки представляет собой частный случай криптографии, основанной на задаче суммы подмножества, и была впервые представлена в 1996 году Айтаем. Это общий термин для криптографических примитивов, построенных с использованием решеток. Некоторые из этих конструкций кажутся устойчивыми как к квантовым, так и к классическим компьютерным атакам. Кроме того, у них есть и другие привлекательные особенности, такие как сложность наихудшего случая. Они также отличаются простотой и параллелизмом и достаточно универсальны для создания надежных криптографических схем. Наконец, это единственное семейство алгоритмов, содержащее все три вида примитивов, необходимых для построения постквантовой инфраструктуры открытых ключей: шифрование с открытым ключом, обмен ключами и цифровая подпись.
Многовариантная криптография
Многомерная криптография относится к криптографии с открытым ключом, открытые ключи которой представляют собой многомерную и нелинейную (обычно квадратичную) полиномиальную карту. Доказано, что решение этих систем является NP-полным, что делает это семейство алгоритмов хорошими кандидатами для постквантовой криптографии. В настоящее время многовариантные схемы шифрования оказались менее эффективными, чем другие схемы, поскольку они требуют значительных открытых ключей и длительного времени дешифрования. С другой стороны, они оказались более подходящими для построения схем подписи, поскольку они обеспечивают самые короткие размеры подписи среди постквантовых алгоритмов, хотя и требуют довольно больших открытых ключей.
Криптография на основе изогении
Криптография на основе изогении использует карты между эллиптическими кривыми для построения криптографии с открытым ключом. Алгоритм, который является кандидатом для постквантовой криптографии, - это суперсингулярная изогения обмена ключами Диффи-Хеллмана (SIDH), представленная в 2011 году, что делает эту схему самой последней среди кандидатов. SIDH требует одного из самых маленьких ключей среди предлагаемых схем обмена ключами и поддерживает идеальную прямую секретность. Однако его относительно молодой возраст означает, что существует не так много схем, основанных на этой концепции, и не так много возможностей для проверки их возможных уязвимостей.
Проекты постквантовой криптографии
Существуют различные рабочие группы по схемам постквантовой криптографии, такие как проект Open Quantum Safe (OQS) и ENISA. Тем не менее, наиболее последовательной инициативой является проект NIST по стандартизации постквантовой криптографии, который добился значительного прогресса с 2021 года, а новые алгоритмы стали лидерами отраслевой стандартизации в постквантовую эпоху. Процесс начался с 69 алгоритмов-кандидатов, 26 из которых прошли второй этап оценки. В июле 2020 года были объявлены кандидаты третьего тура, как показано в таблице ниже. Всего есть семь финалистов и восемь альтернативных кандидатов. В таблице указано, рассматриваются ли они для схем шифрования или подписи, семейство алгоритмов и сложная проблема, на которой они основаны.
| Схема | Enc / SIg | Семейные | Сложная проблема |
|---|---|---|---|
| Классический МакЭлис | ООО | На основе кода | Расшифровка случайных двоичных кодов Гоппа |
| Кристаллы-Кибер | ООО | На основе решетки | Циклотомический модуль-LWE |
| НТРУ | ООО | На основе решетки | Циклотомическая проблема NTRU |
| Знать | ООО | На основе решетки | Циклотомический модуль-LWR |
| Кристаллы-Дилитий | Sig | На основе решетки | Циклотомический модуль-LWE и модуль-SIS |
| Cокол | Sig | На основе решетки | Циклотомическое кольцо-SIS |
| радуга | Sig | Многомерный | Люк для масла и уксуса |
Альтернативные кандидаты 3-го раунда
| Схема | Enc/подпись | Семейные |
|---|---|---|
| ВЕЛОСИПЕД | ООО | На основе кода |
| Высший квалификационная комиссия | ООО | На основе кода |
| Фродо-КЭМ | ООО | На основе решетки |
| НТРУ-Прайм | ООО | На основе решетки |
| САЙК | ООО | На основе изогении |
| ГеМСС | Sig | Многомерный |
| Пикник | Sig | Симметричная криптография |
| SPHINCS + | Sig | На основе хеша |
Оценка алгоритма была основана на трех критериях, показанных ниже.
-
Безопасность: Это самый важный критерий. NIST установил несколько факторов, которые следует учитывать при оценке безопасности, обеспечиваемой каждым алгоритмом-кандидатом. Помимо квантовой устойчивости алгоритмов, NIST также определил дополнительные параметры безопасности, которые не являются частью текущей экосистемы кибербезопасности. Это идеальная прямая секретность,
-
Стоимость и производительность: Алгоритмы оцениваются на основе их показателей производительности, таких как размеры ключей, вычислительная эффективность операций и генерации открытых и закрытых ключей, а также ошибки расшифровки.
-
Алгоритм и характеристики реализации: Предполагая, что алгоритмы обеспечивают хорошую общую безопасность и производительность, они оцениваются на основе их гибкости, простоты и легкости внедрения (например, наличия или отсутствия интеллектуальной собственности, охватывающей алгоритм).
Криптографическая гибкость
Важной парадигмой при разработке протоколов информационной безопасности является гибкость шифрования. Он требует, чтобы протоколы поддерживали несколько криптографических примитивов, позволяя системам, реализующим определенный стандарт, выбирать, какие комбинации примитивов подходят. Основная цель криптографической гибкости — обеспечить быструю адаптацию уязвимых криптографических примитивов и алгоритмов к надежным без внесения разрушительных изменений в инфраструктуру системы. Эта парадигма имеет решающее значение в разработке постквантовой криптографии и требует, по крайней мере, частичной автоматизации. Например, среднее предприятие владеет сотнями тысяч сертификатов и ключей, и это число продолжает расти. Имея такое большое количество сертификатов, организациям приходится развертывать автоматизированные методы для быстрой замены этих сертификатов, если криптография, на которую они полагаются, становится небезопасной.
Отличная первая мера для организаций - начать внедрение гибридной криптографии, в которой квантово-безопасные алгоритмы с открытым ключом используются наряду с традиционными алгоритмами с открытым ключом (такими как RSA или эллиптические кривые), чтобы решение было по крайней мере не менее безопасным, чем существующие традиционные криптография.
Взгляд в будущее
Квантовые вычисления переходят от теоретической возможности к практической реальности, примером чему служат недавние разработки в области квантовых процессоров и систем. Следовательно, сфере кибербезопасности необходимо будет быстро адаптироваться к этим изменениям.
