Аннотация результатов, полученных в 2022 году
Будучи разделенным на три основных направления: криптоанализ схем на решётках, криптоанализ кодовых криптосистемы, построение плотных решеток из АГ-кодов), проект продвинулся по всем трём направлениям. По части решеток были получены два результата. В первом строится протокол слепой подписи, во втором получен алгоритм вычисления группы классов в мнимых мультиквадратичных полях. Полученная конструкция слепой подписи – наиболее эффективная из существующих пост-квантовых конструкций, обладающая малым размером подписи и эффективными алгоритмами генерации подписи и проверки. Безопасность схемы основана на предположении сложности новой и естественной с точки зрения слепых подписей задачи – задачи one-more-ISIS (еще одно короткое целочисленное решение). One-more-ISIS может считаться аналогом задачи one-more-RSA (на основе которой основана слепая подпись RSA) на языке решеток. Для понимания сложности задачи в статье представлен исчерпывающих анализ различных алгоритмов решения задачи one-more-ISIS. Статья “Practical, Round-Optimal Lattice-Based Blind Signatures” (авторы Ш.Аграваль, Е.Киршанова, Д.Штеле, А.Ядав) опубликована в ACM CCS 2022, полная версия статьи доступна https://eprint.iacr.org/2021/1565 вместе с сопутствующими материалами для анализа и получения конкретных параметров https://gitlab.com/ElenaKirshanova/onemoresis_estimates Второй результат в направлении решеток достигнут Новоселовым С.А. в статье “О вычислении группы классов идеалов мнимых мультиквадратичных полей” (опубликована в журнале Прикладная дискретная математика. 2022, полная версия статьи доступна по адресу https://crypto-kantiana.com/semyon.novoselov/publications/mqCLGP.pdf) В статье работе расширены эксперименты предыдущих результатов Биассе-ван Вредендал (OBS, 2019, vol. 2) по вычислению группы классов идеалов с действительных мультиквадратичных полей на мнимые мультиквадратичные поля. Представлены примеры вычисления группы классов для мнимых мультквадратичных полей степени 64 и 128, недостижимые ранее. Исходный код программы доступен по адресу https://github.com/novoselov-sa/multiclass-im По второму направлению проекта – криптоанализу конструкций на кодах – Киршановой Е.А. совместно с А. Майем (Рурский Университет г. Бохум) представлена первая атака типа Partial Key Recovery (реконструкция ключа по частичной информации) на криптосистему МакЭлис. Статья “Decoding McEliece with a Hint - Secret Goppa Key Parts Reveal Everything” опубликована на SCN 2022 и полная версия доступна по адресу https://eprint.iacr.org/2022/525 Полученный результат позволяет эффективно восстановить ключ в криптосистеме, имея всего 25% ключа. По третьему направлению, связанному с АГ-кодами, Малыгина Е.С. и Кунинец А.А. проанализировали параметры АГ-кодов, ассоциированных с минимальной кривой рода 3. В работе “Анализ минимального расстояния АГ-кода, ассоциированного с максимальной кривой рода три” получены критерии, определяющие, когда АГ-коды являются или не являются так называемым MDS-кодами. Результаты работы опубликованы в журнале Прикладная дискретная математика, полная версия доступна по адресу https://crypto-kantiana.com/ekaterina.malygina/papers/Malygina_Kuninetz_pdm.pdf

Аннотация результатов, полученных в 2023 году
По направлению 1 (криптоанализ схем на решетках): 1.1. Совместно с немецкой стороной (проф. А.Май и аспирант Ю.Новаковский) была разработана и реализована практическая атака на криптосистему NTRU. Оригинальная схема NTRU, предложенная в 1996 году, дала толчок современной криптографии на решетках и является прародителем современных версий криптосистем NTRU, таких как NTRU-HRSS и NTRU-HPS – финалисты 3-го раунда конкурса NIST пост-квантовых примитивов. Почти сразу в 1997 году Копперсмит и Шамир предложили атаку на NTRU, в основе которой лежит редукция особой решетки (решетки Копперсмит-Шамира). До сих пор эта атака считалась самой эффективной, и с её помощью были решены самые большие размерности NTRU, представленные в официальном NTRU челлендже от Security Innovations, в частности размерность n=173. В совместной работе с А.Майем и Ю.Новаковским, мы предлагаем новые инструменты для атаки на современные версии задачи NTRU. В частности, мы предлагаем конструкции новых решеток, а также использование более эффективной версии редукции этих новых решеток. Конкретно, пусть n – простое, тогда для циклотомического поля Φn := (X^n − 1)/(X − 1) определим Zq[X]/(Φn) как фактор-кольцо кольца целых Φn. Мы показываем (опровергая сложившееся на сегодня мнение), что строить решетку для этого кольца более выгодно для атаки, нежели решетку Копперсмит-Шамира. В связи с этим, мы расширяем работу Дахман-Солед, Дюки, Гонда и Росс (Crypto 2020), добавляя в неё так называемые “почти-параллельные проекции”, возникающие в наших конструкциях решеток и позволяющие решить задачу NTRU более эффективно. С помощью наших идей, мы получили решения для NTRU-HPS при n ∈ [101, 171] и для NTRU-HRSS при n ∈ [101, 211]. Качественно, наша атака выигрывает по сравнению с предыдущими атаками, так как, например, нам удалось решить NTRU-HPS при n=171 за 83 core-дней, в то время как базис Копперсмит-Шамира потребовал 172 core-дня. Нам также удалось взломать челлендж от Security Innovations для рекордной размерности n=181. Результаты описаны в совместной статье New NTRU Records with Improved Lattice Bases, представленной на PQCrypto 2023 (https://pqcrypto2023.umiacs.io/). Полная версия статьи доступна по адресу https://eprint.iacr.org/2023/582 , реализация атаки находится в открытом доступе https://github.com/ElenaKirshanova/ntru_with_sieving 1.2. Разработан алгоритм для решения задачи вычисления дискретного логарифма в группе классов идеалов мультиквадратичных полей. На основе анализа алгоритма получена новая оценка сложности решения данной задачи для случая, когда неизвестно разложение исходного идеала на простые идеалы. Для данного случая разработанный алгоритм имеет наилучшее асимптотическое время работы среди всех известных алгоритмов. Решение задачи вычисления дискретного логарифма необходимо в алгоритмах нахождения коротких векторов в идеальных решетках мультиквадратичных полей для разложения исходного идеала по образующим группы классов (с малой нормой) и последующего поиска короткого вектора с помощью редукции полученного разложения. Результат описан в работе “On the Discrete Logarithm Problem in the Ideal Class Group of Multiquadratic Fields” представленной на LatinCrypt 2023 (https://www.espe.edu.ec/latincrypt/). Полная версия статьи доступна по адресу: https://link.springer.com/chapter/10.1007/978-3-031-44469-2_10. Реализация алгоритма находится в открытом доступе: https://github.com/novoselov-sa/mqCLDL. По направлению 2 (криптоанализ кодовых криптосистем, в частности МакЭлиса): 2.1. Мы рассматриваем криптосистему МакЭлиса с бинарным кодом Гоппы C ⊂ F_2^n, заданным неприводимым многочленом g(x) ∈F_{2^m}[X] и так называемыми точками Гоппы (α1, . . . , αn) ∈ F_{2^m}^n. Вместе эти данные: многочлен и точки, позволяют эффективно декодировать ошибки в коде Гоппы и составляют секретный ключ в рассматриваемой криптосистеме. Такой код Гоппы C имеет ко-размерность tm, и, как правило, tm ≈n/4. В совместной работе с А. Май мы предлагаем полиномиальный алгоритм, который по заданным g(x) и t(m-2)+1 точкам Гоппы, вычисляет оставшиеся n - (t(m-2)+1) секретных точек Гоппы. Этот результат опубликован в журнале “Information and Computation”, полная версия статьи доступна по адресу https://eprint.iacr.org/2022/525 вместе с исходным кодом атаки https://github.com/ElenaKirshanova/leaky_goppa_in_mceliece 2.2 Представлен полный обзор теоретических основ алгебраических кривых и их функциональных полей, необходимых для построения АГ-кодов, а также пар, исправляющих ошибки, с целью их дальнейшего применения для декодирования кодов. Приведены примеры построения АГ-кодов, ассоциированных с эллиптической кривой, эрмитовой кривой и квартикой Клейна, и явно заданы пары, исправляющие ошибки, для построенных кодов. https://crypto-kantiana.com/ekaterina.malygina/papers/Malygina_2023_.pdf 2.3. Для произвольного АГ-кода и дуального к нему, а также для их подполевых подкодов (в случае квадратичного расширения конечного поля) получены классификации пар, исправляющих ошибки. Также представлена классификация кодов, участвующих в построении пары, относительно MDS-свойства. Результаты этой работы были доложены на конференции SibeCrypt 2023 и представлены в виде тезисов, доступных по адресу: https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=pdma&paperid=629&option_lang=rus По направлению 3 (конструкции решеток из АГ-кодов): Работа Киршановой Е.А. и Малыгиной Е.С. по конструкции-D решеток из АГ-кодов отправлена в журнал Designs, Codes and Cryptography. Статья получила положительные отзывы и планируется в печать в первом квартале 2024 г.