Постквантовая криптография ( PQC ), иногда называемая квантово-устойчивой , квантово-безопасной или квантово-устойчивой , представляет собой разработку криптографических алгоритмов (обычно алгоритмов с открытым ключом ), которые в настоящее время считаются защищенными от криптоаналитической атаки квантового компьютера . Наиболее широко используемые алгоритмы с открытым ключом полагаются на сложность одной из трех математических задач: задачи факторизации целых чисел , задачи дискретного логарифмирования или задачи дискретного логарифмирования эллиптической кривой . Все эти задачи можно было бы легко решить на достаточно мощном квантовом компьютере, работающем по алгоритму Шора [1] [2] или даже на более быстрых и менее требовательных (с точки зрения количества требуемых кубитов) альтернативах. [3]
В то время как по состоянию на 2023 год квантовым компьютерам не хватает вычислительной мощности для взлома широко используемых криптографических алгоритмов, [4] криптографы разрабатывают новые алгоритмы для подготовки к Y2Q или Q-Day , дню, когда текущие алгоритмы будут уязвимы для атак квантовых вычислений. Их работа привлекла внимание ученых и промышленности благодаря серии конференций PQCrypto , проводимых с 2006 года, нескольким семинарам по квантовой безопасной криптографии, проводимым Европейским институтом стандартов в области телекоммуникаций (ETSI), и Институтом квантовых вычислений . [5] [6] [7] Слухи о существовании широко распространенных программ «собирай сейчас, расшифруй позже» также рассматривались как мотивация для раннего внедрения постквантовых алгоритмов, поскольку данные, записанные сейчас, могут оставаться конфиденциальными в течение многих лет в будущем. [8] [9] [10]
В отличие от угрозы, которую квантовые вычисления представляют для современных алгоритмов с открытым ключом, большинство современных симметричных криптографических алгоритмов и хэш-функций считаются относительно защищенными от атак квантовых компьютеров. [2] [11] Хотя квантовый алгоритм Гровера действительно ускоряет атаки на симметричные шифры, удвоение размера ключа может эффективно блокировать эти атаки. [12] Таким образом, постквантовая симметричная криптография не должна существенно отличаться от современной симметричной криптографии.
13 августа 2024 года Национальный институт стандартов и технологий США (NIST) опубликовал окончательные версии своих первых трех постквантовых криптостандартов. [13]
Исследования постквантовой криптографии в основном сосредоточены на шести различных подходах: [2] [6]
Этот подход включает в себя криптографические системы, такие как обучение с ошибками , кольцевое обучение с ошибками ( ring-LWE ), [14] [15] [16] кольцевое обучение с ошибками обмена ключами и кольцевое обучение с ошибками подписи , старые схемы шифрования NTRU или GGH , а также новые подписи NTRU и подписи BLISS . [17] Некоторые из этих схем, такие как шифрование NTRU, изучались в течение многих лет, и никто не нашел осуществимой атаки. Другие, такие как алгоритмы ring-LWE, имеют доказательства того, что их безопасность сводится к проблеме наихудшего случая. [18] Исследовательская группа по постквантовой криптографии, спонсируемая Европейской комиссией, предложила изучить вариант NTRU Штеле-Штайнфельда для стандартизации, а не алгоритм NTRU. [19] [20] В то время NTRU все еще был запатентован. Исследования показали, что NTRU может иметь более безопасные свойства, чем другие алгоритмы на основе решеток. [21]
Это включает в себя криптографические системы, такие как схема Rainbow ( несбалансированное масло и уксус ), которая основана на трудности решения систем многомерных уравнений. Различные попытки построить безопасные схемы шифрования многомерных уравнений потерпели неудачу. Однако многомерные схемы подписи, такие как Rainbow, могут стать основой для квантовой безопасной цифровой подписи. [22] Схема подписи Rainbow запатентована.
Сюда входят криптографические системы, такие как подписи Лампорта , схема подписи Меркла , XMSS, [23] SPHINCS, [24] и схемы WOTS. Цифровые подписи на основе хеша были изобретены в конце 1970-х годов Ральфом Мерклем и с тех пор изучались как интересная альтернатива цифровым подписям на основе теории чисел, таким как RSA и DSA. Их основным недостатком является то, что для любого открытого ключа на основе хеша существует ограничение на количество подписей, которые могут быть подписаны с использованием соответствующего набора закрытых ключей. Этот факт снизил интерес к этим подписям, пока интерес не возродился из-за желания иметь криптографию, устойчивую к атакам квантовых компьютеров. Похоже, что на схему подписи Меркла нет патентов [ требуется ссылка ] , и существует множество незапатентованных хеш-функций, которые можно использовать с этими схемами. Схема подписи на основе хэш-функций с отслеживанием состояния XMSS, разработанная группой исследователей под руководством Йоханнеса Бухмана , описана в RFC 8391. [25]
Обратите внимание, что все вышеперечисленные схемы являются одноразовыми или ограниченными по времени подписями. Мони Наор и Моти Юнг изобрели хеширование UOWHF в 1989 году и разработали подпись на основе хеширования (схема Наора-Юнга) [26] , которая может использоваться неограниченное время (первая такая подпись, не требующая свойств лазейки).
Это включает в себя криптографические системы, которые полагаются на коды исправления ошибок , такие как алгоритмы шифрования McEliece и Niederreiter и связанная с ними схема подписи Courtois, Finiasz и Sendrier . Оригинальная подпись McEliece, использующая случайные коды Goppa , выдерживала проверку более 40 лет. Однако многие варианты схемы McEliece, которые стремятся ввести больше структуры в код, используемый для уменьшения размера ключей, оказались небезопасными. [27] Исследовательская группа Post Quantum Cryptography, спонсируемая Европейской комиссией, рекомендовала систему шифрования с открытым ключом McEliece в качестве кандидата на долгосрочную защиту от атак квантовых компьютеров. [19]
Эти криптографические системы полагаются на свойства графов изогений эллиптических кривых (и многомерных абелевых многообразий ) над конечными полями, в частности, суперсингулярных графов изогений , для создания криптографических систем. Среди наиболее известных представителей этой области — обмен ключами типа Диффи–Хеллмана CSIDH , который может служить простой квантово-устойчивой заменой методов обмена ключами Диффи–Хеллмана и эллиптической кривой Диффи–Хеллмана , которые широко используются сегодня, [28] и схема подписи SQISign , которая основана на категориальной эквивалентности между суперсингулярными эллиптическими кривыми и максимальными порядками в определенных типах кватернионных алгебр. [29] Другая широко известная конструкция, SIDH/SIKE , была эффектно взломана в 2022 году. [30] Однако атака специфична для семейства схем SIDH/SIKE и не распространяется на другие конструкции, основанные на изогении. [31]
При условии использования достаточно больших размеров ключей, симметричные криптографические системы с ключами, такие как AES и SNOW 3G, уже устойчивы к атакам квантового компьютера. [32] Кроме того, системы управления ключами и протоколы, использующие симметричную криптографию вместо криптографии с открытым ключом, такие как Kerberos и структура аутентификации мобильной сети 3GPP, также изначально защищены от атак квантового компьютера. Учитывая его широкое распространение в мире, некоторые исследователи рекомендуют расширенное использование симметричного управления ключами, подобного Kerberos, как эффективного способа получить постквантовую криптографию сегодня. [33]
В криптографических исследованиях желательно доказать эквивалентность криптографического алгоритма и известной сложной математической проблемы. Эти доказательства часто называют «снижениями безопасности» и используют для демонстрации сложности взлома алгоритма шифрования. Другими словами, безопасность данного криптографического алгоритма сводится к безопасности известной сложной проблемы. Исследователи активно ищут снижения безопасности в перспективах постквантовой криптографии. Текущие результаты приведены здесь:
В некоторых версиях Ring-LWE есть сокращение безопасности до задачи поиска кратчайшего вектора (SVP) в решетке в качестве нижней границы безопасности. Известно, что SVP является NP-трудной . [34] Конкретные системы Ring-LWE, которые имеют доказуемые сокращения безопасности, включают вариант подписей Ring-LWE Любашевского, определенных в статье Гюнейсу, Любашевского и Пёппельмана. [15] Схема подписи GLYPH является вариантом подписи Гюнейсу, Любашевского и Пёппельмана (GLP) , которая учитывает результаты исследований, появившихся после публикации подписи GLP в 2012 году. Другая подпись Ring-LWE — это Ring-TESLA. [35] Существует также «дерандомизированный вариант» LWE, называемый обучением с округлением (LWR), который обеспечивает «улучшенное ускорение (за счет исключения выборки небольших ошибок из гауссовоподобного распределения с детерминированными ошибками) и пропускную способность». [36] В то время как LWE использует добавление небольшой ошибки для сокрытия младших битов, LWR использует округление для той же цели.
Безопасность схемы шифрования NTRU и подписи BLISS [17] считается связанной с, но не доказуемо сводимой к, ближайшей векторной задаче (CVP) в решетке. Известно, что CVP является NP-трудной . Исследовательская группа по постквантовой криптографии, спонсируемая Европейской комиссией, предложила, чтобы вариант NTRU Штеле-Штайнфельда, который имеет снижение безопасности, был изучен для долгосрочного использования вместо исходного алгоритма NTRU. [19]
Схемы подписи Unbalanced Oil and Vinegar являются асимметричными криптографическими примитивами, основанными на многомерных полиномах над конечным полем . Булыгин, Петцольдт и Бухманн показали сведение общих многомерных квадратичных систем UOV к NP-Hard многомерной квадратичной задаче решения уравнения. [37]
В 2005 году Луис Гарсия доказал, что существует снижение безопасности подписей Merkle Hash Tree до безопасности базовой хэш-функции. Гарсия показал в своей статье, что если вычислительно односторонние хэш-функции существуют, то подпись Merkle Hash Tree является доказуемо безопасной. [38]
Следовательно, если бы кто-то использовал хэш-функцию с доказуемым снижением безопасности до известной сложной проблемы, то он получил бы доказуемое снижение безопасности сигнатуры дерева Меркла до этой известной сложной проблемы. [39]
Исследовательская группа по постквантовой криптографии, спонсируемая Европейской комиссией, рекомендовала использовать схему подписи Меркла для долгосрочной защиты от квантовых компьютеров. [19]
Система шифрования McEliece имеет снижение безопасности до проблемы декодирования синдрома (SDP). Известно, что SDP является NP-трудной . [40] Исследовательская группа по постквантовой криптографии, спонсируемая Европейской комиссией, рекомендовала использовать эту криптографию для долгосрочной защиты от атак квантового компьютера. [19]
В 2016 году Ван предложил схему шифрования случайного линейного кода RLCE [41] , которая основана на схемах Мак-Элиса. Схема RLCE может быть построена с использованием любого линейного кода, такого как код Рида-Соломона, путем вставки случайных столбцов в базовую матрицу генератора линейного кода.
Безопасность связана с проблемой построения изогении между двумя суперсингулярными кривыми с одинаковым числом точек. Последнее исследование сложности этой проблемы, проведенное Делфсом и Гэлбрейтом, показывает, что эта проблема настолько сложна, насколько предполагают изобретатели обмена ключами. [42] Не существует снижения безопасности до известной NP-сложной проблемы.
Одной из общих характеристик многих алгоритмов постквантовой криптографии является то, что они требуют больших размеров ключей, чем обычно используемые "доквантовые" алгоритмы открытого ключа. Часто приходится идти на компромиссы между размером ключа, вычислительной эффективностью и размером шифротекста или подписи. В таблице перечислены некоторые значения для различных схем на 128-битном уровне постквантовой безопасности.
Практическим соображением при выборе между постквантовыми криптографическими алгоритмами является усилие, необходимое для отправки открытых ключей через Интернет. С этой точки зрения алгоритмы Ring-LWE, NTRU и SIDH предоставляют удобные размеры ключей менее 1 кБ, открытые ключи хэш-подписи занимают менее 5 кБ, а McEliece на основе MDPC занимает около 1 кБ. С другой стороны, схемы Rainbow требуют около 125 кБ, а McEliece на основе Goppa требует ключ размером почти 1 МБ.
Основная идея использования LWE и Ring LWE для обмена ключами была предложена и подана в Университете Цинциннати в 2011 году Цзиньтаем Дином. Основная идея исходит из ассоциативности умножения матриц, а ошибки используются для обеспечения безопасности. Статья [52] появилась в 2012 году после подачи предварительной патентной заявки в 2012 году.
В 2014 году Пейкерт [53] представил схему транспортировки ключей, основанную на той же базовой идее Динга, где также используется новая идея отправки дополнительного 1-битного сигнала для округления в конструкции Динга. Для немного большей, чем 128 бит безопасности , Сингх представляет набор параметров, которые имеют 6956-битные открытые ключи для схемы Пейкерта. [54] Соответствующий закрытый ключ будет примерно 14 000 бит.
В 2015 году на Eurocrypt 2015 был представлен аутентифицированный обмен ключами с доказуемой прямой безопасностью, следующий той же базовой идее Дина, [55] , который является расширением конструкции HMQV [56] в Crypto2005. Параметры для различных уровней безопасности от 80 бит до 350 бит, а также соответствующие размеры ключей приведены в статье. [55]
Для 128 бит безопасности в NTRU Хиршхорн, Хоффштейн, Хаугрейв-Грэхем и Уайт рекомендуют использовать открытый ключ, представленный в виде полинома степени 613 с коэффициентами Это приводит к открытому ключу длиной 6130 бит. Соответствующий закрытый ключ будет иметь длину 6743 бит. [43]
Для 128-битной безопасности и наименьшего размера подписи в схеме подписи многомерного квадратного уравнения Rainbow Петцольдт, Булыгин и Бухманн рекомендуют использовать уравнения с размером открытого ключа чуть более 991 000 бит, закрытым ключом чуть более 740 000 бит и цифровыми подписями длиной 424 бита. [44]
Чтобы получить 128 бит безопасности для подписей на основе хэша для подписания 1 миллиона сообщений с использованием метода фрактального дерева Меркла Наора Шенхава и Вула, размеры открытого и закрытого ключей составляют примерно 36 000 бит в длину. [57]
Для 128 бит безопасности в схеме Мак-Элиса группа по исследованию постквантовой криптографии Европейской комиссии рекомендует использовать двоичный код Гоппы длиной не менее и размерностью не менее , способный исправлять ошибки. С этими параметрами открытый ключ для системы Мак-Элиса будет систематической генераторной матрицей, неидентичная часть которой занимает биты. Соответствующий закрытый ключ, который состоит из поддержки кода с элементами из и генераторного полинома с коэффициентами из , будет иметь длину 92 027 бит [19]
Группа также исследует использование квазициклических кодов MDPC длиной не менее и размерностью не менее , способных исправлять ошибки. С этими параметрами открытый ключ для системы Мак-Элиса будет первой строкой матрицы систематического генератора, неидентичная часть которой занимает биты. Закрытый ключ, квазициклическая матрица проверки четности с ненулевыми записями в столбце (или вдвое больше в строке), занимает не более бит, когда представлен как координаты ненулевых записей в первой строке.
Баррето и др. рекомендуют использовать двоичный код Гоппы длиной не менее и размерностью не менее , способный исправлять ошибки. С этими параметрами открытый ключ для системы Мак-Элиса будет систематической генераторной матрицей, нетождественная часть которой занимает биты. [58] Соответствующий закрытый ключ, который состоит из поддержки кода с элементами из и генераторного полинома с коэффициентами из , будет иметь длину 40 476 бит.
Для 128 бит безопасности в методе суперсингулярной изогении Диффи-Хеллмана (SIDH) Де Фео, Джао и Плут рекомендуют использовать суперсингулярную кривую по модулю 768-битного простого числа. Если использовать сжатие точек эллиптической кривой, открытый ключ должен быть не более 8x768 или 6144 бит в длину. [59] В статье от марта 2016 года авторов Азардерахша, Джао, Калаха, Козиэля и Леонарди было показано, как сократить количество передаваемых битов вдвое, что было дополнительно улучшено авторами Костелло, Джао, Лонгой, Наеригом, Ренесом и Урбаником, что привело к версии протокола SIDH со сжатым ключом с открытыми ключами размером всего 2640 бит. [51] Это делает количество передаваемых битов примерно эквивалентным неквантовому безопасному RSA и Диффи-Хеллмана на том же классическом уровне безопасности. [60]
Как правило, для 128 бит безопасности в системе на основе симметричного ключа можно безопасно использовать ключи размером 256 бит. Лучшая квантовая атака против произвольных систем с симметричным ключом — это применение алгоритма Гровера , который требует работы, пропорциональной квадратному корню размера ключевого пространства. Для передачи зашифрованного ключа устройству, обладающему симметричным ключом, необходимым для расшифровки этого ключа, также требуется примерно 256 бит. Очевидно, что системы с симметричным ключом предлагают наименьшие размеры ключей для постквантовой криптографии. [ необходима цитата ]
Система с открытым ключом демонстрирует свойство, называемое совершенной прямой секретностью , когда она генерирует случайные открытые ключи за сеанс для целей согласования ключей. Это означает, что компрометация одного сообщения не может привести к компрометации других, а также что нет ни одного секретного значения, которое может привести к компрометации нескольких сообщений. Эксперты по безопасности рекомендуют использовать криптографические алгоритмы, которые поддерживают прямую секретность, а не те, которые ее не поддерживают. [61] Причина этого в том, что прямая секретность может защитить от компрометации долгосрочных закрытых ключей, связанных с парами открытого/закрытого ключей. Это рассматривается как средство предотвращения массового наблюдения со стороны разведывательных служб.
Оба обмена ключами Ring-LWE и суперсингулярный изогенный обмен ключами Диффи-Хеллмана (SIDH) могут поддерживать прямую секретность в одном обмене с другой стороной. Оба, Ring-LWE и SIDH, могут также использоваться без прямой секретности, создавая вариант классического варианта шифрования ElGamal Диффи-Хеллмана.
Другие алгоритмы в этой статье, такие как NTRU, не поддерживают прямую секретность как таковую.
Любая аутентифицированная система шифрования с открытым ключом может быть использована для создания обмена ключами с прямой секретностью. [62]
Проект Open Quantum Safe ( OQS ) был запущен в конце 2016 года и имеет целью разработку и прототипирование квантово-устойчивой криптографии. [63] [64] Он направлен на интеграцию текущих постквантовых схем в одну библиотеку: liboqs . [65] liboqs — это библиотека C с открытым исходным кодом для квантово-устойчивых криптографических алгоритмов. Изначально она фокусировалась на алгоритмах обмена ключами, но к настоящему времени включает в себя несколько схем подписи. Она предоставляет общий API, подходящий для постквантовых алгоритмов обмена ключами, и будет собирать вместе различные реализации. liboqs также будет включать в себя тестовую обвязку и процедуры бенчмаркинга для сравнения производительности постквантовых реализаций. Кроме того, OQS также обеспечивает интеграцию liboqs в OpenSSL . [66]
По состоянию на март 2023 года поддерживаются следующие алгоритмы обмена ключами: [63]
По состоянию на август 2024 года NIST опубликовал 3 алгоритма, перечисленных ниже, в качестве стандартов FIPS, а 4-й ожидается ближе к концу года: [67]
Старые поддерживаемые версии, которые были удалены в связи с развитием проекта NIST по стандартизации постквантовой криптографии:
Одной из главных проблем в постквантовой криптографии считается внедрение потенциально квантово-безопасных алгоритмов в существующие системы. Существуют тесты, например, Microsoft Research, реализующие PICNIC в PKI с использованием аппаратных модулей безопасности . [85] Тестовые реализации для алгоритма NewHope от Google также были выполнены поставщиками HSM . В августе 2023 года Google выпустила реализацию ключа безопасности FIDO2 гибридной схемы подписи ECC /Dilithium, которая была сделана в партнерстве с ETH Zürich . [86]
Протокол сигнала использует постквантовый расширенный алгоритм Диффи–Хеллмана (PQXDH). [87]
21 февраля 2024 года Apple объявила, что собирается обновить свой протокол iMessage новым протоколом PQC под названием «PQ3», который будет использовать постоянное ключирование. [87] [88] [89] Apple заявила, что, хотя квантовые компьютеры пока не существуют, они хотели бы снизить риски от будущих квантовых компьютеров, а также от так называемых сценариев атак « собрать сейчас, расшифровать позже ». Apple заявила, что, по их мнению, их реализация PQ3 обеспечивает защиту, которая «превосходит защиту во всех других широко распространенных приложениях для обмена сообщениями», поскольку она использует постоянное ключирование. Apple намерена полностью заменить существующий протокол iMessage во всех поддерживаемых разговорах на PQ3 к концу 2024 года. Apple также определила шкалу, чтобы упростить сравнение свойств безопасности приложений для обмена сообщениями, со шкалой, представленной уровнями от 0 до 3: 0 для отсутствия сквозного протокола по умолчанию, 1 для сквозного протокола до квантового уровня по умолчанию, 2 для установления только ключа PQC (например, PQXDH) и 3 для установления ключа PQC и постоянной смены ключа (PQ3). [87]
Другие примечательные реализации включают в себя:
Google сохранил использование «гибридного шифрования» в своем использовании постквантовой криптографии: всякий раз, когда используется относительно новая постквантовая схема, она объединяется с более проверенной, не-PQ схемой. Это необходимо для того, чтобы гарантировать, что данные не будут скомпрометированы, даже если относительно новый алгоритм PQ окажется уязвимым для неквантовых атак до Y2Q. Этот тип схемы используется в его тестах 2016 и 2019 годов для постквантового TLS, [92] и в его ключе FIDO2 2023 года. [86] Действительно, один из алгоритмов, использованных в тесте 2019 года, SIKE, был взломан в 2022 году, но не-PQ слой X25519 (уже широко используемый в TLS) по-прежнему защищал данные. [92] PQ3 от Apple и PQXDH от Signal также являются гибридными. [87]
АНБ и GCHQ выступают против гибридного шифрования, утверждая, что оно усложняет реализацию и переход. Дэниел Дж. Бернстайн , поддерживающий гибридное шифрование, утверждает, что эти заявления являются фальшивыми. [92]
{{cite web}}
: CS1 maint: бот: исходный статус URL неизвестен ( ссылка ){{cite web}}
: CS1 maint: бот: исходный статус URL неизвестен ( ссылка ){{cite web}}
: CS1 maint: бот: исходный статус URL неизвестен ( ссылка ){{cite web}}
: CS1 maint: бот: исходный статус URL неизвестен ( ссылка ){{cite web}}
: CS1 maint: бот: исходный статус URL неизвестен ( ссылка )Благодаря устойчивому к взлому шифрованию и обширной защите даже от самых сложных квантовых атак PQ3 является первым протоколом обмена сообщениями, достигшим того, что мы называем безопасностью уровня 3 — обеспечивая защиту протокола, превосходящую защиту всех других широко распространенных приложений обмена сообщениями.