Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the Cryptanalysis of pSIDH

Mingjie Chen; Muhammad Imran; Gábor Ivanyos; Peter Kutas; Antonin Leroux; Christophe Petit

doi:10.1007/978-981-99-8727-6_4

Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the Cryptanalysis of pSIDH

Mingjie Chen, Muhammad Imran, Gábor Ivanyos, Peter Kutas^*, Antonin Leroux, Christophe Petit

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

The Isogeny to Endomorphism Ring Problem (IsERP) asks to compute the endomorphism ring of the codomain of an isogeny between supersingular curves in characteristic p given only a representation for this isogeny, i.e. some data and an algorithm to evaluate this isogeny on any torsion point. This problem plays a central role in isogeny-based cryptography; it underlies the security of pSIDH protocol (ASIACRYPT 2022) and it is at the heart of the recent attacks that broke the SIDH key exchange. Prior to this work, no efficient algorithm was known to solve IsERP for a generic isogeny degree, the hardest case seemingly when the degree is prime.

In this paper, we introduce a new quantum polynomial-time algorithm to solve IsERP for isogenies whose degrees are odd and have many prime factors. As main technical tools, our algorithm uses a quantum algorithm for computing hidden Borel subgroups, a group action on supersingular isogenies from EUROCRYPT 2021, various algorithms for the Deuring correspondence and a new algorithm to lift arbitrary quaternion order elements modulo an odd integer N with many prime factors to powersmooth elements.

As a main consequence for cryptography, we obtain a quantum polynomial-time key recovery attack on pSIDH. The technical tools we use may also be of independent interest.

Original language	English
Title of host publication	Advances in Cryptology – ASIACRYPT 2023
Subtitle of host publication	29th International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, December 4–8, 2023, Proceedings, Part III
Editors	Jian Guo, Ron Steinfeld
Place of Publication	Singapore
Publisher	Springer
Pages	99-130
Number of pages	31
Volume	3
Edition	1
ISBN (Electronic)	9789819987276
ISBN (Print)	9789819987269
DOIs	https://doi.org/10.1007/978-981-99-8727-6_4
Publication status	Published - 18 Dec 2023
Event	29th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2023 - Guangzhou, China Duration: 4 Dec 2023 → 8 Dec 2023

Publication series

Name	Lecture Notes in Computer Science
Volume	14440
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	29th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2023
Abbreviated title	ASIACRYPT 2023
Country/Territory	China
City	Guangzhou
Period	4/12/23 → 8/12/23

Bibliographical note

Acknowledgements
Gábor Ivanyos is supported in part by the Hungarian Ministry of Innovation and Technology NRDI Office within the framework of the Artificial Intelligence National Laboratory Program. Péter Kutas is supported by the Hungarian Ministry of Innovation and Technology NRDI Office within the framework of the Quantum Information National Laboratory Program, the J’anos Bolyai Research Scholarship of the Hungarian Academy of Sciences and by the UNKP-22-5 New National Excellence Program. Mingjie Chen, Péter Kutas and Christophe Petit are partly supported by EPSRC through grant number EP/V011324/1.

Access to Document

10.1007/978-981-99-8727-6_4Licence: None: All rights reserved

Embargoed Document

ChenM2023Hidden
Accepted author manuscript, 533 KB
Licence: Other (please specify with Rights Statement)
Embargo ends: 18/12/24

Post-Quantum Cryptography: a Cryptanalysis Approach
Petit, C.
Engineering & Physical Science Research Council
1/10/21 → 30/09/26
Project: Research Councils

Cite this

Chen, M., Imran, M., Ivanyos, G., Kutas, P., Leroux, A., & Petit, C. (2023). Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the Cryptanalysis of pSIDH. In J. Guo, & R. Steinfeld (Eds.), Advances in Cryptology – ASIACRYPT 2023: 29th International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, December 4–8, 2023, Proceedings, Part III (1 ed., Vol. 3, pp. 99-130). (Lecture Notes in Computer Science; Vol. 14440). Springer. https://doi.org/10.1007/978-981-99-8727-6_4

Chen, Mingjie ; Imran, Muhammad ; Ivanyos, Gábor et al. / Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the Cryptanalysis of pSIDH. Advances in Cryptology – ASIACRYPT 2023: 29th International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, December 4–8, 2023, Proceedings, Part III. editor / Jian Guo ; Ron Steinfeld. Vol. 3 1. ed. Singapore : Springer, 2023. pp. 99-130 (Lecture Notes in Computer Science).

@inproceedings{e48c14b3a5cc4b6f95cbac9e667952e9,

title = "Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the Cryptanalysis of pSIDH",

abstract = "The Isogeny to Endomorphism Ring Problem (IsERP) asks to compute the endomorphism ring of the codomain of an isogeny between supersingular curves in characteristic p given only a representation for this isogeny, i.e. some data and an algorithm to evaluate this isogeny on any torsion point. This problem plays a central role in isogeny-based cryptography; it underlies the security of pSIDH protocol (ASIACRYPT 2022) and it is at the heart of the recent attacks that broke the SIDH key exchange. Prior to this work, no efficient algorithm was known to solve IsERP for a generic isogeny degree, the hardest case seemingly when the degree is prime.In this paper, we introduce a new quantum polynomial-time algorithm to solve IsERP for isogenies whose degrees are odd and have many prime factors. As main technical tools, our algorithm uses a quantum algorithm for computing hidden Borel subgroups, a group action on supersingular isogenies from EUROCRYPT 2021, various algorithms for the Deuring correspondence and a new algorithm to lift arbitrary quaternion order elements modulo an odd integer N with many prime factors to powersmooth elements.As a main consequence for cryptography, we obtain a quantum polynomial-time key recovery attack on pSIDH. The technical tools we use may also be of independent interest.",

author = "Mingjie Chen and Muhammad Imran and G{\'a}bor Ivanyos and Peter Kutas and Antonin Leroux and Christophe Petit",

note = "Acknowledgements G{\'a}bor Ivanyos is supported in part by the Hungarian Ministry of Innovation and Technology NRDI Office within the framework of the Artificial Intelligence National Laboratory Program. P{\'e}ter Kutas is supported by the Hungarian Ministry of Innovation and Technology NRDI Office within the framework of the Quantum Information National Laboratory Program, the J{\textquoteright}anos Bolyai Research Scholarship of the Hungarian Academy of Sciences and by the UNKP-22-5 New National Excellence Program. Mingjie Chen, P{\'e}ter Kutas and Christophe Petit are partly supported by EPSRC through grant number EP/V011324/1.; 29th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2023, ASIACRYPT 2023 ; Conference date: 04-12-2023 Through 08-12-2023",

year = "2023",

month = dec,

day = "18",

doi = "10.1007/978-981-99-8727-6_4",

language = "English",

isbn = "9789819987269",

volume = "3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "99--130",

editor = "Jian Guo and Ron Steinfeld",

booktitle = "Advances in Cryptology – ASIACRYPT 2023",

edition = "1",

}

Chen, M, Imran, M, Ivanyos, G, Kutas, P, Leroux, A & Petit, C 2023, Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the Cryptanalysis of pSIDH. in J Guo & R Steinfeld (eds), Advances in Cryptology – ASIACRYPT 2023: 29th International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, December 4–8, 2023, Proceedings, Part III. 1 edn, vol. 3, Lecture Notes in Computer Science, vol. 14440, Springer, Singapore, pp. 99-130, 29th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2023, Guangzhou, China, 4/12/23. https://doi.org/10.1007/978-981-99-8727-6_4

Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the Cryptanalysis of pSIDH. / Chen, Mingjie; Imran, Muhammad; Ivanyos, Gábor et al.
Advances in Cryptology – ASIACRYPT 2023: 29th International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, December 4–8, 2023, Proceedings, Part III. ed. / Jian Guo; Ron Steinfeld. Vol. 3 1. ed. Singapore: Springer, 2023. p. 99-130 (Lecture Notes in Computer Science; Vol. 14440).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the Cryptanalysis of pSIDH

AU - Chen, Mingjie

AU - Imran, Muhammad

AU - Ivanyos, Gábor

AU - Kutas, Peter

AU - Leroux, Antonin

AU - Petit, Christophe

N1 - Acknowledgements Gábor Ivanyos is supported in part by the Hungarian Ministry of Innovation and Technology NRDI Office within the framework of the Artificial Intelligence National Laboratory Program. Péter Kutas is supported by the Hungarian Ministry of Innovation and Technology NRDI Office within the framework of the Quantum Information National Laboratory Program, the J’anos Bolyai Research Scholarship of the Hungarian Academy of Sciences and by the UNKP-22-5 New National Excellence Program. Mingjie Chen, Péter Kutas and Christophe Petit are partly supported by EPSRC through grant number EP/V011324/1.

PY - 2023/12/18

Y1 - 2023/12/18

N2 - The Isogeny to Endomorphism Ring Problem (IsERP) asks to compute the endomorphism ring of the codomain of an isogeny between supersingular curves in characteristic p given only a representation for this isogeny, i.e. some data and an algorithm to evaluate this isogeny on any torsion point. This problem plays a central role in isogeny-based cryptography; it underlies the security of pSIDH protocol (ASIACRYPT 2022) and it is at the heart of the recent attacks that broke the SIDH key exchange. Prior to this work, no efficient algorithm was known to solve IsERP for a generic isogeny degree, the hardest case seemingly when the degree is prime.In this paper, we introduce a new quantum polynomial-time algorithm to solve IsERP for isogenies whose degrees are odd and have many prime factors. As main technical tools, our algorithm uses a quantum algorithm for computing hidden Borel subgroups, a group action on supersingular isogenies from EUROCRYPT 2021, various algorithms for the Deuring correspondence and a new algorithm to lift arbitrary quaternion order elements modulo an odd integer N with many prime factors to powersmooth elements.As a main consequence for cryptography, we obtain a quantum polynomial-time key recovery attack on pSIDH. The technical tools we use may also be of independent interest.

AB - The Isogeny to Endomorphism Ring Problem (IsERP) asks to compute the endomorphism ring of the codomain of an isogeny between supersingular curves in characteristic p given only a representation for this isogeny, i.e. some data and an algorithm to evaluate this isogeny on any torsion point. This problem plays a central role in isogeny-based cryptography; it underlies the security of pSIDH protocol (ASIACRYPT 2022) and it is at the heart of the recent attacks that broke the SIDH key exchange. Prior to this work, no efficient algorithm was known to solve IsERP for a generic isogeny degree, the hardest case seemingly when the degree is prime.In this paper, we introduce a new quantum polynomial-time algorithm to solve IsERP for isogenies whose degrees are odd and have many prime factors. As main technical tools, our algorithm uses a quantum algorithm for computing hidden Borel subgroups, a group action on supersingular isogenies from EUROCRYPT 2021, various algorithms for the Deuring correspondence and a new algorithm to lift arbitrary quaternion order elements modulo an odd integer N with many prime factors to powersmooth elements.As a main consequence for cryptography, we obtain a quantum polynomial-time key recovery attack on pSIDH. The technical tools we use may also be of independent interest.

UR - https://asiacrypt.iacr.org/2023/files/cfpv3.pdf

UR - https://asiacrypt.iacr.org/2023/

UR - https://link.springer.com/conference/asiacrypt

UR - https://eprint.iacr.org/2023/779

U2 - 10.1007/978-981-99-8727-6_4

DO - 10.1007/978-981-99-8727-6_4

M3 - Conference contribution

SN - 9789819987269

VL - 3

T3 - Lecture Notes in Computer Science

SP - 99

EP - 130

BT - Advances in Cryptology – ASIACRYPT 2023

A2 - Guo, Jian

A2 - Steinfeld, Ron

PB - Springer

CY - Singapore

T2 - 29th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2023

Y2 - 4 December 2023 through 8 December 2023

ER -

Chen M, Imran M, Ivanyos G, Kutas P, Leroux A, Petit C. Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the Cryptanalysis of pSIDH. In Guo J, Steinfeld R, editors, Advances in Cryptology – ASIACRYPT 2023: 29th International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, December 4–8, 2023, Proceedings, Part III. 1 ed. Vol. 3. Singapore: Springer. 2023. p. 99-130. (Lecture Notes in Computer Science). doi: 10.1007/978-981-99-8727-6_4

Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the Cryptanalysis of pSIDH

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Embargoed Document

Fingerprint

Projects

Post-Quantum Cryptography: a Cryptanalysis Approach

Cite this