Paper 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.
- 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
- 2022-09-27: received
- See all versions
- Short URL
- https://ia.cr/2022/1283
- License
-
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},
url = {https://eprint.iacr.org/2022/1283}
}
