Geodesic
Post-quantum cryptosystems: open problems and current solutions. Isogeny-based and code-based cryptosystems
Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 1, pp. 52-84 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

This paper is a survey of modern post-quantum cryptographic schemes based on codes and isogenies. Special attention is paid to cryptanalysis of these schemes. In particular, for code-based cryptosystems we describe the information set decoding and the support splitting algorithm as main attacks, and for cryptosystems based on isogenies we describe in detail the Castryck — Decru attack on SIDH/SIKE. Tab. 2, bibliogr. 43.
Keywords: post-quantum cryptography, error-correcting code, elliptic curve, isogeny. 
@article{DA_2024_31_1_a3,
     author = {E. S. Malygina and A. V. Kutsenko and S. A. Novoselov and N. S. Kolesnikov and A. O. Bakharev and I. S. Khilchuk and A. S. Shaporenko and N. N. Tokareva},
     title = {Post-quantum cryptosystems: open~problems~and~current solutions. {Isogeny-based~and~code-based~cryptosystems}},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {52--84},
     year = {2024},
     volume = {31},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2024_31_1_a3/}
}
TY  - JOUR
AU  - E. S. Malygina
AU  - A. V. Kutsenko
AU  - S. A. Novoselov
AU  - N. S. Kolesnikov
AU  - A. O. Bakharev
AU  - I. S. Khilchuk
AU  - A. S. Shaporenko
AU  - N. N. Tokareva
TI  - Post-quantum cryptosystems: open problems and current solutions. Isogeny-based and code-based cryptosystems
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2024
SP  - 52
EP  - 84
VL  - 31
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DA_2024_31_1_a3/
LA  - ru
ID  - DA_2024_31_1_a3
ER  - 
%0 Journal Article
%A E. S. Malygina
%A A. V. Kutsenko
%A S. A. Novoselov
%A N. S. Kolesnikov
%A A. O. Bakharev
%A I. S. Khilchuk
%A A. S. Shaporenko
%A N. N. Tokareva
%T Post-quantum cryptosystems: open problems and current solutions. Isogeny-based and code-based cryptosystems
%J Diskretnyj analiz i issledovanie operacij
%D 2024
%P 52-84
%V 31
%N 1
%U http://geodesic.mathdoc.fr/item/DA_2024_31_1_a3/
%G ru
%F DA_2024_31_1_a3
E. S. Malygina; A. V. Kutsenko; S. A. Novoselov; N. S. Kolesnikov; A. O. Bakharev; I. S. Khilchuk; A. S. Shaporenko; N. N. Tokareva. Post-quantum cryptosystems: open problems and current solutions. Isogeny-based and code-based cryptosystems. Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 1, pp. 52-84. http://geodesic.mathdoc.fr/item/DA_2024_31_1_a3/

[1] E. S. Malygina, N. N. Tokareva, A. V. Kutsenko et al., “Post-quantum cryptosystems: Open questions and solutions. Lattice-based cryptosystems”, J. Appl. Ind. Math., 17:4 (2023), 767–790 | DOI | MR

[2] Courtois N. T., Finiasz M., Sendrier N., “How to achieve a McEliece-based digital signature scheme”, Advances in cryptology — ASIACRYPT'01, Proc. Int. Conf. Theory and Application of Cryptology (Gold Coast, Australia, Dec. 9–13, 2001), Lect. Notes Comput. Sci., 2248, Springer, Heidelberg, 2001, 157–174 | DOI | MR | Zbl

[3] Stern J., “A new paradigm for public key identification”, IEEE Trans. Inf. Theory, 42:6 (1996), 1757–1768 | DOI | MR | Zbl

[4] Childs A., Jao D., Soukharev V., “Constructing elliptic curve isogenies in quantum subexponential time”, J. Math. Cryptology, 8:1 (2014), 1–29 | DOI | MR | Zbl

[5] McEliece R. J., “A public-key cryptosystem based on algebraic coding theory”, The deep space network, California Inst. Technol., Pasadena, CA, 1978, 42-44, 114–116

[6] Niederreiter H., “Knapsack-type cryptosystems and algebraic coding theory”, J. Prob. Contr. Inform. Theory, 15:2 (1986), 159–166 | MR | Zbl

[7] Niederreiter H., Xing C., Algebraic geometry in coding theory and cryptography, Princeton Univ. Press, Princeton, NJ, 2009, 272 pp. | MR | Zbl

[8] Minder L., Shokrollahi A., “Cryptanalysis of the Sidelnikov cryptosystem”, Advances in cryptology — EUROCRYPT'07, Proc. Int. Conf. Theory and Applications of Cryptographic Techniques (Barcelona, Spain, May 20–24, 2007), Lect. Notes Comput. Sci., 4515, Springer, Heidelberg, 2007, 347–360 | DOI | MR | Zbl

[9] Berlekamp E., McEliece R. J., van Tilborg H., “On the inherent intractability of certain coding problems”, IEEE Trans. Inf. Theory, 24:3 (1978), 384–386 | DOI | MR | Zbl

[10] Lee P. J., Brickell E. F., “An observation on the security of McEliece's public-key cryptosystem”, Advances in cryptology — EUROCRYPT'88, Proc. Workshop Theory and Application of Cryptographic Techniques (Davos, Switzerland, May 25–27, 1988), Lect. Notes Comput. Sci., 330, Springer, Heidelberg, 1988, 275–280 | DOI | MR

[11] Petrank E., Roth R., Is code equivalence easy to decide?, IEEE Trans. Inf. Theory, 43:5 (1997), 1602–1604 | DOI | MR | Zbl

[12] Sendrier N., “Finding the permutation between equivalent linear codes: The support splitting algorithm”, IEEE Trans. Inf. Theory, 46:4 (2000), 1193–1203 | DOI | MR | Zbl

[13] Misoczki R., Tillich J.-P., Sendrier N., Barreto P., “MDPC-McEliece: New McEliece variants from moderate density parity-check codes”, Proc. IEEE Int. Symp. Information Theory (Istanbul, Turkey, Jul. 7–12, 2013), IEEE Comput. Soc., Los Alamitos, CA, 2013, 2069–2073 | DOI

[14] Drucker N., Gueron S., Kostic D., “QC-MDPC decoders with several shades of gray”, Post-quantum cryptography. Proc. Int. Conf. (Paris, France, Apr. 15–17, 2020), Lect. Notes Comput. Sci., 12100, Springer, Cham, 2020, 35–50 | DOI | MR | Zbl

[15] Torres R. C., Sendrier N., “Analysis of information set decoding for a sublinear error weight”, Post-quantum cryptography, Proc. Int. Conf. (Fukuoka, Japan, Feb. 24–26, 2016), Lect. Notes Comput. Sci., 9606, Springer, Cham, 2016, 144–161 | DOI | MR | Zbl

[16] Fujisaki E., Okamoto T., “Secure integration of asymmetric and symmetric encryption schemes”, J. Cryptology, 26 (2013), 80–101 | DOI | MR | Zbl

[17] Bindel N., Hamburg M., Hövelmanns K., Hülsing A., Persichetti E., “Tighter proofs of CCA security in the quantum random oracle model”, Theory of cryptography, Proc. Int. Conf. (Nuremberg, Germany, Dec. 1–5, 2019), Lect. Notes Comput. Sci., 11892, Springer, Cham, 2019, 61–90 | DOI | MR | Zbl

[18] Aguilar-Melchor C., Blazy O., Deneuville J.-C., Gaborit P., Zémor G., “Efficient encryption from random quasi-cyclic codes”, IEEE Trans. Inf. Theory, 64:5 (2018), 3927–3943 | DOI | MR | Zbl

[19] Aragon N., Gaborit P., Zémor G., HQC-RMRS, an instantiation of the HQC encryption framework with a more efficient auxiliary error-correcting code, Cornell Univ., Ithaca, NY, 2005, arXiv: 2005.10741

[20] Doche C., Lange T., “Arithmetic of elliptic curves”, Handbook of elliptic and hyperelliptic curve cryptography, Chapman Hall/CRC Press, Boca Raton, FL, 2006, 267–302 | MR

[21] A. A. Bolotov, S. B. Gashkov, A. B. Frolov, and A. A. Chasovskikh, An Elementary Introduction to Ellipic Cryptography: Algebraic and Algorithmic Basics, KomKniga, M., 2006 (Russian)

[22] Sutherland A., Ellipic curves. Isogenies. Lecture notes, MIT, Cambridge, MA, 2022 (accessed Dec. 22, 2023) math.mit.edu/classes/18.783/2022/LectureNotes4.pdf

[23] Vélu J., “Isogénies entre courbes elliptiques”, C. R. Acad. Sci. Paris. Sér. A, 273 (1971), 238–241 | MR | Zbl

[24] Duquesne S., Lange T., “Arithmetic of hyperelliptic curves”, Handbook of elliptic and hyperelliptic curve cryptography, Chapman Hall/CRC Press, Boca Raton, FL, 2006, 303–353 | MR

[25] Kani E., “The number of curves of genus two with elliptic differentials”, J. Reine Angew. Math., 485 (1997), 93–122 | MR

[26] Flynn E. V., Ti Y. B., “Genus two isogeny cryptography”, Post-quantum cryptography, Proc. Int. Conf. (Chongquin, China, May 10–12, 2019), Lect. Notes Comput. Sci., 11505, Springer, Cham, 2019, 286–306 | DOI | MR | Zbl

[27] Castryck W., Decru T., Smith B., “Hash functions from superspecial genus-2 curves using Richelot isogenies”, J. Math. Cryptology, 14:1 (2020), 268–292 | DOI | MR | Zbl

[28] Alamati N., de Feo L., Montgomery H., Patranabis S., Cryptographic group actions and applications, Cryptology ePrint Archive, Paper ID 2020/1188, , Univ. California, San Diego, 2020 (accessed Dec. 22, 2023) eprint.iacr.org/2020/1188.pdf | MR

[29] De Feo L., Jao D., Plût J., Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, Cryptology ePrint Archive, Paper ID 2011/506, , Univ. California, San Diego, 2011 (accessed Dec. 22, 2023) eprint.iacr.org/2011/506.pdf | MR

[30] Castryck W., Decru T., An efficient key recovery attack on SIDH, Cryptology ePrint Archive, Paper ID 2022/975, , Univ. California, San Diego, 2022 (accessed Dec. 22, 2023) eprint.iacr.org/2022/975.pdf

[31] Castryck W., Lange T., Martindale C., Panny L., Renes J., CSIDH: An efficient post-quantum commutative group action, Cryptology ePrint Archive, Paper ID 2018/383, , Univ. California, San Diego, 2018 (accessed Dec. 22, 2023) eprint.iacr.org/2018/383.pdf

[32] Chi-Domínguez J.-J., Rodríguez-Henríquez F., “Optimal strategies for CSIDH”, J. Adv. Math. Commun., 16:2 (2022), 383–411 | DOI | MR | Zbl

[33] Cohen H., A course in computational algebraic number theory, Springer, Berlin, 1993, 536 pp. | MR | Zbl

[34] Maino L., Martindale C., An attack on SIDH with arbitrary starting curve, Cryptology ePrint Archive, Paper ID 2022/1026, , 2022 (accessed Dec. 22, 2023) eprint.iacr.org/2022/1026.pdf

[35] Robert D., Breaking SIDH in polynomial time, Cryptology ePrint Archive, Paper ID 2022/1038, , Univ. California, San Diego, 2022 (accessed Dec. 22, 2023) eprint.iacr.org/2022/1038.pdf

[36] Howe E. W., Leprevost F., Poonen B., “Large torsion subgroups of split Jacobians of curves of genus two or three”, J. Forum Math., 12:3 (2000), 315–364 | MR | Zbl

[37] Bruin N., Flynn E. V., Testa D., “Descent via $(3,3)$-isogeny on Jacobians of genus 2 curves”, J. Acta Arithmetica, 165:3 (2014), 201–223 | DOI | MR | Zbl

[38] Cosset R., Robert D., “Computing $(\ell,\ell)$-isogenies in polynomial time on Jacobians of genus 2 curves”, Math. Comput., 84:294 (2015), 1953–1975 | DOI | MR | Zbl

[39] Milio E., “Computing isogenies between Jacobians of curves of genus 2 and 3”, Math. Comput., 89:323 (2020), 1331–1364 | DOI | MR | Zbl

[40] De Feo L., Dobson S., Galbraith S. D., Zobernig L., SIDH proof of knowledge, Cryptology ePrint Archive, Paper ID 2021/1023, , Univ. California, San Diego, 2021 (accessed Dec. 22, 2023) eprint.iacr.org/2021/1023.pdf | MR

[41] De Feo L., Kieffer J., Smith B., “Towards practical key exchange from ordinary isogeny graphs”, Advances in cryptology — ASIACRYPT'18, Proc. Int. Conf. Theory and Application of Cryptology (Brisbane, Australia, Dec. 2–6, 2018), Lect. Notes Comput. Sci., 11274, Springer, Cham, 2018, 365–394 | DOI | MR | Zbl

[42] Dartois P., de Feo L., “On the security of OSIDH”, Public-key cryptography — PKC 2022, Proc. 25th IACR Int. Conf. Practice and Theory of Public-Key Cryptography (Yokohama, Japan, Mar. 8–11, 2022), v. I, Lect. Notes Comput. Sci., 13177, Springer, Cham, 2022, 52–81 | DOI | MR | Zbl

[43] Colò L., Kohel D., “Orienting supersingular isogeny graphs”, J. Math. Cryptology, 14:1 (2020), 414–437 | DOI | MR | Zbl