skip to main content


Title: Multiprime Strategies for Serial Evaluation of eSIDH-Like Isogenies
We present new results and speedups for the large-degree isogeny computations within the extended supersingular isogeny Diffie-Hellman (eSIDH) key agreement framework. As proposed by Cervantes-Vázquez, Ochoa-Jiménez, and Rodríguez-Henríquez, eSIDH is an extension to SIDH and fourth round NIST post-quantum cryptographic standardization candidate SIKE. By utilizing multiprime large-degree isogenies, eSIDH and eSIKE are faster than the standard SIDH/SIKE and amenable to parallelization techniques that can noticeably increase their speed with multiple cores. Here, we investigate the use of multiprime isogeny strategies to speed up eSIDH and eSIKE in serial implementations. These strategies have been investigated for other isogeny schemes such as CSIDH. We apply them to the eSIDH/eSIKE scenario to speed up the multiprime strategy by about 10%. When applied to eSIDH, we achieve a 7–8% speedup for Bob’s shared key agreement operation. When applied to eSIKE, we achieve a 3–4% speedup for key decapsulation. Historically, SIDH and SIKE have been considerably slower than its competitors in the NIST PQC standardization process. These results continue to highlight the various speedups achievable with the eSIKE framework to alleviate these speed concerns. Though eSIDH and eSIKE are susceptible to the recent devastating attacks on SIKE, our analysis applies to smooth degree isogeny computations in general, and isogeny-based signature schemes which use isogenies of smooth (not necessarily powersmooth) degree.  more » « less
Award ID(s):
2101085
PAR ID:
10524253
Author(s) / Creator(s):
; ;
Publisher / Repository:
LNCS
Date Published:
ISSN:
10.1007/978-3-031-45933-7_21
ISBN:
978-3-031-45932-0
Format(s):
Medium: X
Location:
USA
Sponsoring Org:
National Science Foundation
More Like this
  1. The advances in quantum technologies and the fast move toward quantum computing are threatening classical cryptography and urge the deployment of post-quantum (PQ) schemes. The only isogeny-based candidate forming part of the third round of the standardization, the Supersingular Isogeny Key Encapsulation (SIKE) mechanism, is a subject of constant latency optimizations given its attractive compact key size lengths and, thus, its limited bandwidth and memory requirements. In this work, we present a new speed record of the SIKE protocol by implementing novel low-level finite field arithmetic targeting ARMv7-M architecture. We develop a handcrafted assembly code for the modular multiplication and squaring functions where we obtain 8.71% and 5.38% of speedup, respectively, compared to the last best-reported assembly implementations for p434. After deploying the finite field optimized architecture to the SIKE protocol, we observe 5.63%, 3.93%, 3.48%, and 1.61% of latency reduction for SIKE p434, p503, p610, and p751, respectively, targeting the NIST recommended STM32F407VG discovery board for our experiments. 
    more » « less
  2. Yung, M ; L, Shujun. (Ed.)
    In 2016, the National Institute of Standards and Technology (NIST) initiated a standardization process among the post-quantum secure algorithms. Forming part of the alternate group of candidates after Round 2 of the process is the Supersingular Isogeny Key Encapsulation (SIKE) mechanism which attracts with the smallest key sizes offering post-quantum security in scenarios of limited bandwidth and memory resources. Even further reduction of the exchanged information is offered by the compression mechanism, proposed by Azarderakhsh et al., which, however, introduces a significant time overhead and increases the memory requirements of the protocol, making it challenging to integrate it into an embedded system. In this paper, we propose the first compressed SIKE implementation for a resource-constrained device, where we targeted the NIST recommended platform STM32F407VG featuring ARM Cortex-M4 processor. We integrate the isogeny-based implementation strategies described previously in the literature into the compressed version of SIKE. Additionally, we propose a new assembly design for the finite field operations particular for the compressed SIKE, and observe a speedup of up to 16% and up to 25% compared to the last best-reported assembly implementations for p434, p503, and p610. 
    more » « less
  3. Finite field multiplication plays the main role determining the efficiency of public key cryptography systems based on RSA and elliptic curve cryptography (ECC). Most recently, quantum-safe cryptographic systems are proposed based on supersingular isogenies on elliptic curves which require large integer multiplications over extended prime fields. In this work, we present two Montgomery multiplication architectures for special primes used in a post-quantum cryptography system known as supersingular isogeny key encapsulation (SIKE). We optimize two existing Montgomery multiplication algorithms and develop area-efficient and time-efficient Montgomery multiplication architectures for hardware implementations of post-quantum cryptography. Our proposed time-efficient architecture is 32% to 42% faster than the leading one (depending on the prime size) available in the literature which has been used in original SIKE submission to the NIST standardization process. The area-efficient architecture is 42% to 50% smaller than the counterparts and is about 3% to 11% faster depending on the NIST security level. 
    more » « less
  4. Problems relating to the computation of isogenies between elliptic curves defined over finite fields have been studied for a long time. Isogenies on supersingular elliptic curves are a candidate for quantum-safe key exchange protocols because the best known classical and quantum algorithms for solving well-formed instances of the isogeny problem are exponential. We propose an implementation of supersingular isogeny Diffie-Hellman (SIDH) key exchange for complete Edwards curves. Our work is motivated by the use of Edwards curves to speed up many cryptographic protocols and improve security. Our work does not actually provide a faster implementation of SIDH, but the use of complete Edwards curves and their complete addition formulae provides security benefits against side-channel attacks. We provide run time complexity analysis and operation counts for the proposed key exchange based on Edwards curves along with comparisons to the Montgomery form. 
    more » « less
  5. Recent attacks have shown that SIKE is not secure and should not be used in its current state. However, this work was completed before these attacks were discovered and might be beneficial to other cryptosystems such as SQISign. The primary downside of SIKE is its performance. However, this work achieves new SIKE speed records even using less resources than the state-of-the-art. Our approach entails designing and optimizing a new field multiplier, SIKE-optimized Keccak unit, and high-level controller. On a Xilinx Virtex-7 FPGA, this architecture performs the NIST Level 1 SIKE scheme key encapsulation and key decapsulation functions in 2.23 and 2.39 ms, respectively. The combined key encapsulation and decapsulation time is 4.62 ms, which outperforms the next best Virtex-7 implementation by nearly 2 ms. Our implementation achieves speed records for the NIST Level 1, 2, and 3 parameter sets. Only our NIST Level 5 parameter set was beat by an all-out performance implementation. Our implementations also efficiently utilize the FPGA resources, achieving new records in area-time product metrics for all parameter sets. Overall, this work continues to push the bar for accelerating SIKE computations to make a stronger case for SIKE standardization.

     
    more » « less