Криптоанализ пост-квантовых примитивов, основанных на решётках и кодах: рекорды на практике и ускорения в теории

КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

ОБЩИЕ СВЕДЕНИЯ

Номер проекта 22-41-04411

НазваниеКриптоанализ пост-квантовых примитивов, основанных на решётках и кодах: рекорды на практике и ускорения в теории

Руководитель Самусев Илья Геннадьевич, Кандидат физико-математических наук

Организация финансирования, регион федеральное государственное автономное образовательное учреждение высшего образования "Балтийский федеральный университет имени Иммануила Канта" , Калининградская обл

Конкурс №54 - Конкурс 2021 года «Проведение фундаментальных научных исследований и поисковых научных исследований международными научными коллективами» (DFG)

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-102 - Алгебра

Ключевые слова пост-квантовая криптография, криптография на решетках, криптография на кодах, практический криптоанализ, квантовое ускорение, упаковка шаров

Код ГРНТИ27.15.25

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ

Аннотация
Целью нашего проекта является разработка новых и расширение существующих криптоаналитических инструментов для схем на основе решеток и кодов. Основу нашего исследования составляет анализ сложности математических задач, лежащих в криптографических конструкциях на базе решеток и кодов. Углубление нашего понимания этих проблем не только повысит нашу уверенность в криптографических конструкциях на основе решеток и кодов, но и поможет практикам в случае, если дело дойдет до реальных приложений. Вполне вероятно, что в ближайшем будущем эти криптографические приложения войдут в нашу повседневную жизнь. В 2016 году Национальный институт стандартов и технологий (NIST) открыл конкурс по отбору постквантовых кандидатов, направленный на выбор схем шифрования и цифровых подписей, которые заменят имеющиеся в настоящее время криптографические алгоритмы, уязвимые относительно квантовых атак. Предложенные схемы шифрования, которые к настоящему времени пережили процесс отбора, либо основаны на решетках (3 из 4), либо на кодах (1 из 4). Для подписей 2 из 3 финалистов касаются решеток. Тем не менее, существует шанс, что мы будем полагаться либо на решетчатые, либо на кодовые предположения безопасности, а может быть, даже на оба из них. Однако, прежде чем такие схемы будут готовы к реализации, необходимо решить множество вопросов, и многие из них носят криптоаналитический характер. Наш проект посвящен криптоанализу постквантовых криптографических схем шифрования с открытым ключом на решетках и кодах. В работе мы рассматриваем три исследовательских направления: криптоанализ криптосистемы NTRU как яркий пример криптосхемы на решетках, криптоанализ криптосистемы Мак-Элиса как наиболее важный пример схемы шифрования с открытым ключом на кодах и, в-третьих, построение решеток с большим контактным числом. Мы рассматриваем криптосистему NTRU как одну из, возможно, наименее понятных с криптоаналитической точки зрения схем на решетках. Цель нашего исследования заключается в: 1. усовершенствовании различных комбинаторных атак на NTRU, в том числе атак типа «встреча посередине»; 2. выполнении средне - и крупномасштабных экспериментов относительно NTRU-атак и установления практической значимости этих атак; 3. разработке квантового ускорения для предложенных классических улучшений. Для криптосистемы Мак-Элиса мы объединим все последние результаты, касающиеся декодирования случайных линейных кодов, в программную реализацию с открытым исходным кодом, закладывая основу для дальнейших практических разработок в этой области, попутно отвечая на вопросы о гарантиях безопасности относительно конкретных параметров криптосистемы, а также уделим внимание асимптотической стороне работы, проводимой за последнее время. Мы оформим наши результаты в виде общедоступного анализа безопасности для схем на основе кодов, что, в свою очередь, любой практик мог бы использовать в случае, если криптосистема Мак-Элиса станет стандартизированной. Наше третье направление относительно построения решеток с большим контактным числом имеет значение как в теории, так и на практике. С теоретической точки зрения наша цель -- решить вопрос о том, является ли недавно предложенная конструкция решеток с экспоненциальным контактным числом плотной. Этот вопрос не так далек от криптоанализа, как может показаться: решетки с большим контактным числом дают хорошие сферические коды, которые, в свою очередь, используются в быстрых алгоритмах для решения задачи нахождения кратчайшего вектора -- основы криптоанализа криптосистем на решетках. Мы исследуем применимость решеток с большим контактным числом к криптоанализу, ответив на вопрос, допускают ли такие решетки быстрые алгоритмы декодирования.

ОТЧЁТНЫЕ МАТЕРИАЛЫ

Публикации

1. Киршанова Е, Май А. Decoding McEliece with a Hint – Secret Goppa Key Parts Reveal Everything Security and Cryptography for Networks: 13th International Conference, SCN 2022, Amalfi (SA), С. 3–20 (год публикации - 2022)
10.1007/978-3-031-14791-3_1

2. Кунинец А.А., Малыгина Е.С. Анализ минимального расстояния АГ-кода, ассоциированного с максимальной кривой рода три Прикладная дискретная математика, № 58, С. 5-14 (год публикации - 2022)
10.17223/20710410/X/1

3. Агравал С., Киршанова Е., Штеле Д., Йадав А. Practical, Round-Optimal Lattice-Based Blind Signatures Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, стр. 39–53 (год публикации - 2022)
10.1145/3548606.3560650

4. Новоселов С.А. О вычислении группы классов идеалов мнимых мультиквадратичных полей Прикладная дискретная математика, № 58. С. 26-30 (год публикации - 2022)
10.17223/20710410/58/3

Публикации

1. Киршанова Е.А., Май А. Breaking Goppa-Based McEliece with Hints Information and Computation, Volume 293, pages 105045 (год публикации - 2023)
10.1016/j.ic.2023.105045

2. Киришанова Е.А., Май A., Новаковский Ю. New NTRU Records with Improved Lattice Bases Lecture Notes in Computer Science, LNCS, PQCrypto 2023: Post-Quantum Cryptography. pp. 167–195, volume 14154 (год публикации - 2023)
10.1007/978-3-031-40003-2_7

3. Новоселов С.А. On the Discrete Logarithm Problem in the Ideal Class Group of Multiquadratic Fields Lecture Notes in Computer Science, Progress in Cryptology – LATINCRYPT 2023. Lecture Notes in Computer Science, vol 14168. Springer, Cham pp 192–211 (год публикации - 2023)
10.1007/978-3-031-44469-2_10

4. Малыгина Е.С., Кунинец А.А. Вычисление пар, исправляющих ошибки, для алгеброгеометрического кода. Издательский Дом ТГУ, Прикладная дискретная математика. Приложение., Прикладная дискретная математика. Приложение, 2023, выпуск 16, страницы 136–140 DOI: https://doi.org/10.17223/2226308X/16/36 (год публикации - 2023)
10.17223/2226308X/16/36

5. Малыгина Е.С., Кунинец А.А., Раточка В.Л., Дупленко А.Г., Нейман Д.Я. Алгеброгеометрические коды и их декодирование на основе пар, исправляющих ошибки Издательский Дом ТГУ, Прикладная дискретная математика., Прикладная дискретная математика, 2023, № 62, страницы 83–105 DOI 10.17223/20710410/62/7 (год публикации - 2023)
10.17223/20710410/62/7

Аннотация результатов, полученных в 2024 году
По направлению 1 (криптоанализ схем на решетках): 1.1 Совместно с немецкой стороной (Рурский университет г. Бохум в лице Проф. А. Мая и аспиранта 3го года Ю.Новаковским) разработан гибридный алгоритм, решающий задачу LWE. Сделан асимптотический и конкретный анализы алгоритма, а также его распараллеленная реализация. Реализация доступна по адресу https://github.com/ElenaKirshanova/g6k_hybrid 1.2 Разработан эвристический алгоритм для нахождения коротких векторов в идеальных решётках мультиквадратичных полей, который позволяет находить короткие вектора с субэкспоненциальным фактором аппроксимации за квази-полиномиальное время от размерности решётки. Для сравнения - алгоритм BKZ, работающий для любой решётки, позволяет находить вектора с таким фактором аппроксимации за субэкспоненциальное время. Работа принята на конференцию IndoCrypt 2024. Реализация алгоритма доступна по адресу: https://github.com/novoselov-sa/mqASVP По направлению 2 (криптоанализ кодовых криптосистем, в частности МакЭлиса): 2.1. Для произвольного АГ-кода и дуального к нему, а также для их подполевых подкодов получен явный вид пар, исправляющих ошибки. Представлена классификация кодов, участвующих в построении пары, относительно MDS-свойства. Показана неприменимость пар, исправляющих ошибок, определённых в базовом поле, для декодирования подполевых подкодов, а также для криптоанализа схем на подполевых подкодах АГ-кодов. Результат опубликован в журнале «Прикладная дискретная математика», полная версия доступна по адресу: https://www.mathnet.ru/rus/pdm848 2.2. Получено обобщение алгоритма Márquez-Corbella и др. для VSAG-кодов на класс алгебро-геометрических кодов C_L(X,P,E) с параметрами 2g + 1 < m < n − 3, где g - род кривой X, n = deg P, а m = deg E. Алгоритм позволяет за полиномиальное время восстановить по порождающей матрице кода исходное представление кода (с точностью до изоморфизма кривых и эквивалентности дивизоров). Результат отправлен в журнал. Реализация алгоритма доступна по адресу: https://github.com/kn02262/AG-code-representation/ 2.3. Представлен детальный обзор построения квазициклических GRS-кодов и альтернантных кодов, а также описана редукция ключевой безопасности квазициклических алгеброгеометрических кодов к ключевой безопасности инвариантных кодов, ассоциированных с той же кривой, однако имеющих меньшую длину и размерность. Таким образом, была показана зависимость стойкости к структурным атакам рассматриваемых кодов от стойкости к структурным атакам инвариантных (свёрнутых) кодов с меньшими параметрами, а также переработано доказательство такой зависимости для случая диагонализируемого автоморфизма проективной прямой. Также были представлены подробные примеры, иллюстрирующие возможность восстановления параметров исходного кода при знании секретных параметрах инвариантного кода. Результаты были доложены на конференции SibeCrypt 2024 (https://www.mathnet.ru/rus/pdma668), а также опубликованы в журнале «Прикладная дискретная математика», полная версия доступна по адресу: https://www.mathnet.ru/rus/pdm848 2.4. Совместно с немецкой стороной (Ruhr University Bochum и Technical University Munich), продолжена работа по восстановлению ключа криптосистемы МакЭлиса, зная частичную информацию о ключе. В работе также задействованы инженеры из Technology Innovation Institute для реализации предлагаемой атаки. Конкретно, мы используем ChipWhisperer для проведения “шаблонной” атаки на реализацию криптосистемы Classic McEliece для Cortex M4. Идея шаблона состоит в получения веса Хэмминга секрета на блоках размерности 32 бит. Имея эти веса, мы адаптируем алгоритмы декодирования по информационному множеству (Information Set Decoding). Мы показываем, насколько и как можно ускорить эти алгоритмы, добавляя дополнительные проверочные уравнения, полученные из весов на блоках. Получив теоретическую базу, мы на практике восстанавливаем секрет для размерности кода n = 2197 за несколько секунд. Без “шаблонной” атаки (то есть без информации о весе Хэмминга секрета на 32-битных блоках), инстанция такой размерности имеет сложность в 88 бит, что далеко от достижимой на практике. Полная версия статьи доступна по адресу https://eprint.iacr.org/2024/621. Статья опубликована на WCC’24, а также была приглашена в журнал Designs, Codes and Cryptography (Q1). 2.5. В совместной работе с криптографами из CWI (Амстердам), Киршанова Е.А. получила алгоритм декодирования случайных бинарных линейных кодов, основанный на идеи просеивания. В частности, в статье “Asymptotics and Improvements of Sieving for Codes” (полная версия доступна по адресу https://eprint.iacr.org/2023/1577.pdf) представлен алгоритм, комбинирующий вектора подкода малого веса Хэмминга, в вектора подкода бОльшей размерности (также малого веса Хэмминга). Идея взята из наиболее эффективных (из известных) алгоритмов просеивания для нахождения коротких векторов решетки. Сложность заключается в переносе идей на новую метрику (из евклидовой в метрику Хэмминга). Кроме этого в статье показаны методы хэширования (так называемые locality sensitive hashing), позволяющие найти “близкие” по весу Хэмминга вектора. Эти методы позволяют более эффективно найти (просеять) “короткие” кодовые слова из подкода в бОльший код. В работе дается анализ представленных алгоритмов и сравнение с существующими алгоритмами декодирования по информационным символам. Статья представлена на конференции Eurocrypt’2024 (A+) и опубликована в Lecture Notes of Computer Science. По направлению 3 (конструкции решеток из АГ-кодов): Совместно с Малыгиной Е.С. опубликована статья (Designs, Codes and Cryptography, Scopus, Q1) по конструкции решеток типа D из башни Гарсия-Штихтенота. В статье получена конструкция плотной решетки из АГ-кодов: описана Конструкция-D решетки, возникающая из башни Гарсии-Штихтенота, доказано “качество” полученной решетки, получен алгоритма декодирования подполевого подкода АГ-кода, используемого в построении. В частности, удалось улучшить плотность построенной решетки с максимального из известных Ω(sqrt(n/log n)) до Ω(sqrt(n)/log^eps n), где eps > 0 – произвольная константа. В частности, eps может быть выбрана меньше ½, что даёт асимптотическое улучшение относительно предыдущих работ. Для получения эффективного алгоритма был адаптирован так называемый алгоритм “мягкого” декодирования Кёттера-Ворди (IEEE Trans. Inf. Theory, no. 49(11), 2003). Изначально, алгоритм был предложен для кода Рида-Соломона. В этой работе мы показали, как расширить этот алгоритм на алгебро-геометрические коды и проанализировали качество полученного декодера. Полная версия работы представлена по адресу: https://eprint.iacr.org/2023/1730

Публикации

1. Кунинец А.А., Малыгина Е.С. Вычисление пар, исправляющих ошибки для алгеброгеометрического кода Прикладная дискретная математика, № 63, 65-90 (год публикации - 2024)
10.17223/20710410/63/4

2. Кунинец А.А., Малыгина Е.С. Построение квазициклических альтернантных кодов и их приложение в кодовых криптосистемах Прикладная дискретная математика, № 65, 84–109 (год публикации - 2024)
10.17223/20710410/65/5

3. Киршанова Е.А., Малыгина Е.С. Construction-D lattice from Garcia-Stichtenoth tower code Designs, Codes and Cryptography, vol. 92, no. 5, pp. 1127-1142 (год публикации - 2024)
10.1007/s10623-023-01333-2

4. Новоселов С.А. On Approx-SVP in multiquadratic ideal lattices Progress in Cryptology – INDOCRYPT 2024. Lecture Notes in Computer Science (год публикации - 2025)
10.1007/978-3-031-80308-6_4

5. Кунинец А.А. Квазициклические альтернантные коды и анализ их безопасности в криптографических приложениях Прикладная дискретная математика. Приложение, № 17, с. 147–152 (год публикации - 2024)
10.17223/2226308X/17/38

6. Дука Л., Ессер А., Етински С., Киршанова Е.А. Asymptotics and Improvements of Sieving for Codes Lecture Notes in Computer Science, vol 14657, pp. 151–180, Springer, Cham, EUROCRYPT 2024 (год публикации - 2024)
10.1007/978-3-031-58754-2_6

Возможность практического использования результатов
Полученные результаты имеют прямое влияние на стандартизацию и внедрение пост-квантовых механизмов защиты информации в РФ. Криптоанализ позволяет выявить небезопасные наборы параметров криптосистем и избегать их в рекомендациях по стандартизации и использовании криптографических схем.