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

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

**Abstract: **Isogeny-based cryptography is one of the main candidates of post-quantum cryptography. To realize efficient computations, one usually uses formulas of scalar multiplications and isogeny computations on elliptic curves using only one coordinate in isogeny-based cryptography. The $x$-coordinate of Montgomery curves is the most standard, and we sometimes use the $x$-coordinate of Montgomery$^-$ curves, the $w$-coordinate of Edwards curves, and the $w$-coordinate of Huff's curves.

In this paper, we define a novel function on elliptic curves called the generalized Montgomery coordinate that has the four coordinates described above as special cases. For a generalized Montgomery coordinate, we construct an explicit formula of scalar multiplication which 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 expect numerous applications for the generalized Montgomery coefficient. As an experimental study, we present two applications of the theory of a generalized Montgomery coordinate. The first one is to construct 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}}$élu's formula in our implementation. The second one is to construct a new generalized Montgomery coordinate for Montgomery$^-$ curves used for CSURF.

**Category / Keywords: **public-key cryptography / isogeny-based cryptography, Velu's formulas, elliptic curves, generalized Montgomery coordinates

**Date: **received 10 Feb 2022

**Contact author: **tomoki_moriya at mist i u-tokyo ac jp

**Available format(s): **PDF | BibTeX Citation

**Version: **20220212:064653 (All versions of this report)

**Short URL: **ia.cr/2022/150

[ Cryptology ePrint archive ]