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.
