Доказательства безопасности и сведение в решетчатых схемах

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

Знаменитое доказательство Регева 2005 года показывает, что алгоритм полиномиального времени, решающий задачу различения LWE, можно использовать для решения задачи GapSVP (задачи о кратчайшем векторе с зазором) на решётках размерности n в наихудшем случае. Это сведение является квантовым: в нём используется квантовая процедура выборки, преобразующая алгоритм решения LWE в алгоритм решения задачи на решётке. Это означает, что LWE не менее трудна, чем задачи на решётках в наихудшем случае, при использовании квантовых вычислений.

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

Для схемы шифрования на основе LWE доказывается стойкость IND-CPA (неотличимость при атаке с выбранным открытым текстом) с помощью гибридного доказательства. Доказательство показывает, что различитель IND-CPA позволяет построить различитель LWE. В первом гибриде настоящий шифротекст заменяется равномерно случайной строкой; неотличимость следует из предположения LWE. Это даёт ясное доказательство стойкости базового решёточного шифрования.

Стойкости IND-CPA недостаточно для механизмов инкапсуляции ключа, используемых в TLS: им требуется стойкость IND-CCA2 (при атаке с выбранным шифротекстом). Преобразование Фудзисаки—Окамото (FO) превращает любую схему со стойкостью IND-CPA в KEM со стойкостью IND-CCA2 в модели случайного оракула (ROM). ML-KEM применяет вариант преобразования FO к лежащему в основе шифрованию на основе модульного LWE, обеспечивая стойкость CCA2, необходимую для практического применения.

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

Доказательство в стандартной модели не делает идеализации относительно хеш-функций и строго сильнее доказательства в ROM. В большинстве практических решёточных схем используются доказательства в ROM, поскольку доказательства стойкости CCA2 в стандартной модели для решёточных KEM значительно сложнее и приводят к менее благоприятным конкретным параметрам. NIST принял доказательства на основе ROM для ML-KEM, считая их достаточными для целевых уровней стойкости.

Доказательство стойкости ML-KEM состоит из двух этапов. Сначала показывается, что лежащее в основе шифрование на основе модульного LWE обладает стойкостью IND-CPA в предположении о трудности модульного LWE. Затем преобразование Фудзисаки—Окамото, а именно преобразования T и U, используемые в Kyber, повышает эту стойкость до IND-CCA2 в квантовой модели случайного оракула (QROM), учитывающей противников, которые запрашивают случайный оракул в суперпозиции.

Оценщик решёток, разработанный Альбрехтом, Плейером и Скоттом, является стандартным инструментом для оценки конкретной стойкости схем на основе LWE. Он моделирует стоимость известных наилучших атак на решётки, включая BKZ с просеиванием или перебором, и выдаёт оценку стойкости в битах для заданных параметров (n, q, sigma). Инструмент регулярно обновляется по мере публикации новых алгоритмов и моделей стоимости оборудования.

Алгоритм блочной редукции Коркина—Золотарёва (BKZ) является наиболее эффективным на практике алгоритмом редукции решёток. BKZ с размером блока beta находит короткие векторы со сложностью примерно 2^{0.292*beta} вентильных операций при использовании лучших алгоритмов просеивания. Для ML-KEM-768 оцениваемая классическая стойкость составляет около 180 бит, а квантовая стойкость — около 164 бит, что значительно выше целевого уровня в 192 бита.

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

Какое преобразование используется для повышения стойкости решёточного шифрования IND-CPA до IND-CCA2 в ML-KEM?

Доказательства стойкости решёточных схем сводят стойкость схемы к трудности решения LWE или SVP. Сведение Регева гарантирует, что LWE не менее трудна, чем задачи на решётках в наихудшем случае. Преобразование Фудзисаки—Окамото повышает стойкость с IND-CPA до IND-CCA2 в ROM. Конкретная стойкость оценивается с помощью оценщика решёток и моделей сложности BKZ. Разрывы в плотности сведений означают, что практические параметры опираются на оценки стоимости атак, а не только на границы сведений.