Paper 2020/1109 Original: eprint.iacr.org/2020/1109 ↗
Karatsuba-based square-root Vélu’s formulas applied to two isogeny-based protocols
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.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2021-09-05: last updated
- 2020-09-15: published
- Short URL
- https://ia.cr/2020/1109
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2020/1109}
}