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

Tomoki Moriya*, Hiroshi Onuki, Yusuke Aikawa, Tsuyoshi Takagi

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

43 Downloads (Pure)

Abstract

Recently, some studies have constructed one-coordinate arithmetics on elliptic curves. For example, formulas of the 𝑥-coordinate of Montgomery curves, 𝑥-coordinate of Montgomery− curves, 𝑤-coordinate of Edwards curves, 𝑤-coordinate of Huff’s curves, 𝜔-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√élu’s formula in our implementation. The second one is the construction of a new generalized Montgomery coordinate for Montgomery−curves used for CSURF.
Original languageEnglish
Pages (from-to)36-59
Number of pages24
JournalMathematical Cryptology
Volume2
Issue number1
Publication statusPublished - 4 Oct 2022

Keywords

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

Fingerprint

Dive into the research topics of 'The Generalized Montgomery Coordinate: A New Computational Tool for Isogeny-based Cryptography'. Together they form a unique fingerprint.

Cite this