Paper 2022/150

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

Tomoki Moriya
Hiroshi Onuki
Yusuke Aikawa
Tsuyoshi Takagi
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 $\sqrt{\vphantom{2}}$\'{e}lu's formula in our implementation. The second one is the construction of a new generalized Montgomery coordinate for Montgomery$^-$ curves used for CSURF.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
isogeny-based cryptographyVelu's formulaselliptic curvesgeneralized Montgomery coordinates
Contact author(s)
tomoki_moriya @ mist i u-tokyo ac jp
History
2023-08-08: last of 4 revisions
2022-02-12: received
See all versions
Short URL
https://ia.cr/2022/150
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/150,
      author = {Tomoki Moriya and Hiroshi Onuki and Yusuke Aikawa and Tsuyoshi Takagi},
      title = {The Generalized Montgomery Coordinate: A New Computational Tool for Isogeny-based Cryptography},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/150},
      year = {2022},
      url = {https://eprint.iacr.org/2022/150}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.