Welcome to the resource topic for 2024/584
Title:
Efficient Implementations of Square-root Vélu’s Formulas
Authors: Jianming Lin, Weize Wang, Chang-An Zhao, Yuhao Zheng
Abstract:In the implementation of isogeny-based cryptographic schemes, Vélu’s formulas are essential for constructing and evaluating odd degree isogenies. Bernstein et al. proposed an approach known as √élu, which computes an 𝓁-isogeny at a cost of̃ (√𝓁) finite field operations. This paper presents two key improvements to enhance the efficiency of the implementation of √élu from two aspects: optimizing the partition involved in √élu and speeding up the computations of the sums of products used in polynomial multiplications over finite field 𝔽𝑝 with large prime characteristic 𝑝. To optimize the partition, we adjust it to enhance the utilization of 𝑥-coordinates and eliminate the computational redundancy, which can ultimately reduce the number of 𝔽𝑝-multiplications. The speedup of the sums of products is to employ two techniques: lazy reduction (abbreviated as LZYR) and generalized interleaved Montgomery multiplication (abbreviated as INTL). These techniques aim to minimize the underlying operations such as 𝔽𝑝-reductions and
assembly memory instructions. We present an optimized C and
ssembly code implementation of √élu for the CTIDH512 instantiation. In terms of 𝓁-isogeny computations in CTIDH512, the performance of clock cycles applying new partition + INTL (resp. new partition + LZYR) offers an improvement up to 16.05% (resp. 10.96%) compared to the previous work.
ePrint: https://eprint.iacr.org/2024/584
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .