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

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

  • نوع فایل : کتاب
  • زبان : انگلیسی
  • ناشر : IEEE
  • چاپ و سال / کشور: 2018

توضیحات

رشته های مرتبط مهندسی کامپیوتر
گرایش های مرتبط امنیت اطلاعات
مجله معاملات IEEE در رایانه ها – IEEE Transactions on Computers
دانشگاه J. W. Bos is with NXP Semiconductors – Leuven – Belgium
شناسه دیجیتال – doi https://doi.org/10.1109/TC.2018.2851238
منتشر شده در نشریه IEEE

Description

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.
اگر شما نسبت به این اثر یا عنوان محق هستید، لطفا از طریق "بخش تماس با ما" با ما تماس بگیرید و برای اطلاعات بیشتر، صفحه قوانین و مقررات را مطالعه نمایید.

دیدگاه کاربران


لطفا در این قسمت فقط نظر شخصی در مورد این عنوان را وارد نمایید و در صورتیکه مشکلی با دانلود یا استفاده از این فایل دارید در صفحه کاربری تیکت ثبت کنید.

بارگزاری