دانلود رایگان مقاله انگلیسی ملاحظات حسابگرانه برای رمزنگاری مبتنی بر ایزوژنتیک - IEEE 2018

Abstract

In this paper we investigate various arithmetic techniques which can be used to potentially enhance the performance in the supersingular isogeny Diffie-Hellman (SIDH) key-exchange protocol which is one of the more recent contenders in the post-quantum public-key arena. Firstly, we give a systematic overview of techniques to compute efficient arithmetic modulo 2 xp y ± 1. Our overview shows that in the SIDH setting, where arithmetic over a quadratic extension field is required, the approaches based on the Montgomery reduction for such primes of a special shape are to be preferred. Moreover, the outcome of our investigation reveals that there exist moduli which allow even faster implementations. Secondly, we investigate if it is beneficial to use other curve models to speed up the elliptic curve scalar multiplication. The use of twisted Edwards curves allows one to search for efficient addition-subtraction chains for fixed scalars while this is not possible with the differential addition law when using Montgomery curves. Our preliminary results show that despite the fact that we found such efficient chains, using twisted Edwards curves does not result in faster scalar multiplication arithmetic in the setting of SIDH.

5 CONCLUSIONS AND FUTURE WORK

We have studied various arithmetic properties which are useful for enhancing the performance in a recent postquantum key encapsulation candidate based on the hardness of constructing an isogeny between two isogenous supersingular elliptic curves defined over a finite field. We have provided an overview of different techniques to compute arithmetic modulo 2 xp y ± 1. Although we have surveyed this in more generality it turns out that the noninterleaved Montgomery reduction which is optimized for such primes is the most efficient approach in practice. Additionally, we have identified other moduli suitable for SIDH which allow even faster implementations. Furthermore, we have analyzed the relative costs of Montgomery curves and the twisted Edwards family of curves which allows precomputing more efficient addition chains. We found multiple efficient addition-subtraction chains for the scalar powers required in the key encapsulation mechanism computation. However, based on these results we have to conclude that these more efficient chains cannot compensate for the more expensive group law in twisted Edwards curves.

Incorporating such efficient addition-subtraction chains into the computation of the isogeny tree presents an interesting challenge because the algorithm for calculating the optimal tree given by Jao and De Feo [21] cannot be easily generalized to arbitrary steps since the problem becomes much harder.