Welcome to the resource topic for 2020/1109
Title:
Karatsuba-based square-root Vélu’s formulas applied to two isogeny-based protocols
Authors: Gora Adj, Jesús-Javier Chi-Domínguez, 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.
ePrint: https://eprint.iacr.org/2020/1109
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .