ملاحظات حسابگرانه برای رمزنگاری مبتنی بر ایزوژنتیک Arithmetic Considerations for Isogeny Based Cryptography

1 INTRODUCTION RECENT significant advances in quantum computing have accelerated the research into post-quantum cryptography schemes [22], [35], [49]. Such schemes can be used as drop-in replacements for classical public-key cryptography primitives. This demand is driven by interest from standardization bodies, such as the call for proposals for new public-key cryptography standards [47] by the National Institute of Standards and Technology (NIST) [15] and the European Union’s prestigious PQCrypto research effort [2]. One such recent approach is called Supersingular Isogeny Diffie-Hellman (SIDH), which was introduced in 2011 and is based on the hardness of constructing a smoothdegree isogeny, between two supersingular elliptic curves defined over a finite field [21]. The Supersingular Isogeny Key Encapsulation (SIKE) protocol [3] submission to NIST is based on the SIDH approach with optimizations from recent work such as [19], [25]. The full details of this protocol are outside the scope of this paper. However, the arithmetic in supersingular isogeny cryptography is performed in quadratic extension fields of a prime field Fq with q = 2xp y ± 1; where the extension field is formed as Fq 2 = Fq(i) with i 2 = −1. The computationally expensive operations consist of computing a number of elliptic curve scalar multiplications by ` and of evaluations of `-isogenies for ` ∈ {2, p} which in turn translate to a number of arithmetic operation in Fq 2 . In the proposed SIKE protocol p = 3 and the elliptic curve arithmetic is performed using Montgomery curves [46]. These choices are motivated by performance arguments. In this paper we investigate alternative approaches. On the one hand we study, in Section 3, if different choices for p in the modulus q = 2xp y ± 1 can result in faster modular reduction. We find that alternative design choices can indeed lead to practical performance gains for the modular arithmetic. However, this ignores the impact on the isogeny computations: as shown by Costello and Hisil in [18] there is a moderate degradation when computing arbitrary large- and odd-degree isogenies. The overall protocol performance might suffer slightly but, as motivated in [18], the computational effort for one of the parties computing the key-exchange can be decreased. This is beneficial in settings where the computational power is unbalanced. On the other hand we investigate in Section 4 if the elliptic curve scalar multiplications can be done more efficiently by using curve arithmetic on different curve models. Montgomery curves are extremely efficient but require the differential addition law to gain this performance. We study if switching to twisted Edwards curves [24], [7], [6], [30] is beneficial: this setting allows one to more generic use addition/subtraction chains which can lower the number of arithmetic operations when multiplying by small powers of p at-a-time. We note that addition chains in the setting of SIDH have been studied in [39] before. However, the focus and goal of [39] is to find addition chains to aid in the computation of modular inversion and modular square root computation. This paper is an extended version of a previous work which appeared as [11]. The main result presented in [11] is captured in Section 3. This has been extended with the addition-subtraction chain investigation as presented in Section 4. The code which implements the modular arithmetic presented in Section 3 can be found at https: //github.com/sidh-arith.