Paper 2022/1283 Original: eprint.iacr.org/2022/1283 ↗
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.
Metadata
- Available format(s)
PDF- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- History
- 2022-09-27: last updated
- 2022-09-27: published
- Short URL
- https://ia.cr/2022/1283
- License
- https://creativecommons.org/licenses/by-sa/4.0/
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},
url = {https://eprint.iacr.org/2022/1283}
}