M-SIDH and MD-SIDH: countering SIDH attacks by masking information

Tako Boris Fouotsa; Tomoki Moriya; Christophe Petit

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

M-SIDH and MD-SIDH: countering SIDH attacks by masking information

Tako Boris Fouotsa^*, Tomoki Moriya, Christophe Petit

^*Corresponding author for this work

Computer Science

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

1 Downloads (Pure)

Abstract

The SIDH protocol is an isogeny-based key exchange protocol using supersingular isogenies, designed by Jao and De Feo in 2011. The protocol underlies the SIKE algorithm which advanced to the fourth round of NIST’s post-quantum standardization project in May 2022. The algorithm was considered very promising: indeed the most significant attacks against SIDH were meet-in-the-middle variants with exponential complexity, and torsion point attacks which only applied to unbalanced parameters (and in particular, not to SIKE).

This security picture dramatically changed in August 2022 with new attacks by Castryck-Decru, Maino-Martindale and Robert. Like prior attacks on unbalanced versions, these new attacks exploit torsion point information provided in the SIDH protocol. Crucially however, the new attacks embed the isogeny problem into a similar isogeny problem in a higher dimension to also affect the balanced parameters. As a result of these works, the SIKE algorithm is now fully broken both in theory and in practice.

Given the considerable interest attracted by SIKE and related protocols in recent years, it is natural to seek countermeasures to the new attacks. In this paper, we introduce two such countermeasures based on partially hiding the isogeny degrees and torsion point information in the SIDH protocol. We present a preliminary analysis of the resulting schemes including non-trivial generalizations of prior attacks. Based on this analysis we suggest parameters for our M-SIDH variant with public key sizes of 4434, 7037 and 9750 bytes respectively for NIST security levels 1, 3, 5.

Original language	English
Title of host publication	Advances in Cryptology – EUROCRYPT 2023
Subtitle of host publication	42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings
Editors	Carmit Hazay, Martijn Stam
Publisher	Springer
Pages	282-309
Edition	1
ISBN (Electronic)	978-3-031-30589-4
ISBN (Print)	978-3-031-30588-7
DOIs	https://doi.org/10.1007/978-3-031-30589-4_10
Publication status	E-pub ahead of print - 16 Apr 2023
Event	42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques - Lyon, France Duration: 23 Apr 2023 → 27 Apr 2023

Publication series

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

Conference

Conference	42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques
Abbreviated title	EUROCRYPT 2023
Country/Territory	France
City	Lyon
Period	23/04/23 → 27/04/23

Access to Document

10.1007/978-3-031-30589-4_10Licence: None: All rights reserved

FouotsaT2023MSIDH
This is the Accepted Author Manuscript of the followig article published by Springer and subject to Springer's Terms of Use at https://www.springernature.com/gp/open-research/policies/accepted-manuscript-terms: Fouotsa, T.B., Moriya, T., Petit, C. (2023). M-SIDH and MD-SIDH: Countering SIDH Attacks by Masking Information. In: Hazay, C., Stam, M. (eds) Advances in Cryptology – EUROCRYPT 2023. EUROCRYPT 2023. Lecture Notes in Computer Science, vol 14008. Springer, Cham. https://doi.org/10.1007/978-3-031-30589-4_10
Accepted author manuscript, 617 KBLicence: Other (please specify with Rights Statement)

Cite this

Fouotsa, T. B., Moriya, T., & Petit, C. (2023). M-SIDH and MD-SIDH: countering SIDH attacks by masking information. In C. Hazay, & M. Stam (Eds.), Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings (1 ed., pp. 282-309). (Lecture Notes in Computer Science; Vol. 14008). Springer. Advance online publication. https://doi.org/10.1007/978-3-031-30589-4_10

Fouotsa, Tako Boris ; Moriya, Tomoki ; Petit, Christophe. / M-SIDH and MD-SIDH : countering SIDH attacks by masking information. Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings. editor / Carmit Hazay ; Martijn Stam. 1. ed. Springer, 2023. pp. 282-309 (Lecture Notes in Computer Science).

@inproceedings{12b4347c493c49c796aa3341ee428df6,

title = "M-SIDH and MD-SIDH: countering SIDH attacks by masking information",

abstract = "The SIDH protocol is an isogeny-based key exchange protocol using supersingular isogenies, designed by Jao and De Feo in 2011. The protocol underlies the SIKE algorithm which advanced to the fourth round of NIST{\textquoteright}s post-quantum standardization project in May 2022. The algorithm was considered very promising: indeed the most significant attacks against SIDH were meet-in-the-middle variants with exponential complexity, and torsion point attacks which only applied to unbalanced parameters (and in particular, not to SIKE).This security picture dramatically changed in August 2022 with new attacks by Castryck-Decru, Maino-Martindale and Robert. Like prior attacks on unbalanced versions, these new attacks exploit torsion point information provided in the SIDH protocol. Crucially however, the new attacks embed the isogeny problem into a similar isogeny problem in a higher dimension to also affect the balanced parameters. As a result of these works, the SIKE algorithm is now fully broken both in theory and in practice.Given the considerable interest attracted by SIKE and related protocols in recent years, it is natural to seek countermeasures to the new attacks. In this paper, we introduce two such countermeasures based on partially hiding the isogeny degrees and torsion point information in the SIDH protocol. We present a preliminary analysis of the resulting schemes including non-trivial generalizations of prior attacks. Based on this analysis we suggest parameters for our M-SIDH variant with public key sizes of 4434, 7037 and 9750 bytes respectively for NIST security levels 1, 3, 5.",

author = "Fouotsa, {Tako Boris} and Tomoki Moriya and Christophe Petit",

year = "2023",

month = apr,

day = "16",

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

language = "English",

isbn = "978-3-031-30588-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "282--309",

editor = "Carmit Hazay and Martijn Stam",

booktitle = "Advances in Cryptology – EUROCRYPT 2023",

edition = "1",

note = "42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2023 ; Conference date: 23-04-2023 Through 27-04-2023",

}

Fouotsa, TB, Moriya, T & Petit, C 2023, M-SIDH and MD-SIDH: countering SIDH attacks by masking information. in C Hazay & M Stam (eds), Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings. 1 edn, Lecture Notes in Computer Science, vol. 14008, Springer, pp. 282-309, 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, 23/04/23. https://doi.org/10.1007/978-3-031-30589-4_10

M-SIDH and MD-SIDH: countering SIDH attacks by masking information. / Fouotsa, Tako Boris; Moriya, Tomoki ; Petit, Christophe.
Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings. ed. / Carmit Hazay; Martijn Stam. 1. ed. Springer, 2023. p. 282-309 (Lecture Notes in Computer Science; Vol. 14008).

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

TY - GEN

T1 - M-SIDH and MD-SIDH

T2 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques

AU - Fouotsa, Tako Boris

AU - Moriya, Tomoki

AU - Petit, Christophe

PY - 2023/4/16

Y1 - 2023/4/16

N2 - The SIDH protocol is an isogeny-based key exchange protocol using supersingular isogenies, designed by Jao and De Feo in 2011. The protocol underlies the SIKE algorithm which advanced to the fourth round of NIST’s post-quantum standardization project in May 2022. The algorithm was considered very promising: indeed the most significant attacks against SIDH were meet-in-the-middle variants with exponential complexity, and torsion point attacks which only applied to unbalanced parameters (and in particular, not to SIKE).This security picture dramatically changed in August 2022 with new attacks by Castryck-Decru, Maino-Martindale and Robert. Like prior attacks on unbalanced versions, these new attacks exploit torsion point information provided in the SIDH protocol. Crucially however, the new attacks embed the isogeny problem into a similar isogeny problem in a higher dimension to also affect the balanced parameters. As a result of these works, the SIKE algorithm is now fully broken both in theory and in practice.Given the considerable interest attracted by SIKE and related protocols in recent years, it is natural to seek countermeasures to the new attacks. In this paper, we introduce two such countermeasures based on partially hiding the isogeny degrees and torsion point information in the SIDH protocol. We present a preliminary analysis of the resulting schemes including non-trivial generalizations of prior attacks. Based on this analysis we suggest parameters for our M-SIDH variant with public key sizes of 4434, 7037 and 9750 bytes respectively for NIST security levels 1, 3, 5.

AB - The SIDH protocol is an isogeny-based key exchange protocol using supersingular isogenies, designed by Jao and De Feo in 2011. The protocol underlies the SIKE algorithm which advanced to the fourth round of NIST’s post-quantum standardization project in May 2022. The algorithm was considered very promising: indeed the most significant attacks against SIDH were meet-in-the-middle variants with exponential complexity, and torsion point attacks which only applied to unbalanced parameters (and in particular, not to SIKE).This security picture dramatically changed in August 2022 with new attacks by Castryck-Decru, Maino-Martindale and Robert. Like prior attacks on unbalanced versions, these new attacks exploit torsion point information provided in the SIDH protocol. Crucially however, the new attacks embed the isogeny problem into a similar isogeny problem in a higher dimension to also affect the balanced parameters. As a result of these works, the SIKE algorithm is now fully broken both in theory and in practice.Given the considerable interest attracted by SIKE and related protocols in recent years, it is natural to seek countermeasures to the new attacks. In this paper, we introduce two such countermeasures based on partially hiding the isogeny degrees and torsion point information in the SIDH protocol. We present a preliminary analysis of the resulting schemes including non-trivial generalizations of prior attacks. Based on this analysis we suggest parameters for our M-SIDH variant with public key sizes of 4434, 7037 and 9750 bytes respectively for NIST security levels 1, 3, 5.

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

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

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

M3 - Conference contribution

SN - 978-3-031-30588-7

T3 - Lecture Notes in Computer Science

SP - 282

EP - 309

BT - Advances in Cryptology – EUROCRYPT 2023

A2 - Hazay, Carmit

A2 - Stam, Martijn

PB - Springer

Y2 - 23 April 2023 through 27 April 2023

ER -

Fouotsa TB, Moriya T , Petit C. M-SIDH and MD-SIDH: countering SIDH attacks by masking information. In Hazay C, Stam M, editors, Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings. 1 ed. Springer. 2023. p. 282-309. (Lecture Notes in Computer Science). Epub 2023 Apr 16. doi: 10.1007/978-3-031-30589-4_10

M-SIDH and MD-SIDH: countering SIDH attacks by masking information

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this