Руководство по постквантовой криптографии

Руководство по постквантовой криптографии

Источник · Перевод автора

Эта статья была написана Беном Пересом (Ben Perez) и первоначально появилась в блоге Trail of Bits. Она переиздается с разрешения автора и включает дополнительные заметки и комментарии исследователей из лаборатории RI.

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

Квантовый Вычислительный Пример

Квантовые компьютеры – это не просто классические параллельные компьютеры. Часто считается, что, поскольку квантовый бит может занимать одновременно и 0, и 1, тогда n-битный квантовый компьютер может одновременно находиться в 2n состояниях и, следовательно, чрезвычайно быстро вычислять NP-полные задачи. Это не так, поскольку измерение квантового состояния уничтожает большую часть исходной информации. Например, квантовая система обладает полным знанием как импульса объекта, так и местоположения, но любое измерение импульса уничтожит информацию о местоположении и наоборот. Это известно как принцип неопределенности Гейзенберга. Следовательно, успешные квантовые алгоритмы состоят из серии преобразований квантовых битов, так что в конце вычисления измерение состояния системы не уничтожит необходимую информацию. Фактически, было показано, что не может существовать квантовый алгоритм, который одновременно пытается все решения некоторой NP-полной задачи и выводит правильный ввод. Другими словами, любой квантовый алгоритм для решения сложных классических задач должен использовать конкретную структуру рассматриваемой проблемы. Сегодня существует два таких алгоритма, которые можно использовать в криптоанализе.

Способность быстро учитывать большие числа может нарушить как RSA, так и криптографию на основе дискретного журнала. Самым быстрым алгоритмом для целочисленной факторизации является сито поля общего числа, которое выполняется за субэкспоненциальное время. Тем не менее, в 1994 году Питер Шор разработал квантовый алгоритм (алгоритм Шора) для целочисленной факторизации, который выполняется за полиномиальное время и, следовательно, сможет взломать любую RSA или дискретную криптосистему на основе логарифма (включая те, которые используют эллиптические кривые). Это подразумевает, что всякая широко используемая криптография с открытым ключом была бы небезопасной, если бы кто-то собирал квантовый компьютер.

Второй – алгоритм Гровера, который способен инвертировать функции за O (√n) времени. Этот алгоритм снизил бы безопасность криптографии с симметричным ключом на корневой фактор, поэтому AES-256 обеспечит только 128-битную защиту. Точно так же поиск предварительного изображения 256-битной хеш-функции займет всего 2128 раз. Поскольку повышение безопасности хэш-функции или AES в два раза не очень обременительно, алгоритм Гровера не представляет серьезной угрозы для симметричной криптографии. Кроме того, изобретение квантового компьютера не затронет ни один из генераторов псевдослучайных чисел, предлагаемых для криптографического использования, за исключением, возможно, фактора O (√n), возникающего в алгоритме Гровера.

Типы постквантовых алгоритмов

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

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

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

Решетки

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

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

где дан вектор a, мы видим результат ax, не зная x. После достаточного количества запросов к этой функции мы можем за короткое время выучить f (решая систему уравнений, приведенную выше). Таким образом, мы можем переосмыслить задачу линейной алгебры как проблему машинного обучения.

Теперь предположим, что мы вводим небольшое количество шума в нашу функцию, так что после умножения x и a мы добавляем член ошибки e и уменьшаем все это по модулю простого числа (среднего размера) q. Тогда наша шумная загадочная функция выглядит

Математически доказано, что изучение этой шумной загадочной функции чрезвычайно сложно. Интуиция заключается в том, что на каждом шаге процедуры исключения Гаусса, которую мы использовали в нешумном случае, термин ошибки становится все больше и больше, пока он не затмевает всю полезную информацию о функции. В криптографической литературе это называется проблемой обучения с ошибками (Learning With Errors problem, LWE).

Криптография, основанная на LWE, называется криптографией на основе решетки, потому что доказательство того, что LWE сложно, основано на том факте, что известно, что поиск кратчайшего вектора в чем-то, называемом решеткой, является NP-Hard. Мы не будем углубляться в математику решеток здесь, но о решетках можно думать как о мозаике n-мерного пространства.

Решетки представлены координатными векторами. В приведенном выше примере любая точка в решетке может быть достигнута путем объединения e1, e2 и e3 (посредством сложения векторов нормалей). Самая короткая векторная задача (shortest vector problem, SVP) гласит: если задана решетка, найдите элемент, длина которого как вектор самая короткая. Интуитивная причина, по которой это сложно, заключается в том, что не все системы координат для данной решетки одинаково просты в работе. В приведенном выше примере мы могли бы вместо этого представить решетку с тремя координатными векторами, которые были чрезвычайно длинными и близко друг к другу, что затрудняет поиск векторов, близких к началу координат. На самом деле, существует канонический способ найти «наихудшее» представление решетки. Известно, что при использовании такого представления кратчайшая векторная задача является NP-сложной.

Прежде чем приступить к использованию LWE для создания квантовостойкой криптографии, мы должны отметить, что сам LWE не является NP-Hard. Вместо того, чтобы сводиться непосредственно к SVP, он сводится к приближению SVP, которое фактически считается не NP-Hard. Тем не менее, в настоящее время нет полиномиального (или субэкспоненциального) алгоритма для решения LWE.

Теперь давайте используем проблему LWE для создания реальной криптосистемы. Самая простая схема была создана Одедом Регевым (Oded Regev) в его оригинальной статье, доказывающей сложность проблемы LWE. Здесь секретный ключ является n-мерным вектором с целочисленными элементами mod q, то есть секретом LWE, упомянутым выше. Открытый ключ – это матрица A из предыдущего обсуждения вместе с вектором выходов из функции LWE

Важным свойством этого открытого ключа является то, что когда он умножается на вектор (-sk, 1), мы возвращаем термин ошибки, который равен примерно 0.

Чтобы зашифровать бит информации m, мы берем сумму случайных столбцов A и кодируем m в последней координате результата, добавляя 0, если m равно 0 и q / 2, если m равно 1. Другими словами, мы выбираем случайный вектор х 0 или 1, и вычислить

Интуитивно, мы только что оценили функцию LWE (которую мы знаем, что ее трудно сломать) и закодировали наш бит в выходных данных этой функции.

Расшифровка работает, потому что знание секрета LWE позволит получателю вернуть сообщение, плюс небольшой термин ошибки

Если распределение ошибок выбрано правильно, оно никогда не будет искажать сообщение более чем на q / 4. Получатель может проверить, является ли выход ближе к 0 или q / 2 mod q, и декодировать бит соответственно.

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

Начиная с оригинальной статьи Регева была проведена огромная работа по криптосистемам на основе решеток. Ключевым прорывом в улучшении их практичности стала разработка Ring-LWE, которая является вариантом проблемы LWE, где ключи представлены определенными полиномами. Это привело к квадратичному уменьшению размеров ключей и ускорило шифрование и дешифрование для использования только n * log (n) операций (с использованием методов быстрого Фурье).

Среди множества криптосистем на основе решетки, рассматриваемых в качестве стандарта NIST PQC, следует особо отметить две из них: конструкции Crystals, Kyber и Dilithium.

Kyber – это механизм инкапсуляции ключей (KEM), который следует структуре, аналогичной системе, описанной выше, но использует некоторую причудливую теорию алгебраических чисел, чтобы получить даже лучшую производительность, чем Ring-LWE. Размеры ключа составляют приблизительно 1 КБ для приемлемых параметров безопасности (все еще больших!), Но время шифрования и дешифрования составляет порядка 0,075 мс. Учитывая, что эта скорость была достигнута в программном обеспечении, Kyber KEM кажется многообещающим для постквантового обмена ключами.

Dilithium – это схема цифровой подписи, основанная на тех же методах, что и Kyber. Его детали выходят за рамки этого поста в блоге, но стоит упомянуть, что он также достигает довольно хорошей производительности. Размеры открытых ключей составляют около 1 КБ, а подписи – 2 КБ. Это также довольно производительно. На процессорах Skylake среднее количество циклов, необходимое для вычисления подписи, составило около 2 миллионов. Проверка заняла в среднем 390000 циклов.

Коды

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

При передаче двоичных сообщений ошибки могут возникать в виде переворотов битов. Коды с исправлением ошибок обеспечивают способность выдерживать определенное количество переворачиваний битов за счет компактности сообщений. Например, мы могли бы защитить от однобитовых переворотов, кодируя 0 как 000 и 1 как 111. Таким образом, получатель может определить, что 101 на самом деле был 111, или что 001 был 0, взяв большинство голосов из трех бит. Этот код не может исправить ошибки, когда два бита перевернуты, хотя, поскольку 111, превращающийся в 001, будет декодирован как 0.

Наиболее известный тип кодов с исправлением ошибок называется линейными кодами и может быть представлен k x n матрицами, где k – длина исходных сообщений, а n – длина кодированного сообщения. В общем, вычислительно сложно декодировать сообщения, не зная базового линейного кода. Эта жесткость лежит в основе безопасности криптосистемы с открытым ключом McEliece.

На высоком уровне секретный ключ в системе Мак-Элиса представляет собой случайный код (представленный в виде матрицы G) из класса кодов, называемых кодами Гоппа. Открытый ключ – это матрица SGP, где S – обратимая матрица с двоичными записями, а P – перестановка. Чтобы зашифровать сообщение m, отправитель вычисляет c = m (SGP) + e, где e – случайный вектор ошибок с точным количеством ошибок, которые код может исправить. Чтобы расшифровать, мы вычисляем cP-1 = mSG + eP-1, так что mS является кодовым словом G, которое может исправить добавленный термин ошибки e. Сообщение может быть легко восстановлено путем вычисления mSS-1.

Подобно решеткам, криптография на основе кода страдает от того факта, что ключи представляют собой большие матрицы. Используя рекомендуемые параметры безопасности, открытые ключи McEliece составляют около 1 МБ, а закрытые ключи – 11 КБ. В настоящее время ведется работа, направленная на использование специального класса кодов, называемых квазициклическими кодами проверки четности умеренной плотности, которые могут быть представлены более кратко, чем коды Гоппы, но безопасность этих кодов изучена хуже, чем коды Гоппы.

Изогении

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

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

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

Для схемы Supersingular Isogeny Diffie-Hellman (SIDH) секретные ключи представляют собой цепочку изогений, а открытые ключи – кривые. Когда Алиса и Боб объединяют эту информацию, они получают кривые, которые отличаются, но имеют один и тот же j-инвариант. Для целей криптографии не так важно, каков j-инвариант, а скорее то, что это число может быть легко вычислено как Алисой, так и Бобом после того, как они завершили обмен ключами.

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

Хеш-подписи

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

К сожалению, из хэшей невозможно построить схему шифрования KEM или открытого ключа. Поэтому сигнатуры на основе хешей не являются полным постквантовым криптографическим решением. Кроме того, они не занимают мало места; одна из наиболее многообещающих схем подписи, SPHINCS, производит подписи размером 41 Кбайт и открытые / закрытые ключи размером 1 Кбайт. С другой стороны, схемы, основанные на хэше, чрезвычайно быстры, поскольку они требуют только вычисления хеш-функций. Они также имеют чрезвычайно сильные доказательства безопасности, основанные исключительно на предположении, что существуют хеш-функции, которые являются стойкими к столкновениям и прообразами. Поскольку ничто не говорит о том, что современные широко используемые хеш-функции, такие как SHA3 или BLAKE2, уязвимы для этих атак, сигнатуры на основе хеша защищены.

Определения

Постквантовая криптография – это невероятно интересная область исследований, в которой за последнее десятилетие наблюдался огромный рост. Хотя четыре типа криптосистем, описанных в этом посте, получили большое академическое внимание, ни один из них не был одобрен NIST и, как следствие, пока не рекомендуется для общего использования. Многие из схем не являются производительными в их первоначальном виде и подвергались различным оптимизациям, которые могут влиять или не влиять на безопасность. Действительно, несколько попыток использовать более компактные коды для системы Мак-Элиса оказались небезопасными. На самом деле, получение максимальной защиты от постквантовых криптосистем требует жертвы некоторого количества пространства или времени. Криптография на основе кольцевой решетки является наиболее многообещающим направлением работы с точки зрения гибкости (как сигнатуры, так и KEM, также полностью гомоморфное шифрование), но предположения, на которых она основывается, интенсивно изучались в течение нескольких лет. Сейчас самым безопасным вариантом является использование McEliece с кодами Гоппы, поскольку он выдержал несколько десятилетий криптоанализа.

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

Заметки

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

Комментарии

1. «Квантовая система обладает полным знанием как импульса, так и местоположения объекта» – это кажется сомнительным утверждением. Эта идея существовала в 1920–1930-х годах и называлась «теориями со скрытыми переменными», но существует множество экспериментов, показывающих, что эти теории не работают. Согласно более современным взглядам, полное знание о импульсе и местоположении не может существовать.

2. «Если кто-то не найдет алгоритм полиномиального времени для факторизации больших целых чисел, этот риск минимален для современных лучших практик» – в настоящее время криптографическая факторизация (RSA) используется редко. Почти вся асимметричная криптография связана с проблемой дискретной логарифмизации.

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

4. Автор часто ссылается на класс NP-hard и рассуждения о времени вычисления полинома. Эти структуры прекрасны, но теперь более или менее ясно, что в криптографии их следует использовать с осторожностью. Нас больше интересуют проблемы, которые в среднем являются сложными, а не проблемы, среди которых сложные возникают только время от времени. Кроме того, даже если проблема может быть решена за полиномиальное время, но степень полинома очень велика, на практике проблема все еще неразрешима и может использоваться для криптографии.