Постквантовая криптография - Post-quantum cryptography

В криптографии , после квантовой криптографии (иногда называют квантовое доказательством , квантовым безопасным или квантово-резистентный ) относится к криптографическим алгоритмам ( как правило , с открытым ключом алгоритмов), которые считаются в безопасности против криптоаналитической атаки с помощью квантового компьютера . По состоянию на 2021 год это не относится к наиболее популярным алгоритмам с открытым ключом, которые могут быть эффективно взломаны достаточно мощным квантовым компьютером. Проблема в настоящее время популярных алгоритмов является то , что их безопасность зависит от одной из трех жестких математических задач: задачи целочисленной факторизации , в задачах дискретного логарифмирования или эллиптических кривых задачах дискретного логарифмирования . Все эти проблемы легко решаются на достаточно мощном квантовом компьютере с алгоритмом Шора . Несмотря на то, что текущим, широко известным экспериментальным квантовым компьютерам не хватает вычислительной мощности для взлома любого реального криптографического алгоритма, многие криптографы разрабатывают новые алгоритмы, чтобы подготовиться к тому времени, когда квантовые вычисления станут угрозой. Эта работа привлекла повышенное внимание ученых и промышленности благодаря серии конференций PQCrypto с 2006 года, а в последнее время - нескольким семинарам по квантовой безопасной криптографии, организованным Европейским институтом стандартов электросвязи (ETSI) и Институтом квантовых вычислений .

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

Алгоритмы

В настоящее время исследования постквантовой криптографии в основном сосредоточены на шести различных подходах:

Криптография на основе решеток

Этот подход включает в себя криптографические системы, такие как обучение с ошибками , кольцевое обучение с ошибками ( кольцо-LWE ), кольцевое обучение с ошибками, обмен ключами и кольцевое обучение с сигнатурой ошибок , более старые схемы шифрования NTRU или GGH , а также более новую подпись NTRU и Подписи BLISS . Некоторые из этих схем, такие как шифрование NTRU, изучались в течение многих лет, и никто не нашел подходящей атаки. Другие, такие как алгоритмы кольцевого LWE, имеют доказательства того, что их безопасность сводится к проблеме наихудшего случая. Исследовательская группа постквантовой криптографии, спонсируемая Европейской комиссией, предложила изучить вариант NTRU Стеле – Штейнфельда для стандартизации, а не алгоритм NTRU. На тот момент НТРУ еще был запатентован. Исследования показали, что NTRU может иметь более безопасные свойства, чем другие алгоритмы на основе решеток.

Многовариантная криптография

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

Криптография на основе хеша

Сюда входят криптографические системы, такие как подписи Лампорта и схема подписи Меркла, а также новые схемы XMSS и SPHINCS. Цифровые подписи на основе хеша были изобретены в конце 1970-х годов Ральфом Мерклом и с тех пор изучаются как интересная альтернатива теоретико-числовым цифровым подписям, таким как RSA и DSA. Их основной недостаток заключается в том, что для любого открытого ключа на основе хэша существует ограничение на количество подписей, которые могут быть подписаны с использованием соответствующего набора закрытых ключей. Этот факт снизил интерес к этим сигнатурам, пока интерес не возродился из-за стремления к криптографии, устойчивой к атакам квантовых компьютеров. Похоже, что на схему подписи Меркла нет патентов, и существует множество незапатентованных хэш-функций, которые можно было бы использовать с этими схемами. Схема подписи на основе хэша с отслеживанием состояния XMSS, разработанная группой исследователей под руководством Йоханнеса Бухманна , описана в RFC 8391. Обратите внимание, что все вышеупомянутые схемы являются одноразовыми или ограниченными по времени подписями, Мони Наор и Моти Юнг изобрели хеширование UOWHF. в 1989 году и разработал сигнатуру, основанную на хешировании (схема Наор-Юнга), которая может использоваться неограниченное время (первая такая сигнатура, не требующая свойств лазейки).

Криптография на основе кода

Это включает в себя криптографические системы, которые полагаются на коды с исправлением ошибок , такие как алгоритмы шифрования Мак- Элиса и Нидеррайтера и связанную с ними схему подписи Куртуа, Финиаса и Сендриера . Оригинальная подпись Мак- Элиса с использованием случайных кодов Гоппа выдерживала тщательную проверку более 30 лет. Однако многие варианты схемы Мак-Элиса, которые стремятся внести больше структуры в код, используемый для уменьшения размера ключей, оказались небезопасными. Исследовательская группа постквантовой криптографии, спонсируемая Европейской комиссией, рекомендовала систему шифрования с открытым ключом Мак-Элиса в качестве кандидата для долгосрочной защиты от атак квантовых компьютеров.

Криптография изогении суперсингулярной эллиптической кривой

Эта криптографическая система полагается на свойства суперсингулярных эллиптических кривых и суперсингулярных графов изогении для создания замены Диффи-Хеллмана с прямой секретностью . Эта криптографическая система использует хорошо изученную математику суперсингулярных эллиптических кривых для создания обмена ключами типа Диффи-Хеллмана, который может служить простой устойчивой к квантовым вычислениям заменой широко распространенных методов обмена ключами Диффи-Хеллмана и эллиптических кривых. Cегодня. Поскольку он работает во многом так же, как существующие реализации Диффи – Хеллмана, он предлагает прямую секретность, которая считается важной как для предотвращения массового наблюдения со стороны правительств, так и для защиты от компрометации долгосрочных ключей в результате сбоев. В 2012 году исследователи Sun, Tian и Wang из Китайской государственной лаборатории ключей для сетей с интегрированными услугами и Xidian University расширили работу Де Фео, Джао и Плут на создание квантовых безопасных цифровых подписей на основе суперсингулярных изогений эллиптических кривых. На эту криптографическую систему нет патентов.

Квантовое сопротивление симметричного ключа

При условии использования ключей достаточно большого размера криптографические системы с симметричным ключом, такие как AES и SNOW 3G , уже устойчивы к атакам со стороны квантового компьютера. Кроме того, системы и протоколы управления ключами, которые используют криптографию с симметричным ключом вместо криптографии с открытым ключом, такие как Kerberos и структура аутентификации мобильной сети 3GPP , также по своей сути защищены от атак квантового компьютера. Учитывая его широкое распространение в мире, некоторые исследователи рекомендуют более широкое использование Kerberos-подобного симметричного управления ключами в качестве эффективного способа получения постквантовой криптографии сегодня.

Снижение безопасности

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

Криптография на основе решеток - подпись Ring-LWE

В некоторых версиях Ring-LWE есть сокращение безопасности до задачи кратчайшего вектора (SVP) в решетке в качестве нижней границы безопасности. SVP, как известно, NP-сложен . Конкретные кольцевые LWE-системы, которые имеют доказуемое снижение безопасности, включают вариант кольцевых LWE-подписей Любашевского, определенных в статье Гюнесу, Любашевского и Пёппельманна. Схема подписи GLYPH представляет собой вариант подписи Гюнесу, Любашевского и Пёппельманна (GLP), которая учитывает результаты исследований, которые были получены после публикации подписи GLP в 2012 году. Другой подписью Ring-LWE является Ring-TESLA. Также существует «дерандомизированный вариант» LWE, называемый обучением с округлением (LWR), который дает «улучшенное ускорение (за счет устранения небольших ошибок выборки из гауссовского распределения с детерминированными ошибками) и пропускную способность». В то время как LWE использует добавление небольшой ошибки, чтобы скрыть младшие биты, LWR использует округление для той же цели.

Криптография на основе решеток - NTRU, BLISS

Считается, что безопасность схемы шифрования NTRU и подписи BLISS связана с проблемой ближайшего вектора (CVP) в решетке , но не может быть сведена к ней . CVP известен как NP-жесткий . Исследовательская группа постквантовой криптографии, спонсируемая Европейской комиссией, предложила изучить вариант NTRU Стеле – Штейнфельда, который имеет снижение безопасности, для долгосрочного использования вместо исходного алгоритма NTRU.

Многовариантная криптография - несбалансированное масло и уксус

Несбалансированные схемы подписи маслом и уксусом - это асимметричные криптографические примитивы, основанные на многомерных полиномах над конечным полем . Булыгин, Петцольдт и Бухманн показали сведение типичных многомерных квадратичных систем UOV к NP-трудной задаче решения многомерных квадратичных уравнений . ${\ Displaystyle \ mathbb {F}}$

Криптография на основе хеша - схема подписи Меркла

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

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

Сообщение Quantum Cryptography Study Group под эгидой Европейской комиссией рекомендовала использовать схемы подписи Merkle для долгосрочного обеспечения безопасности в отношении квантовых компьютеров.

Криптография на основе кода - МакЭлис

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

Криптография на основе кода - RLCE

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

Криптография изогении суперсингулярной эллиптической кривой

Безопасность связана с проблемой построения изогении между двумя суперсингулярными кривыми с одинаковым числом точек. Самое последнее исследование сложности этой проблемы, проведенное Делфсом и Гэлбрейтом, показывает, что эта проблема настолько сложна, насколько предполагают изобретатели обмена ключами. Нет никакого снижения безопасности к известной NP-сложной проблеме.

Сравнение

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

Алгоритм	Тип	Открытый ключ	Закрытый ключ	Подпись
NTRU Шифрование	Решетка	766,25 B	842,875 B
Оптимизированный НТРУ Прайм	Решетка	154 млрд
Радуга	Многомерный	124 КБ	95 КБ
СФИНКОВ	Хеш-подпись	1 КБ	1 КБ	41 КБ
СФИНКЫ +	Хеш-подпись	32 млрд	64 млрд	8 КБ
БЛИСС- II	Решетка	7 КБ	2 КБ	5 КБ
GLP-вариант Подпись GLYPH	Кольцо-LWE	2 КБ	0,4 КБ	1,8 КБ
Новая надежда	Кольцо-LWE	2 КБ	2 КБ
МакЭлис из Гоппы	На основе кода	1 МБ	11,5 КБ
Шифрование на основе случайного линейного кода	RLCE	115 КБ	3 КБ
Квазициклический MDPC на основе McEliece	На основе кода	1232 B	2464 B
SIDH	Изогения	564 млрд	48 млрд
SIDH (сжатые ключи)	Изогения	330 млрд	48 млрд
3072-битный дискретный журнал	не PQC	384 млрд	32 млрд	96 млрд
256-битная эллиптическая кривая	не PQC	32 млрд	32 млрд	65 млрд

Практическое соображение при выборе постквантовых криптографических алгоритмов - это усилия, необходимые для отправки открытых ключей через Интернет. С этой точки зрения алгоритмы Ring-LWE, NTRU и SIDH обеспечивают размер ключей до 1 КБ, открытые ключи с хэш-подписью составляют менее 5 КБ, а МакЭлис на основе MDPC занимает около 1 КБ. С другой стороны, схемы Rainbow требуют около 125 КБ, а МакЭлис на основе Goppa требует ключа размером около 1 МБ.

Криптография на основе решеток - обмен ключами LWE и обмен ключами Ring-LWE

Фундаментальная идея использования LWE и Ring LWE для обмена ключами была предложена и подана в Университет Цинциннати в 2011 году Джинтаем Дингом. Основная идея исходит из ассоциативности умножения матриц, а ошибки используются для обеспечения безопасности. Статья появилась в 2012 году после подачи предварительной заявки на патент в 2012 году.

В 2014 году Пайкерт представил ключевую транспортную схему, следуя той же базовой идее Динга, где также используется новая идея отправки дополнительного 1-битного сигнала для округления в конструкции Динга. Для несколько более чем 128 битов безопасности Сингх представляет набор параметров, которые имеют 6956-битные открытые ключи для схемы Пайкерта. Соответствующий закрытый ключ будет примерно 14 000 бит.

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

Криптография на основе решеток - шифрование NTRU

Для 128 битов безопасности в NTRU Хиршхорн, Хоффштейн, Ховгрейв-Грэм и Уайт рекомендуют использовать открытый ключ, представленный в виде полинома 613 степени с коэффициентами . В результате получается открытый ключ длиной 6130 бит. Соответствующий закрытый ключ будет иметь длину 6743 бита. ${\ displaystyle {\ bmod {\ left (2 ^ {10} \ right)}}}$

Многовариантная криптография - Радужная подпись

Для 128-битной защиты и наименьшего размера подписи в многомерной схеме подписи с квадратичным уравнением Rainbow Петцольдт, Булыгин и Бухманн рекомендуют использовать уравнения с размером открытого ключа чуть более 991000 бит, закрытым ключом чуть более 740000 бит и цифровым подписи длиной 424 бита. ${\ displaystyle \ mathbb {F} _ {31}}$

Криптография на основе хеша - схема подписи Меркла

Чтобы получить 128 бит безопасности для подписей на основе хэша для подписи 1 миллиона сообщений с использованием метода фрактального дерева Меркла Наора Шенхава и Вула, размеры открытого и закрытого ключей составляют примерно 36 000 битов в длину.

Криптография на основе кода - МакЭлис

Для 128-битной защиты в схеме Мак-Элиса Исследовательская группа по постквантовой криптографии Европейской комиссии рекомендует использовать двоичный код Гоппа длиной не менее и не менее размера , способный исправлять ошибки. С этими параметрами открытый ключ для системы Мак-Элиса будет систематической образующей матрицей, неидентификационная часть которой принимает биты. Соответствующий закрытый ключ, состоящий из кодовой поддержки с элементами из и порождающего полинома с коэффициентами из , будет иметь длину 92027 бит. ${\ displaystyle n = 6960}$${\ displaystyle k = 5413}$${\ displaystyle t = 119}$${\ Displaystyle к \ раз (нк) = 8373911}$${\ displaystyle n = 6960}$${\ displaystyle GF (2 ^ {13})}$${\ displaystyle t = 119}$${\ displaystyle GF (2 ^ {13})}$

Группа также изучает возможность использования квазициклических кодов MDPC длиной не менее и размерностью не менее и способных исправлять ошибки. С этими параметрами открытый ключ для системы Мак-Элиса будет первой строкой систематической матрицы генератора, неидентификационная часть которой принимает биты. Закрытый ключ, квазициклическая матрица проверки на четность с ненулевыми элементами в столбце (или в два раза больше в строке), занимает не более чем биты, когда он представлен как координаты ненулевых элементов в первой строке. ${\ displaystyle n = 2 ^ {16} + 6 = 65542}$${\ displaystyle k = 2 ^ {15} + 3 = 32771}$${\ displaystyle t = 264}$${\ displaystyle k = 32771}$${\ displaystyle d = 274}$${\ displaystyle d \ times 16 = 4384}$

Barreto et al. рекомендуют использовать двоичный код Goppa длиной не менее и размером не менее , способный исправлять ошибки. С этими параметрами открытый ключ для системы Мак-Элиса будет систематической образующей матрицей, неидентификационная часть которой принимает биты. Соответствующий закрытый ключ, который состоит из кодовой поддержки с элементами из и порождающего полинома с коэффициентами из , будет иметь длину 40 476 бит. ${\ displaystyle n = 3307}$${\ displaystyle k = 2515}$${\ displaystyle t = 66}$${\ Displaystyle к \ раз (нк) = 1991880}$${\ displaystyle n = 3307}$${\ displaystyle GF (2 ^ {12})}$${\ displaystyle t = 66}$${\ displaystyle GF (2 ^ {12})}$

Криптография изогении суперсингулярной эллиптической кривой

Для 128-битной защиты в методе суперсингулярной изогении Диффи-Хеллмана (SIDH) Де Фео, Джао и Плут рекомендуют использовать суперсингулярную кривую по модулю 768-битного простого числа. Если используется сжатие точек эллиптической кривой, длина открытого ключа не должна превышать 8x768 или 6144 бит. В опубликованной в марте 2016 г. статье авторов Азардерахша, Джао, Калача, Козила и Леонарди показано, как сократить количество передаваемых битов вдвое, что было дополнительно улучшено авторами Костелло, Джао, Лонга, Наэриг, Ренес и Урбаник, что привело к сжатию - Ключевая версия протокола SIDH с открытыми ключами размером всего 2640 бит. Это делает количество передаваемых битов примерно эквивалентным неквантовой безопасности RSA и алгоритму Диффи-Хеллмана с тем же классическим уровнем безопасности.

Криптография на основе симметричного ключа

Как правило, для 128-битной защиты в системе с симметричным ключом можно безопасно использовать размер ключа 256 бит. Лучшая квантовая атака против обычных систем с симметричными ключами - это применение алгоритма Гровера , которое требует работы, пропорциональной квадратному корню из размера ключевого пространства. Для передачи зашифрованного ключа устройству, обладающему симметричным ключом, необходимым для расшифровки этого ключа, также требуется примерно 256 бит. Ясно, что системы с симметричным ключом предлагают наименьшие размеры ключей для постквантовой криптографии.

Прямая секретность

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

Как обмен ключами Ring-LWE, так и обмен ключами суперсингулярной изогении Диффи-Хеллмана (SIDH) могут поддерживать прямую секретность в одном обмене с другой стороной. И Ring-LWE, и SIDH также могут использоваться без прямой секретности, создав вариант классического варианта шифрования Эль-Гамаля по алгоритму Диффи-Хеллмана.

Другие алгоритмы в этой статье, такие как NTRU, не поддерживают прямую секретность как есть.

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

Открыть проект Quantum Safe

Проект Open Quantum Safe ( OQS ) был запущен в конце 2016 года и направлен на разработку и прототипирование квантовой криптографии. Он нацелен на интеграцию текущих постквантовых схем в одну библиотеку: liboqs . liboqs - это библиотека C с открытым исходным кодом для квантово-устойчивых криптографических алгоритмов. Первоначально он фокусируется на алгоритмах обмена ключами. Он предоставляет общий API, подходящий для постквантовых алгоритмов обмена ключами, и объединяет различные реализации. liboqs также будет включать средства тестирования и процедуры тестирования для сравнения производительности постквантовых реализаций. Кроме того, OQS также обеспечивает интеграцию liboqs в OpenSSL .

По состоянию на апрель 2017 года поддерживаются следующие алгоритмы обмена ключами:

Алгоритм	Тип
BCNS15	Кольцевое обучение с ошибками обмена ключами
Новая надежда	Кольцевое обучение с ошибками обмена ключами
Фродо	Обучение с ошибками
НТРУ	Криптография на основе решеток
SIDH	Обмен ключами суперсингулярной изогении
Макбитс	Коды с исправлением ошибок

Реализация

Одной из основных проблем постквантовой криптографии считается внедрение потенциально безопасных квантовых алгоритмов в существующие системы. Были проведены тесты, например, Microsoft Research, реализующие PICNIC в PKI с использованием аппаратных модулей безопасности . Тестовые реализации алгоритма Google NewHope также были выполнены поставщиками HSM .

Смотрите также

• Постквантовая стандартизация криптографии NIST
• Квантовая криптография - криптография, основанная на квантовой механике

использованная литература

дальнейшее чтение

• Постквантовая криптография . Springer. 2008. с. 245. ISBN 978-3-540-88701-0.
• Изогении в квантовом мире
• Об идеальных решетках и обучении с ошибками над кольцами
• Возвращение к Kerberos: квантово-безопасная аутентификация
• Схема подписи для пикника

внешние ссылки

• PQCrypto, конференция по постквантовой криптографии
• Стандарты квантовой безопасности ETSI
• Пост-квантовый криптопроект NIST
• Использование и развертывание PQCrypto