A Direct Key Recovery Attack on SIDH

Luciano Maino; Chloe Martindale; Lorenz Panny; Giacomo Pope; Benjamin Wesolowski

doi:10.1007/978-3-031-30589-4_16

A Direct Key Recovery Attack on SIDH

Luciano Maino^*, Chloe Martindale, Lorenz Panny, Giacomo Pope, Benjamin Wesolowski

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

48 Citations (Scopus)

Abstract

We present an attack on SIDH utilising isogenies between polarized products of two supersingular elliptic curves. In the case of arbitrary starting curve, our attack (discovered independently from [8]) has subexponential complexity, thus significantly reducing the security of SIDH and SIKE. When the endomorphism ring of the starting curve is known, our attack (here derived from [8]) has polynomial-time complexity assuming the generalised Riemann hypothesis. Our attack applies to any isogeny-based cryptosystem that publishes the images of points under the secret isogeny, for example Séta [13] and B-SIDH [11]. It does not apply to CSIDH [9], CSI-FiSh [3], or SQISign [14].

Original language	English
Title of host publication	Advances in Cryptology – EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
Subtitle of host publication	Advances in Cryptology
Editors	Carmit Hazay, Martijn Stam
Publisher	Springer, Cham
Pages	448-471
Number of pages	24
ISBN (Electronic)	9783031305894
ISBN (Print)	9783031305887
DOIs	https://doi.org/10.1007/978-3-031-30589-4_16
Publication status	Published - 16 Apr 2023
Event	Eurocrypt 2023 - Lyon, France Duration: 23 Apr 2023 → 27 Apr 2023 https://eurocrypt.iacr.org/2023/

Publication series

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

Conference

Conference	Eurocrypt 2023
Country/Territory	France
City	Lyon
Period	23/04/23 → 27/04/23
Internet address	https://eurocrypt.iacr.org/2023/

Bibliographical note

Publisher Copyright:
© 2023, International Association for Cryptologic Research.

Access to Document

10.1007/978-3-031-30589-4_16Licence: Unspecified

Handle.net

Persistent link

Cite this

Maino, L., Martindale, C., Panny, L., Pope, G., & Wesolowski, B. (2023). A Direct Key Recovery Attack on SIDH. In C. Hazay, & M. Stam (Eds.), Advances in Cryptology – EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings: Advances in Cryptology (pp. 448-471). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14008 LNCS). Springer, Cham. https://doi.org/10.1007/978-3-031-30589-4_16

Maino, Luciano ; Martindale, Chloe ; Panny, Lorenz et al. / A Direct Key Recovery Attack on SIDH. Advances in Cryptology – EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings: Advances in Cryptology. editor / Carmit Hazay ; Martijn Stam. Springer, Cham, 2023. pp. 448-471 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ad5555bf1b9f4c3a91edef79906dbcd7,

title = "A Direct Key Recovery Attack on SIDH",

abstract = "We present an attack on SIDH utilising isogenies between polarized products of two supersingular elliptic curves. In the case of arbitrary starting curve, our attack (discovered independently from [8]) has subexponential complexity, thus significantly reducing the security of SIDH and SIKE. When the endomorphism ring of the starting curve is known, our attack (here derived from [8]) has polynomial-time complexity assuming the generalised Riemann hypothesis. Our attack applies to any isogeny-based cryptosystem that publishes the images of points under the secret isogeny, for example S{\'e}ta [13] and B-SIDH [11]. It does not apply to CSIDH [9], CSI-FiSh [3], or SQISign [14].",

author = "Luciano Maino and Chloe Martindale and Lorenz Panny and Giacomo Pope and Benjamin Wesolowski",

note = "Publisher Copyright: {\textcopyright} 2023, International Association for Cryptologic Research.; Eurocrypt 2023 ; Conference date: 23-04-2023 Through 27-04-2023",

year = "2023",

month = apr,

day = "16",

doi = "10.1007/978-3-031-30589-4_16",

language = "English",

isbn = "9783031305887",

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

publisher = "Springer, Cham",

pages = "448--471",

editor = "Carmit Hazay and Martijn Stam",

booktitle = "Advances in Cryptology – EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings",

address = "Switzerland",

url = "https://eurocrypt.iacr.org/2023/",

}

Maino, L , Martindale, C, Panny, L, Pope, G & Wesolowski, B 2023, A Direct Key Recovery Attack on SIDH. in C Hazay & M Stam (eds), Advances in Cryptology – EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings: Advances in Cryptology. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14008 LNCS, Springer, Cham, pp. 448-471, Eurocrypt 2023, Lyon, France, 23/04/23. https://doi.org/10.1007/978-3-031-30589-4_16

A Direct Key Recovery Attack on SIDH. / Maino, Luciano ; Martindale, Chloe; Panny, Lorenz et al.
Advances in Cryptology – EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings: Advances in Cryptology. ed. / Carmit Hazay; Martijn Stam. Springer, Cham, 2023. p. 448-471 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14008 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

TY - GEN

T1 - A Direct Key Recovery Attack on SIDH

AU - Maino, Luciano

AU - Martindale, Chloe

AU - Panny, Lorenz

AU - Pope, Giacomo

AU - Wesolowski, Benjamin

PY - 2023/4/16

Y1 - 2023/4/16

N2 - We present an attack on SIDH utilising isogenies between polarized products of two supersingular elliptic curves. In the case of arbitrary starting curve, our attack (discovered independently from [8]) has subexponential complexity, thus significantly reducing the security of SIDH and SIKE. When the endomorphism ring of the starting curve is known, our attack (here derived from [8]) has polynomial-time complexity assuming the generalised Riemann hypothesis. Our attack applies to any isogeny-based cryptosystem that publishes the images of points under the secret isogeny, for example Séta [13] and B-SIDH [11]. It does not apply to CSIDH [9], CSI-FiSh [3], or SQISign [14].

AB - We present an attack on SIDH utilising isogenies between polarized products of two supersingular elliptic curves. In the case of arbitrary starting curve, our attack (discovered independently from [8]) has subexponential complexity, thus significantly reducing the security of SIDH and SIKE. When the endomorphism ring of the starting curve is known, our attack (here derived from [8]) has polynomial-time complexity assuming the generalised Riemann hypothesis. Our attack applies to any isogeny-based cryptosystem that publishes the images of points under the secret isogeny, for example Séta [13] and B-SIDH [11]. It does not apply to CSIDH [9], CSI-FiSh [3], or SQISign [14].

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

U2 - 10.1007/978-3-031-30589-4_16

DO - 10.1007/978-3-031-30589-4_16

M3 - Conference Contribution (Conference Proceeding)

SN - 9783031305887

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

SP - 448

EP - 471

BT - Advances in Cryptology – EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings

A2 - Hazay, Carmit

A2 - Stam, Martijn

PB - Springer, Cham

T2 - Eurocrypt 2023

Y2 - 23 April 2023 through 27 April 2023

ER -

Maino L , Martindale C, Panny L, Pope G, Wesolowski B. A Direct Key Recovery Attack on SIDH. In Hazay C, Stam M, editors, Advances in Cryptology – EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings: Advances in Cryptology. Springer, Cham. 2023. p. 448-471. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-30589-4_16

A Direct Key Recovery Attack on SIDH

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this