### A Note on Reimplementing the Castryck-Decru Attack and Lessons Learned for SageMath

##### Abstract

This note describes the implementation of the Castryck-Decru key recovery attack on SIDH using the computer algebra system, SageMath. We describe in detail alternate computation methods for the isogeny steps of the original attack ($(2,2)$-isogenies from a product of elliptic curves and from a Jacobian), using explicit formulas to compute values of these isogenies at given points, motivated by both performance considerations and working around SageMath limitations. A performance analysis is provided, with focus given to the various algorithmic and SageMath specific improvements made during development, which in total accumulated in approximately an eight-fold performance improvement compared with a naïve reimplementation of the proof of concept.

Available format(s)
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
SIDH SIKE Isogeny-Based Cryptography Post-Quantum Cryptography SageMath
Contact author(s)
remyoudompheng @ gmail com
giacomo pope @ nccgroup com
History
2022-09-28: approved
See all versions
Short URL
https://ia.cr/2022/1283

CC BY-SA

BibTeX

@misc{cryptoeprint:2022/1283,
author = {Rémy Oudompheng and Giacomo Pope},
title = {A Note on Reimplementing the Castryck-Decru Attack and Lessons Learned for SageMath},
howpublished = {Cryptology ePrint Archive, Paper 2022/1283},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1283}},
url = {https://eprint.iacr.org/2022/1283}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.