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.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- isogeny-based cryptographyVélu's formulasresultants
- Contact author(s)
-
gora adj @ udl cat
jesus chidominguez @ tuni fi
francisco @ cs cinvestav mx - History
- 2021-09-05: last of 12 revisions
- 2020-09-15: received
- See all versions
- Short URL
- https://ia.cr/2020/1109
- License
-
CC BY