New Hybrid Method for Isogeny-based Cryptosystems using Edwards Curves

Suhri Kim, Kisoon Yoon, Jihoon Kwon, Young-Ho Park, Seokhie Hong

Abstract

As the cryptographic community prepares for the post-quantum era, isogeny-based primitives like Supersingular Isogeny Diffie-Hellman (SIDH) have emerged as strong candidates due to their exceptionally small key sizes. However, their computational intensity remains a significant barrier to widespread adoption. This paper presents a novel hybrid approach that optimizes isogeny-based cryptosystems by strategically alternating between Montgomery and Edwards curve models. By utilizing Edwards curves for coefficient recovery and Montgomery curves for point arithmetic, the authors achieve a performance improvement of approximately 1% over existing state-of-the-art implementations. This research demonstrates that the overhead of switching between curve models can be minimized, offering a practical pathway for further optimization in post-quantum cryptography.

Introduction

The advent of large-scale quantum computing poses a fundamental threat to current public-key infrastructure, specifically algorithms relying on the hardness of integer factorization and discrete logarithms. Isogeny-based cryptography is a promising alternative within the Post-Quantum Cryptography (PQC) landscape. While it boasts the smallest key sizes among PQC candidates, it is notably slower than lattice-based or code-based alternatives.

Historically, Montgomery curves have been the "gold standard" for implementing isogeny-based protocols because of their highly efficient point arithmetic. While Edwards curves (and twisted Edwards curves) offer competitive arithmetic in other contexts, previous attempts to integrate them into isogeny-based systems often resulted in conversion overhead that negated any performance gains. This paper investigates whether a specific, optimized combination of these two curve models can yield a net performance increase.

Methodology

The researchers propose a hybrid strategy that leverages the unique mathematical strengths of both Montgomery and Edwards representations. The core of their methodology involves four key optimizations:

1. Strategic Division of Labor

The authors identified that while Montgomery curves are superior for point operations, Edwards curves are mathematically more efficient for calculating the "shape" or coefficients of a new curve following an isogeny transformation. Consequently, the hybrid method uses Edwards curves specifically for the get_isog function (coefficient recovery) while maintaining point arithmetic on Montgomery curves.

2. Formula Optimization

The team refined the 4-isogeny formula specifically for Edwards curves. By optimizing the underlying algebra, they reduced the computational cost to $6M + 6S$ (six multiplications and six squarings), providing a leaner alternative to standard Montgomery-only formulas.

3. Breaking Computational Dependencies

In traditional Montgomery implementations, a strict dependency exists: curve coefficients must be recovered before an isogeny can be evaluated. The hybrid approach breaks this dependency during the final step of public key generation. By strategically reordering operations, the authors were able to omit a coefficient recovery step entirely, further reducing the cycle count.

4. Efficient Birational Conversion

The success of a hybrid model depends on the cost of moving between curve representations. The authors utilize "birational equivalence" to switch between Montgomery and Edwards curves. They demonstrate that this conversion is computationally "cheap," requiring only two field additions, which allows for on-the-fly switching without significant penalties.

Experimental Results

The hybrid method was implemented in C and x64 assembly, building upon the Microsoft SIDH library (v3.1). Performance was evaluated on an Intel Core i7-8700K processor using NIST-standardized parameters for 128-bit and 192-bit security levels.

Security Level Parameter Set Speedup vs. Montgomery-only
128-bit $p_{503}$ 1.03%
192-bit $p_{751}$ 1.09%

For the $p_{751}$ prime, the total clock cycles for a key exchange dropped from $71.2 \times 10^6$ to $70.4 \times 10^6$. While a ~1% gain may appear modest, in the highly optimized field of cryptographic engineering, any reduction in the computational bottleneck of isogeny-based systems is a significant contribution.

Discussion and Conclusion

This research proves that mixing curve models is not only theoretically possible but practically beneficial for isogeny-based cryptosystems. The "coefficient specialist" role assigned to Edwards curves, combined with the low-cost birational bridge, provides a template for future optimizations.

It is important to note that since the publication of this research, the SIDH protocol has been subjected to significant theoretical attacks. However, the underlying arithmetic optimizations and the hybrid curve strategy remain highly relevant for other isogeny-based primitives (such as CSIDH or B-SIDH) that share similar mathematical structures. Future work may explore applying these hybrid techniques to broader classes of isogenies where the efficiency gains might be even more pronounced.

Summary updated

BibTeX
@article{kim2018new,
  author = {Suhri Kim and Kisoon Yoon and Jihoon Kwon and Young-Ho Park and Seokhie Hong},
  title = {{New Hybrid Method for Isogeny-based Cryptosystems using Edwards Curves}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2018},
}
Figure