Paper 2023/013

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

Tako Boris Fouotsa, École Polytechnique Fédérale de Lausanne
Tomoki Moriya, The University of Tokyo
Christophe Petit, Université Libre de Bruxelles, University of Birmingham
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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
IsogeniesSIDH attacksCountermeasuresM-SIDHMD-SIDH
Contact author(s)
tako fouotsa @ epfl ch
tomoki_moriya @ mist i u-tokyo ac jp
christophe f petit @ gmail com
History
2023-01-03: approved
2023-01-03: received
See all versions
Short URL
https://ia.cr/2023/013
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/013,
      author = {Tako Boris Fouotsa and Tomoki Moriya and Christophe Petit},
      title = {M-{SIDH} and {MD}-{SIDH}: countering {SIDH} attacks by masking information},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/013},
      year = {2023},
      url = {https://eprint.iacr.org/2023/013}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.