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

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

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}
}