Lower bound of costs of formulas to compute image curves of $3$-isogenies in the framework of generalized Montgomery coordinates

Tomoki Moriya; Hiroshi Onuki; Yusuke Aikawa; Tsuyoshi Takagi

Paper 2023/1511

Lower bound of costs of formulas to compute image curves of $3$-isogenies in the framework of generalized Montgomery coordinates

Tomoki Moriya

, University of Birmingham

Hiroshi Onuki

, University of Tokyo

Yusuke Aikawa, University of Tokyo

Tsuyoshi Takagi, University of Tokyo

Abstract

In 2022, Moriya, Onuki, Aikawa, and Takagi proposed a new framework named generalized Montgomery coordinates to treat one-coordinate type formulas to compute isogenies. This framework generalizes some already known one-coordinate type formulas of elliptic curves. Their result shows that a formula to compute image points under isogenies is unique in the framework of generalized Montogmery coordinates; however, a formula to compute image curves is not unique. Therefore, we have a question: What formula is the most efficient to compute image curves in the framework of generalized Montogmery coordinates? In this paper, we analyze the costs of formulas to compute image curves of $3$-isogenies in the framework of generalized Montgomery coordinates. From our result, the lower bound of the costs is $1\mathbf{M}+1\mathbf{S}$ as a formula whose output and input are in affine coordinates, $2\mathbf{S}$ as an affine formula whose output is projective, and $2\mathbf{M}+3\mathbf{S}$ as a projective formula.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: isogeny-based cryptography Velu's formulas elliptic curves generalized Montgomery coordinates
Contact author(s): t moriya @ bham ac uk
onuki @ mist i u-tokyo ac jp
aikawa @ mist i u-tokyo ac jp
takagi @ mist i u-tokyo ac jp
History: 2023-10-06: approved; 2023-10-03: received; See all versions
Short URL: https://ia.cr/2023/1511
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1511,
      author = {Tomoki Moriya and Hiroshi Onuki and Yusuke Aikawa and Tsuyoshi Takagi},
      title = {Lower bound of costs of formulas to compute image curves of $3$-isogenies in the framework of generalized Montgomery coordinates},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1511},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1511}},
      url = {https://eprint.iacr.org/2023/1511}
}