Paper 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.

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