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

Keywords

isogeny-based cryptography
Vélu’s formulas
elliptic curves
Kummer line
generalized Montgomery coordinates

How to Cite

Moriya, T., Onuki, H., Aikawa, Y., & Takagi, T. (2022). The Generalized Montgomery Coordinate: A New Computational Tool for Isogeny-based Cryptography. Mathematical Cryptology, 2(1), 36–59. Retrieved from https://ojs.test.flvc.org/mathcryptology/article/view/132126

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.

PDF
Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Copyright (c) 2022 Tomoki Moriya, Hiroshi Onuki, Yusuke Aikawa, Tsuyoshi Takagi