Paper 2023/1511
Lower bound of costs of formulas to compute image curves of $3$isogenies in the framework of generalized Montgomery coordinates
Abstract
In 2022, Moriya, Onuki, Aikawa, and Takagi proposed a new framework named generalized Montgomery coordinates to treat onecoordinate type formulas to compute isogenies. This framework generalizes some already known onecoordinate 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)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 isogenybased cryptographyVelu's formulaselliptic curvesgeneralized Montgomery coordinates
 Contact author(s)

t moriya @ bham ac uk
onuki @ mist i utokyo ac jp
aikawa @ mist i utokyo ac jp
takagi @ mist i utokyo ac jp  History
 20231006: approved
 20231003: 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}, url = {https://eprint.iacr.org/2023/1511} }