Paper 2022/150
The Generalized Montgomery Coordinate: A New Computational Tool for Isogenybased Cryptography
Abstract
Recently, some studies have constructed onecoordinate 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 isogenybased 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.
Note: The part about theta coordinates in Introduction may be wrong. After we understand the relationship between our theory and that of theta coordinates correctly, we'll rewrite them.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint.
 Keywords
 isogenybased cryptographyVelu's formulaselliptic curvesgeneralized Montgomery coordinates
 Contact author(s)
 tomoki_moriya @ mist i utokyo ac jp
 History
 20230426: last of 3 revisions
 20220212: received
 See all versions
 Short URL
 https://ia.cr/2022/150
 License

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 Isogenybased Cryptography}, howpublished = {Cryptology ePrint Archive, Paper 2022/150}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/150}}, url = {https://eprint.iacr.org/2022/150} }