eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2020/1109

Karatsuba-based square-root Vélu’s formulas applied to two isogeny-based protocols

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


At a combined computational expense of about $6{\ell}$ field operations, Vélu's formulas are used to construct and evaluate degree-$\ell$ isogenies in the vast majority of isogeny-based cryptographic schemes. By adapting to Vélu's formulas a baby-step giant-step approach, Bernstein, De Feo, Leroux, and Smith presented a procedure that can computes isogeny operations at a reduced cost of just $\tilde{O}(\sqrt{\ell})$ field operations. In this paper, we present a concrete computational analysis of these novel procedure along with several algorithmic tricks that helped us to further decrease its computational cost. We also report an optimized Python3-code implementation of several instantiations of two isogeny-based key-exchange protocols, namely, CSIDH and B-SIDH. Our software library uses a combination of the modified Vélu's formulas and an adaptation of the optimal strategies commonly used in the SIDH/SIKE protocols to produce significant speedups. 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, we present the first optimized implementation of B-SIDH ever reported in the open literature.

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

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
isogeny-based cryptographyVélu's formulasresultantsB-SIDHSIDHCSIDHSIKE
Contact author(s)
gora adj @ udl cat
jesus chidominguez @ tuni fi
francisco @ cs cinvestav mx
2021-09-05: last of 12 revisions
2020-09-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Gora Adj and Jesús-Javier Chi-Domínguez and Francisco Rodríguez-Henríquez},
      title = {Karatsuba-based square-root Vélu’s formulas applied to two isogeny-based protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1109},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1109}},
      url = {https://eprint.iacr.org/2020/1109}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.