Механизм инкапсуляции ключа на решетках «Земляника»
«Земляника» представляет собой постквантовый механизм инкапсуляции ключа (МИК) на решетках. Криптографическая стойкость “Земляники” обеспечивается сложностью решения модульной версии задачи обучения с ошибками (Module-LWE, M-LWE), сводящейся к сложным геометрическим задачами на модульных решетках.
Задача M-LWE считается надежным основанием для построения криптографических схем, что подтверждается ее использованием в постквантовых стандартах США ML-KEM и ML-DSA. Конструкция нашего МИК следует широко распространенной парадигме построения. А именно, «Земляника» получается путем применения преобразования к системе асимметричного шифрования. Относится к модификациям преобразования Фуджисаки-Окамото, которые нашли широкое применение при построении постквантовых МИК.
Таким образом, при построении «Земляники» мы использовали хорошо проверенные и распространенные подходы. С другой стороны, наше решение обладает рядом особенностей.
Стек технологий:
Свидетельство о государственной регистрации программы для ЭВМ
Задача M-LWE считается надежным основанием для построения криптографических схем, что подтверждается ее использованием в постквантовых стандартах США ML-KEM и ML-DSA. Конструкция нашего МИК следует широко распространенной парадигме построения. А именно, «Земляника» получается путем применения преобразования к системе асимметричного шифрования. Относится к модификациям преобразования Фуджисаки-Окамото, которые нашли широкое применение при построении постквантовых МИК.
Таким образом, при построении «Земляники» мы использовали хорошо проверенные и распространенные подходы. С другой стороны, наше решение обладает рядом особенностей.
Стек технологий:
Свидетельство о государственной регистрации программы для ЭВМ
Особенности «Земляники»
Модуль, равный степени двойки
текст
Явное оповещение об ошибке при декапсуляции
текст
Использование новых требований к параметрам защиты от атак
текст
Мы выделяем три ключевых особенности нашего МИК: модуль, равный степени двойки, явное оповещение об ошибке при декапсуляции, а также использование новых требований к параметрам защиты от атак, эксплуатирующих ошибки при декапсуляции. Далее кратко опишем каждую из указанных особенностей.
Выбор в качестве модуля q степени двойки нетипичен для криптографических схем на основе задачи M-LWE, поскольку он исключает использование быстрых алгоритмов умножения на основе NTT. С другой стороны, такой выбор избавляет от необходимости приведения чисел по модулю, а также упрощает генерацию некоторых объектов в ходе работы МИК.
Явное оповещение об ошибке при декапсуляции стало возможным благодаря недавним работам, посвященным безопасности преобразования . Насколько нам известно, “Земляника” — это первый МИК, в котором используется явное оповещение об ошибках при декапсуляции. Такой выбор позволяет минимизировать число дополнительных операций, вносимых в систему шифрования, для получения МИК.
Для достижения стойкости к атакам, эксплуатирующим ошибки при декапсуляции, разработчики многих современных МИК, включая ML-KEM, выбирали параметры схемы таким образом, чтобы вероятность возникновения ошибки при декапсуляции в среднем (обозначается за ) была пренебрежимо мала. Конкретные требования к этой величине предъявлялись исходя из избыточных возможностей злоумышленника. Последнее влечет завышенные требования к , что негативно сказывается на эксплуатационных характеристиках МИК. При разработке “Земляники” нами был предложен новый способ оценки сложности атак, эксплуатирующих ошибки при декапсуляции. Его применение позволило снизить требования к , что способствовало улучшению эксплуатационных характеристик “Земляники”. Однако применение нашего способа сопряжено с оценкой некоторых нетривиальных характеристик МИК. Поэтому на сегодняшний день нам удалось пересмотреть значение только для одного набора параметров.
Выбор в качестве модуля q степени двойки нетипичен для криптографических схем на основе задачи M-LWE, поскольку он исключает использование быстрых алгоритмов умножения на основе NTT. С другой стороны, такой выбор избавляет от необходимости приведения чисел по модулю, а также упрощает генерацию некоторых объектов в ходе работы МИК.
Явное оповещение об ошибке при декапсуляции стало возможным благодаря недавним работам, посвященным безопасности преобразования . Насколько нам известно, “Земляника” — это первый МИК, в котором используется явное оповещение об ошибках при декапсуляции. Такой выбор позволяет минимизировать число дополнительных операций, вносимых в систему шифрования, для получения МИК.
Для достижения стойкости к атакам, эксплуатирующим ошибки при декапсуляции, разработчики многих современных МИК, включая ML-KEM, выбирали параметры схемы таким образом, чтобы вероятность возникновения ошибки при декапсуляции в среднем (обозначается за ) была пренебрежимо мала. Конкретные требования к этой величине предъявлялись исходя из избыточных возможностей злоумышленника. Последнее влечет завышенные требования к , что негативно сказывается на эксплуатационных характеристиках МИК. При разработке “Земляники” нами был предложен новый способ оценки сложности атак, эксплуатирующих ошибки при декапсуляции. Его применение позволило снизить требования к , что способствовало улучшению эксплуатационных характеристик “Земляники”. Однако применение нашего способа сопряжено с оценкой некоторых нетривиальных характеристик МИК. Поэтому на сегодняшний день нам удалось пересмотреть значение только для одного набора параметров.
Наборы параметров
На сегодняшний день мы предлагаем четыре набора параметров для «Земляники». Соответствующие им эксплуатационные характеристики МИК перечислены в таблице ниже. За , и обозначены размеры секретного ключа, открытого ключа и шифртекста. Все размеры даны в байтах. В столбцах KeyGen, Encaps и Decaps представлены результаты измерения времени выполнения трех основных алгоритмов МИК на одном ядре процессора архитектуры ARM64 (Apple M1). Для проведения вычислительных экспериментов использовался программный прототип «Земляники», разработанный на языке программирования C. В столбцах и представлены уровни практической стойкости «Земляники» к атакам с применением классического и квантового компьютера, соответственно.
Статус развития
В настоящее время процесс разработки и анализа «Земляники» продолжается. В частности, исследуется возможность применения предложенного способа оценки сложности атак, эксплуатирующих ошибки при декапсуляции, для наборов параметров Z512 и Z1024. Кроме того, исследуются возможности ускорения операции умножения многочленов и ускорения генерации псевдослучайных бинарных строк. Также исследуются другие модели оценки сложности задачи M-LWE.
