eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2022/975

An efficient key recovery attack on SIDH

Wouter Castryck, KU Leuven
Thomas Decru, KU Leuven
Abstract

We present an efficient key recovery attack on the Supersingular Isogeny Diffie-Hellman protocol (SIDH). The attack is based on Kani's "reducibility criterion" for isogenies from products of elliptic curves and strongly relies on the torsion point images that Alice and Bob exchange during the protocol. If we assume knowledge of the endomorphism ring of the starting curve then the classical running time is polynomial in the input size (heuristically), apart from the factorization of a small number of integers that only depend on the system parameters. The attack is particularly fast and easy to implement if one of the parties uses 2-isogenies and the starting curve comes equipped with a non-scalar endomorphism of very small degree; this is the case for SIKE, the instantiation of SIDH that recently advanced to the fourth round of NIST's standardization effort for post-quantum cryptography. Our Magma implementation breaks SIKEp434, which aims at security level 1, in about ten minutes on a single core.

Note: Fixed a typo in Section 5.2.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in EUROCRYPT 2023
Keywords
SIDHisogeny-based cryptographypost-quantum cryptography
Contact author(s)
wouter castryck @ esat kuleuven be
thomas decru @ esat kuleuven be
History
2023-05-15: last of 4 revisions
2022-07-30: received
See all versions
Short URL
https://ia.cr/2022/975
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/975,
      author = {Wouter Castryck and Thomas Decru},
      title = {An efficient key recovery attack on SIDH},
      howpublished = {Cryptology ePrint Archive, Paper 2022/975},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/975}},
      url = {https://eprint.iacr.org/2022/975}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.