Paper 2017/1198

Computing isogenies between Montgomery curves using the action of (0,0)

Joost Renes

Abstract

A recent paper by Costello and Hisil at Asiacrypt'17 presents efficient formulas for computing isogenies with odd-degree cyclic kernels on Montgomery curves. We provide a constructive proof of a generalization of this theorem which shows the connection between the shape of the isogeny and the simple action of the point (0,0). This generalization removes the restriction of a cyclic kernel and allows for any separable isogeny whose kernel does not contain (0,0). As a particular case, we provide efficient formulas for 2-isogenies between Montgomery curves and show that these formulas can be used in isogeny-based cryptosystems without expensive square root computations and without knowledge of a special point of order 8. We also consider elliptic curves in triangular form containing an explicit point of order 3.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. PQCrypto 2018
Keywords
Velu's formulasMontgomery form2-isogeniesPost-quantum cryptoIsogeny-based crypto
Contact author(s)
j renes @ cs ru nl
History
2018-07-27: last of 3 revisions
2017-12-18: received
See all versions
Short URL
https://ia.cr/2017/1198
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1198,
      author = {Joost Renes},
      title = {Computing isogenies between Montgomery curves using the action of (0,0)},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1198},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1198}},
      url = {https://eprint.iacr.org/2017/1198}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.