Cryptology ePrint Archive: Report 2020/1109

On new Vélu's formulae and their applications to CSIDH and B-SIDH constant-time implementations

Gora Adj and Jesús-Javier Chi-Domínguez and Francisco Rodríguez-Henríquez

Abstract: At a combined computational expense of about $6{\ell}$ field operations, Vélu's formulae are used to construct and evaluate degree-$\ell$ isogenies in the vast majority of isogeny-based primitive implementations. Recently, Bernstein, de Feo, Leroux and Smith introduced a new approach for solving this same problem at a reduced cost of just $\tilde{O}(\sqrt{\ell})$ field operations. In this work, we present a concrete computational analysis of these novel formulae, along with several algorithmic tricks that helped us to significantly reduce their practical cost. Furthermore, we report a Python-3 implementation of several instantiations of CSIDH and B-SIDH using a combination of the novel formulae and an adaptation of the optimal strategies commonly used in the SIDH/SIKE protocols. Compared to a traditional Vélu constant-time implementation of CSIDH, our experimental results report a saving of 5.357\%, 13.68\% and 25.938\% base field operations for CSIDH-512, CSIDH-1024, and CSIDH-1792, respectively. Additionally, the first implementation of the B-SIDH scheme in the open literature is reported here.

Category / Keywords: public-key cryptography / isogeny-based cryptography, Vélu's formulas, resultants

Date: received 14 Sep 2020, last revised 9 Oct 2020

Contact author: gora adj at udl cat,jesus chidominguez@tuni fi,francisco@cs cinvestav mx

Available format(s): PDF | BibTeX Citation

Note: This version includes a comparative between Schonage-FFT and Karatsuba-style polynomial multiplication (see appendix B).

Version: 20201009:182822 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]