Paper 2024/851

On the parallelization of square-root Vélu's formulas

Jorge Chávez-Saab, Cryptography Research Center, Technology Innovation Institute, Abu Dhabi, P.O.1639. United Arab Emirates
Odalis Ortega, Instituto de Matemáticas, Universidad de Valparaíso, Valparaíso, Chile
Amalia Pizarro-Madariaga, Instituto de Matemáticas, Universidad de Valparaíso, Valparaíso, Chile
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
Creative Commons Attribution
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},
      url = {https://eprint.iacr.org/2024/851}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.