Cryptology ePrint Archive: Report 2021/1369

Faster Isogenies for Quantum-Safe SIKE

Rami Elkhatib and Brian Koziel and Reza Azarderakhsh

Abstract: In the third round of the NIST PQC standardization process, the only isogeny-based candidate, SIKE, suffers from slow performance when compared to other contenders. The large-degree isogeny computation performs a series of isogenous mappings between curves, to account for about 80% of SIKE’s latency. Here, we propose, implement, and evaluate a new method for computing large-degree isogenies of an odd power. Our new strategy for this computation avoids expensive recomputation of temporary isogeny results.We modified open-source libraries targeting x86, ARM64, and ARM32 platforms. Across each of these implementations, our new method achieves 10% and 5% speedups in SIKE’s key encapsulation and decapsulation operations, respectively. Additionally, these implementations use 3% less stack space at only a 48 byte increase in code size. Given the benefit and simplicity of our approach, we recommend this method for current and emerging SIKE implementations.

Category / Keywords:

Date: received 10 Oct 2021, last revised 12 Oct 2021

Contact author: razarder at pqsecurity com

Available format(s): PDF | BibTeX Citation

Version: 20211012:220645 (All versions of this report)

Short URL: ia.cr/2021/1369


[ Cryptology ePrint archive ]