Rational Isogenies from Irrational Endomorphisms

Wouter Castryck; Lorenz Panny; Frederik Vercauteren

doi:10.1007/978-3-030-45724-2_18

Rational Isogenies from Irrational Endomorphisms

Wouter Castryck, Lorenz Panny, Frederik Vercauteren

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

18 Citations (SciVal)

Abstract

In this paper, we introduce a polynomial-time algorithm to compute a connecting O-ideal between two supersingular elliptic curves over F_p with common F_p-endomorphism ring O, given a description of their full endomorphism rings. This algorithm provides a reduction of the security of the CSIDH cryptosystem to the problem of computing endomorphism rings of supersingular elliptic curves. A similar reduction for SIDH appeared at Asiacrypt 2016, but relies on totally different techniques. Furthermore, we also show that any supersingular elliptic curve constructed using the complex-multiplication method can be located precisely in the supersingular isogeny graph by explicitly deriving a path to a known base curve. This result prohibits the use of such curves as a building block for a hash function into the supersingular isogeny graph.

Original language	English
Title of host publication	Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
Editors	Anne Canteaut, Yuval Ishai
Publisher	Springer
Pages	523-548
Number of pages	26
ISBN (Print)	9783030457235
DOIs	https://doi.org/10.1007/978-3-030-45724-2_18
Publication status	Published - 2020
Event	39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020 - Zagreb, Croatia Duration: 10 May 2020 → 14 May 2020

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12106 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020
Country/Territory	Croatia
City	Zagreb
Period	10/05/20 → 14/05/20

Bibliographical note

Funding Information:
Author list in alphabetical order; see https://www.ams.org/profession/leaders/ culture/CultureStatement04.pdf. This work was supported in part by the Commission of the European Communities through the Horizon 2020 program under project number 643161 (ECRYPT-NET) and by the Research Council KU Leuven grants C14/18/067 and STG/17/019, and by CyberSecurity Research Flanders with reference number VR20192203. The first listed author was affiliated with the Department of Mathematics at KU Leuven during part of the preparation of this paper.

Publisher Copyright:
© International Association for Cryptologic Research 2020.

Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

Funding

Author list in alphabetical order; see https://www.ams.org/profession/leaders/ culture/CultureStatement04.pdf. This work was supported in part by the Commission of the European Communities through the Horizon 2020 program under project number 643161 (ECRYPT-NET) and by the Research Council KU Leuven grants C14/18/067 and STG/17/019, and by CyberSecurity Research Flanders with reference number VR20192203. The first listed author was affiliated with the Department of Mathematics at KU Leuven during part of the preparation of this paper. Date of this document: 2020-02-20.

Keywords

CSIDH
Endomorphism rings
Isogeny-based cryptography

Access to Document

10.1007/978-3-030-45724-2_18

Cite this

Castryck, W., Panny, L., & Vercauteren, F. (2020). Rational Isogenies from Irrational Endomorphisms. In A. Canteaut, & Y. Ishai (Eds.), Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings (pp. 523-548). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12106 LNCS). Springer. https://doi.org/10.1007/978-3-030-45724-2_18

Castryck, Wouter ; Panny, Lorenz ; Vercauteren, Frederik. / Rational Isogenies from Irrational Endomorphisms. Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. editor / Anne Canteaut ; Yuval Ishai. Springer, 2020. pp. 523-548 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d7453aa3dffc46acb4f5ff12ad5d1c2d,

title = "Rational Isogenies from Irrational Endomorphisms",

abstract = "In this paper, we introduce a polynomial-time algorithm to compute a connecting O-ideal between two supersingular elliptic curves over Fp with common Fp-endomorphism ring O, given a description of their full endomorphism rings. This algorithm provides a reduction of the security of the CSIDH cryptosystem to the problem of computing endomorphism rings of supersingular elliptic curves. A similar reduction for SIDH appeared at Asiacrypt 2016, but relies on totally different techniques. Furthermore, we also show that any supersingular elliptic curve constructed using the complex-multiplication method can be located precisely in the supersingular isogeny graph by explicitly deriving a path to a known base curve. This result prohibits the use of such curves as a building block for a hash function into the supersingular isogeny graph.",

keywords = "CSIDH, Endomorphism rings, Isogeny-based cryptography",

author = "Wouter Castryck and Lorenz Panny and Frederik Vercauteren",

note = "Funding Information: Author list in alphabetical order; see https://www.ams.org/profession/leaders/ culture/CultureStatement04.pdf. This work was supported in part by the Commission of the European Communities through the Horizon 2020 program under project number 643161 (ECRYPT-NET) and by the Research Council KU Leuven grants C14/18/067 and STG/17/019, and by CyberSecurity Research Flanders with reference number VR20192203. The first listed author was affiliated with the Department of Mathematics at KU Leuven during part of the preparation of this paper. Publisher Copyright: {\textcopyright} International Association for Cryptologic Research 2020. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020 ; Conference date: 10-05-2020 Through 14-05-2020",

year = "2020",

doi = "10.1007/978-3-030-45724-2_18",

language = "English",

isbn = "9783030457235",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "523--548",

editor = "Anne Canteaut and Yuval Ishai",

booktitle = "Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings",

address = "Germany",

}

Castryck, W, Panny, L & Vercauteren, F 2020, Rational Isogenies from Irrational Endomorphisms. in A Canteaut & Y Ishai (eds), Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12106 LNCS, Springer, pp. 523-548, 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020, Zagreb, Croatia, 10/05/20. https://doi.org/10.1007/978-3-030-45724-2_18

Rational Isogenies from Irrational Endomorphisms. / Castryck, Wouter; Panny, Lorenz; Vercauteren, Frederik.
Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. ed. / Anne Canteaut; Yuval Ishai. Springer, 2020. p. 523-548 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12106 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Rational Isogenies from Irrational Endomorphisms

AU - Castryck, Wouter

AU - Panny, Lorenz

AU - Vercauteren, Frederik

N1 - Funding Information: Author list in alphabetical order; see https://www.ams.org/profession/leaders/ culture/CultureStatement04.pdf. This work was supported in part by the Commission of the European Communities through the Horizon 2020 program under project number 643161 (ECRYPT-NET) and by the Research Council KU Leuven grants C14/18/067 and STG/17/019, and by CyberSecurity Research Flanders with reference number VR20192203. The first listed author was affiliated with the Department of Mathematics at KU Leuven during part of the preparation of this paper. Publisher Copyright: © International Association for Cryptologic Research 2020. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020

Y1 - 2020

N2 - In this paper, we introduce a polynomial-time algorithm to compute a connecting O-ideal between two supersingular elliptic curves over Fp with common Fp-endomorphism ring O, given a description of their full endomorphism rings. This algorithm provides a reduction of the security of the CSIDH cryptosystem to the problem of computing endomorphism rings of supersingular elliptic curves. A similar reduction for SIDH appeared at Asiacrypt 2016, but relies on totally different techniques. Furthermore, we also show that any supersingular elliptic curve constructed using the complex-multiplication method can be located precisely in the supersingular isogeny graph by explicitly deriving a path to a known base curve. This result prohibits the use of such curves as a building block for a hash function into the supersingular isogeny graph.

AB - In this paper, we introduce a polynomial-time algorithm to compute a connecting O-ideal between two supersingular elliptic curves over Fp with common Fp-endomorphism ring O, given a description of their full endomorphism rings. This algorithm provides a reduction of the security of the CSIDH cryptosystem to the problem of computing endomorphism rings of supersingular elliptic curves. A similar reduction for SIDH appeared at Asiacrypt 2016, but relies on totally different techniques. Furthermore, we also show that any supersingular elliptic curve constructed using the complex-multiplication method can be located precisely in the supersingular isogeny graph by explicitly deriving a path to a known base curve. This result prohibits the use of such curves as a building block for a hash function into the supersingular isogeny graph.

KW - CSIDH

KW - Endomorphism rings

KW - Isogeny-based cryptography

UR - http://www.scopus.com/inward/record.url?scp=85084805042&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-45724-2_18

DO - 10.1007/978-3-030-45724-2_18

M3 - Conference contribution

AN - SCOPUS:85084805042

SN - 9783030457235

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 523

EP - 548

BT - Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings

A2 - Canteaut, Anne

A2 - Ishai, Yuval

PB - Springer

T2 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020

Y2 - 10 May 2020 through 14 May 2020

ER -

Castryck W, Panny L, Vercauteren F. Rational Isogenies from Irrational Endomorphisms. In Canteaut A, Ishai Y, editors, Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Springer. 2020. p. 523-548. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-45724-2_18

Rational Isogenies from Irrational Endomorphisms

Abstract

Publication series

Conference

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this