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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

22 Citaten (Scopus)

Samenvatting

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.

Originele taal-2	Engels
Titel	Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
Redacteuren	Anne Canteaut, Yuval Ishai
Uitgeverij	Springer
Pagina's	523-548
Aantal pagina's	26
ISBN van geprinte versie	9783030457235
DOI's	https://doi.org/10.1007/978-3-030-45724-2_18
Status	Gepubliceerd - 2020
Evenement	39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020 - Zagreb, Kroatië Duur: 10 mei 2020 → 14 mei 2020

Publicatie series

Naam	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12106 LNCS
ISSN van geprinte versie	0302-9743
ISSN van elektronische versie	1611-3349

Congres

Congres	39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020
Land/Regio	Kroatië
Stad	Zagreb
Periode	10/05/20 → 14/05/20

Bibliografische nota

Publisher Copyright:
© International Association for Cryptologic Research 2020.

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

Financiering

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.

Toegang tot document

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

Andere bestanden en links

Link naar publicatie in Scopus

Citeer dit

Castryck, W., Panny, L., & Vercauteren, F. (2020). Rational Isogenies from Irrational Endomorphisms. In A. Canteaut, & Y. Ishai (editors), Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings (blz. 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. redacteur / Anne Canteaut ; Yuval Ishai. Springer, 2020. blz. 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 (reds.), 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, blz. 523-548, 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020, Zagreb, Kroatië, 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. reds. / Anne Canteaut; Yuval Ishai. Springer, 2020. blz. 523-548 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12106 LNCS).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › 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 - https://www.scopus.com/pages/publications/85084805042

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, redacteurs, Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Springer. 2020. blz. 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

Samenvatting

Publicatie series

Congres

Bibliografische nota

Financiering

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit