Paper 2024/851
On the parallelization of square-root Vélu's formulas
Abstract
A primary challenge in isogeny-based cryptography lies in the substantial computational cost associated to computing and evaluating prime-degree isogenies. This computation traditionally relied on Vélu's formulas, an approach with time complexity linear in the degree but which was further enhanced by Bernstein, De Feo, Leroux, and Smith to a square-root complexity. The improved square-root Vélu's formulas exhibit a degree of parallelizability that has not been exploited in major implementations. In this study, we introduce a theoretical framework for parallelizing isogeny computations and provide a proof-of-concept implementation in C with OpenMP. While the parallelization effectiveness exhibits diminishing returns with the number of cores, we still obtain strong results when using a small number of cores. Concretely, our implementation shows that for large degrees it is easy to achieve speedup factors of up to $1.74$, $2.54$, and $3.44$ for two, four, and eight cores, respectively.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Published elsewhere. Math. Comput. Appl. (ISSN 2297-8747) on 07 February 2024
- DOI
- 10.3390/mca29010014
- Keywords
- isogenieselliptic curvesparallelismpostquantum cryptographyefficient implementation
- Contact author(s)
-
jorge saab @ tii ae
odalis ortega @ postgrado uv cl
amalia pizarro @ uv cl - History
- 2024-05-31: approved
- 2024-05-30: received
- See all versions
- Short URL
- https://ia.cr/2024/851
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/851,
author = {Jorge Chávez-Saab and Odalis Ortega and Amalia Pizarro-Madariaga},
title = {On the parallelization of square-root Vélu's formulas},
howpublished = {Cryptology ePrint Archive, Paper 2024/851},
year = {2024},
doi = {10.3390/mca29010014},
note = {\url{https://eprint.iacr.org/2024/851}},
url = {https://eprint.iacr.org/2024/851}
}
