Using 5-isogenies to quintuple points on elliptic curves

Finding multiples of points on elliptic curves is the most important computation in elliptic curve cryptography. Extending the work of C. Doche, T. Icart, and D. Kohel (Efficient scalar multiplication by isogeny decomposition, in: M. Yung, Y. Dodis, A. Kiayias, T.G. Malkin (Eds.), Public Key Cryptography 2006, in: Lecture Notes in Comput. Sci., vol. 3958, Springer, Heidelberg, 2006, pp. 191–206) we use 5-isogenies to compute multiples of a point on an elliptic curve. Specifically, we find explicit formulas for quintupling a point. We compare the results with other published formulas for quintupling. We find that when the point is represented in Jacobian coordinates with z=1z=1, our method is potentially among the fastest on specially chosen elliptic curves. We also see that using l-isogenies to compute the multiplication by l map (for l larger than five) is unlikely to be more efficient than other techniques.

Research highlights► Point multiplication is a key computation in elliptic curve cryptography. ► Isogenies have been used to double and triple points efficiently. ► We use 5-isogenies to find formulas for quintupling a point. ► In special cases, this technique is competitive with other methods. ► It is unlikely higher degree isogenies can be efficiently utilized.