The information is prepared on the basis of data from the information-analytical system RSF, informative part is represented in the author's edition. All rights belong to the authors, the use or reprinting of materials is permitted only with the prior consent of the authors.

Project titleCryptanalysis of post-quantum lattice- and code-based primitives: practical records and theoretical improvements

Research area 01 - MATHEMATICS, INFORMATICS, AND SYSTEM SCIENCES, 01-102 - Algebra

Keywordspost-quantum cryptography, lattice-based cryptography, code-based cryptography, practical cryptanalysis, quantum speed-ups, lattice sphere packing.

Annotation
The goal of our project is to develop new and expand existing cryptanalytic tools for lattice- and code-based schemes. The main purpose of our research is to clarify hardness of mathematical problems that stay behind lattice- and code-based cryptographic constructions. Deepening our understanding of these problems does not only raise our confidence in lattice- and code-based cryptographic constructions, but also aids practitioners when it comes to real-life applications. It may not take too long until these real-life cryptographic applications will come into our everyday usage. In 2016 The National Institute of Standards and Technology (NIST) launched a call for post-quantum submissions aiming at select- ing encryption schemes and digital signatures that will substitute our currently- deployed cryptographic algorithms that are vulnerable to quantum attacks. Proposals of encryption schemes that are by now survived the selection process are either lattice-based (3 out of 4) or code-based (1 out of 4). For signatures 2 out 3 finalists are lattice-based. That’s said, there is good chance that we shall be relying on either lattice-based, or code-bsed security assumptions, or may be even on both of them. Yet there is a lot of questions needed to be settled before such schemes become ready for deployment, and many of these questions are of cryptanalytic nature. Our project is dedicated to cryptanalysis of post-quantum lattice-based and code-based public-key encryption schemes. The research questions we aim to address are divided into three categories: cryptanalysis of the NTRU cryptosystem, as a prominent example of lattice-based schemes, cryptanalysis of McEliece cryptosystem as the most important example of a code-based public-key encryption scheme, and, third, construction of lattices with a large kissing number. We choose the NTRU cryptosystem as one of the oldest yet, perhaps, least understood from the cryptanalytic point of view lattice-based scheme. The goal of our research is to provide a thorough study of the hardness guarantees offered by the NTRU assumption by 1. improving various combinatorial attacks on NTRU including meet-in-the-middle type of attacks; 2. conducting medium- and largescale experiments on NTRU-specific attacks, establishing for the first time practical relevance of these attacks; 3. establishing quantum speed-ups for the proposed classical improvements. In the direction of McEliece cryptosystem, we unify all the recent improvements on the decoding of random linear codes into an open-source implementation, laying the ground for further practical developments in this area, answering longstanding questions on security guarantees offered by concrete parameters of the cryptosystem, and bringing more understanding into the line of the asymtpotic work conducted over the recent years. We shape our results into the form of a publicly available security estimator for code-based schemes, a tool that a practitioner would need in case McEliece cryptosystem becomes standardized. Our third direction on constructing lattices with large kissing number has implications both in theory and practice. From the theoretical perspective, we aim at settling the question of whether the recent construction of lattices with exponential kissing number is tight in the exponent. This question is not that far form cryptanalysis as it may appear: lattices with large kissing number give raise to good spherical codes, which, in turn, are used inside fast algorithms for the shortest vector problem { the main hammer in cryptanalysis of lattice-based cryptosystems. We investigate the applicability of lattices with large kissing number to cryptanalysis by answering the question of whether these lattices admit fast decoding algorithms.

Expected results
We separate all our work programme and hence our results into three categories: cryptanalysis of lattice-based schemes, practical cryptanalysis of code-based schemes, constructing lattices with large kissing number and developing fast algorithms for these lattices. In the direction of lattice-based schemes we provide theoretical and practical cryptanalytic results ultimately aiming at publicly available security estimator of the NTRU cryptosystem – one of the most prominent lattice-based scheme and a candidate for standardisation. On the theoretical side, we provide a thorough study on combinatorial attacks on NTRU. On the practical side, we conduct medium- and large-scale experiments with attacks on NTRU, bringing practical insights into asymptotic analyses. The main outcomes of this topic are: 1. Publicly available implementation of NTRU attacks; 2. Publicly available NTRU estimator; 3. improved combinatorial attacks on NTRU; 4. quantum speed-ups for the proposed improvements. In the direction of cryptanalysis of code-based constructions, we deal with the lack of progress in practical implementation of numerous asymptotic improvements that have been proposed over the last 40 years. As for lattices, our implementation and large-scale experiments will enable us to develop an accurate estimator that, given concrete parameters of the construction, will output its security level. The main outcomes of this topic are: 1. open-source implementation of all new decoding algorithms, 2. an accurate estimator for security level of concrete parameters of code-based schemes. Taking more theoretical turn, we look at constructions of lattices with exceptional geometric properties – lattices with exponentially large kissing number. Ultimately, a good understanding of the geometry of such lattices, as well as developing efficient algorithms associated to them, will improve our current implementations of attacks on lattice-based scheme, thus bringing us back to our first direction: concrete hardness of lattice-based assumptions. The main outcomes of this topic are: 1. explicit construction of lattices from different algebraic geometry codes; 2. analysed and implemented algorithms for solving the shortest vector and the closes vector problem on lattices with large kissing number.

Annotation of the results obtained in 2022
Being split into three different directions (practical cryptanalysis of lattice-based constructions, cryptanalysis of code-based schemes, and construction of dense lattice from AG-codes), the work on the project has been advanced in all three. On the side of lattices, two main results have been achieved: a practical round-optimal post-quantum blind signature construction and an algorithm for class group computations in imaginary multiquadratic fields. The first result presents a blind signature scheme that enjoys small signature size (the smallest known among post-quantum schemes) as well as efficient algorithms for signing and verification. Its security is based on a new and arguably natural assumption, called the one-more-ISIS assumption. This assumption can be seen as a lattice analogue of the one-more-RSA used in pre-quantum blind signatures. To gain confidence in our assumption, a detailed analysis of diverse attack strategies is provided. The work titled “Practical, Round-Optimal Lattice-Based Blind Signatures” by Shweta Agrawal, Elena Kirshanova, Damien Stehlé and Anshu Yadav is published at ACM CCS 2022, the full version of the paper is available at https://eprint.iacr.org/2021/1565 and the accompanying martial at https://gitlab.com/ElenaKirshanova/onemoresis_estimates The second result on lattices concerns the work of S. Novoselov ''On Ideal Class Group Computation of Imaginary Multiquadratic Fields'' published in Prikladnaya Diskretnaya Matematika (full version of the paper is available at https://crypto-kantiana.com/semyon.novoselov/publications/mqCLGP.pdf ). This work extends previous results of Biasse-van Vredendaal of the class group computation from real to imaginary multiquadratic fields. Examples of class group computation of the imaginary multiquadratic fields of degree 64 and 128 are provided. The source code is available at https://github.com/novoselov-sa/multiclass-im In the direction of cryptanalysis of code-based constructions, in their joint work E.Kirshanova and A.May gave the first partial key recovery attack on McEliece cryptosystem. The article “Decoding McEliece with a Hint - Secret Goppa Key Parts Reveal Everything” was published at SCN 2022 and is available at https://eprint.iacr.org/2022/525 They achieve a polynomial time full key recovery algorithm provided ~25% of the secret key is leaked. In the direction of AG-codes, A.Malygina together with A.Kuninets published the article titled “Analysis Of Minimal Distance of AG-code Associated with Maximal Curve of Genus Three” (Prikladnaya Diskretnaya Matematika, full version of the paper is available at https://crypto-kantiana.com/ekaterina.malygina/papers/Malygina_Kuninetz_pdm.pdf). The work considers a class of algebraic geometry codes associated with a maximal curve of genus three whose number of rational points satisfies the upper Hasse-Weil-Serre bound. The main result categorizes rational points into 4 categories and shows for which types of points, the divisor of the functional field is principal. For special cases it allows to show whether the corresponding AG-code is MDS or not.

Publications

1. Agrawal S., Kirshanova E., Stehlé D., Yadav A. Practical, Round-Optimal Lattice-Based Blind Signatures Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, стр. 39–53 (year - 2022) https://doi.org/10.1145/3548606.3560650

2. Kirshanova E., May A. 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 (year - 2022) https://doi.org/10.1007/978-3-031-14791-3_1

3. Kuninets A.A., Malygina E.S. Анализ минимального расстояния АГ-кода, ассоциированного с максимальной кривой рода три Прикладная дискретная математика, № 58, С. 5-14 (year - 2022) https://doi.org/10.17223/20710410/X/1

4. Novoselov S.A. О вычислении группы классов идеалов мнимых мультиквадратичных полей Прикладная дискретная математика, № 58. С. 26-30 (year - 2022) https://doi.org/10.17223/20710410/58/3

Annotation of the results obtained in 2023
Research direction 1 (cryptanalysis of lattice-based schemes) 1.1. The original NTRU cryptosystem from 1996 can be considered the starting point of the great success story of lattice-based cryptography. Modern NTRU versions like NTRU-HPS and NTRU-HRSS are round-3 finalists in NIST's selection process and many other efficient constructions (not only KEMs) rely on NTRU-like assumptions. Back to 1997 Coppersmith and Shamir proposed to attack NTRU via lattice basis reduction, and variations of the Coppersmith-Shamir lattice have been successfully applied to solve official NTRU challenges by Security Innovations, Inc. up to dimension n=173. In joint work with A.May and J.Nowakowski, we provide the tools to attack modern NTRU versions, both by the design of a proper lattice basis, as well as by tuning the modern BKZ with lattice sieving algorithm from the G6K library to NTRU needs. Let n be prime, Φn := (X^n − 1)/(X − 1), and let Zq[X]/(Φn) be the cyclotomic ring. As opposed to the common belief, we show that switching from the Coppersmith-Shamir lattice to a basis for the cyclotomic ring brings benefits. To this end, we slightly enhance the LWE with Hints framework by Dachman-Soled, Ducas, Gong, Ross (Crypto 2020) with the concept of projections against almost-parallel hints. Using our new lattice bases, we set the first cryptanalysis landmarks for NTRU-HPS with n ∈ [101, 171] and for NTRU-HRSS with n ∈ [101, 211]. As a numerical example, we break our largest HPS-171 instance using the cyclotomic ring basis within 83 core days, whereas the Coppersmith-Shamir basis requires 172 core days. We also break one more official NTRU challenges by Security Innovation, Inc., originally worth 1000$, in dimension n = 181 in 20 core years. Our experiments run up to BKZ blocksizes beyond 100, a regime that has not been reached in analyzing cryptosystems so far. The results were presented at PQCrypto 2023 and published in Lecture Notes in Computer Science (series PQCrypto 2023: Post-Quantum Cryptography). The source code of the attack is available at https://github.com/ElenaKirshanova/ntru_with_sieving 1.2. An algorithm for solving discrete logarithm problem was proposed by S. Novoselov in the work “On the Discrete Logarithm Problem in the Ideal Class Group of Multiquadratic Fields”. The new complexity bound was obtained for the case when we do not know the factorization of the target ideal. For this case the algorithm has the best known runtime complexity. The algorithm for the discrete logarithm computation is an essential tool for finding short vectors in multiquadratic ideal lattices. It is used for decomposing a target ideal into a product of class group generators with small norms and finding small vectors using a reduction of this decomposition. The result was presented at the conference LatinCrypt 2023 (full version of the paper is available at https://link.springer.com/chapter/10.1007/978-3-031-44469-2_10). The source code is available at https://github.com/novoselov-sa/mqCLDL. Research direction 2 (cryptanalysis of code-based schemes): 2.1. We consider the McEliece cryptosystem with a binary Goppa code C ⊂ F_2^n specified by an irreducible Goppa polynomial g(x) ∈F_{2^m}[X] and Goppa points (α1, . . . , αn) ∈ F_{2^m}^n. Since g(x) together with the Goppa points allow for efficient decoding, these parameters form McEliece secret keys. Such a Goppa code C is an (n − tm)-dimensional subspace of F_2^n and therefore C has co-dimension tm. For typical McEliece instantiations we have tm ≈n/4. In joint work with A.May we provide a polynomial-time algorithm that, given g(x) and only t(m-2)+1 Goppa points, one can recover with certainty the remaining Goppa points. The result is published in the journal “Information and Computation”, the online version of the paper is available at https://eprint.iacr.org/2022/525 , together with the source code https://github.com/ElenaKirshanova/leaky_goppa_in_mceliece 2.2. A complete review of the theoretical foundations of algebraic curves and their functional fields necessary for constructing AG-codes, as well as pairs correcting errors, with a view to their further application for decoding codes, is presented. Examples of constructing AG codes associated with an elliptic curve, a Hermitian curve, and a Klein apartment are given, and error-correcting pairs are explicitly specified for the constructed codes. https://crypto-kantiana.com/ekaterina.malygina/papers/Malygina_2023_.pdf 2.3. For an arbitrary AG-code and its dual, as well as for their subfield subcodes (in the case of a quadratic extension of a finite field), classifications of pairs correcting errors were obtained. The classification of the codes involved in the construction of the pair with respect to the MDS property was also presented. The results of this work were presented at the SibeCrypt 2023: https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=pdma&paperid=629&option_lang=rus Research direction 3 (construction of lattices from codes) Joint work of Kirshanova and Malygina on Construction-D lattice from AG-codes has been sent to the journal Designs, Codes and Cryptography and received positive review. The article is expected to be published in the first quartile of 2024.

Publications

1. E. Kirshanova, A. May, J. Nowakowski New NTRU Records with Improved Lattice Bases Lecture Notes in Computer Science, LNCS, PQCrypto 2023: Post-Quantum Cryptography. pp. 167–195, volume 14154 (year - 2023) https://doi.org/10.1007/978-3-031-40003-2_7

2. Kirshanova E., May A. Breaking Goppa-Based McEliece with Hints Information and Computation, Volume 293, pages 105045 (year - 2023) https://doi.org/10.1016/j.ic.2023.105045

3. Malygina E.S., Kuninets A.A., Ratochka V.L., Duplenko A.G., Neiman D.Y. Алгеброгеометрические коды и их декодирование на основе пар, исправляющих ошибки Издательский Дом ТГУ, Прикладная дискретная математика., Прикладная дискретная математика, 2023, № 62, страницы 83–105 DOI 10.17223/20710410/62/7 (year - 2023) https://doi.org/10.17223/20710410/62/7

4. Novoselov S.A. 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 (year - 2023) https://doi.org/10.1007/978-3-031-44469-2_10

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