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

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

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

Abstract

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

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: isogeny-based cryptography Vélu's formulas resultants B-SIDH SIDH CSIDH SIKE
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

BibTeX

@misc{cryptoeprint:2020/1109,
      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}
}