The Generalized Montgomery Coordinate: A New Computational Tool for Isogeny-based Cryptography

Abstract

Recently, some studies have constructed one-coordinate arithmetics on elliptic curves. For example, formulas of the x-coordinate of Montgomery curves, x-coordinate of Montgomery^- curves, w-coordinate of Edwards curves, w-coordinate of Huff’s curves, \omega-coordinates of twisted Jacobi intersections have been proposed. These formulas are useful for isogeny-based cryptography because of their compactness and efficiency.
In this paper, we define a novel function on elliptic curves called the generalized Montgomery coordinate that has the five coordinates described above as special cases. For a generalized Montgomery coordinate, we construct an explicit formula of scalar multiplication that includes the division polynomial, and both a formula of an image point under an isogeny and that of a coefficient of the codomain curve.
Finally, we present two applications of the theory of a generalized Montgomery coordinate. The first one is the construction of a new efficient formula to compute isogenies on Montgomery curves. This formula is more efficient than the previous one for high degree isogenies as the Vélu’s formula in our implementation. The second one is the construction of a new generalized Montgomery coordinate for Montgomery^- curves used for CSURF.