Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / Velu's formulas, Montgomery form, 2-isogenies, Post-quantum crypto, Isogeny-based crypto

Original Publication (with minor differences): PQCrypto 2018

Date: received 12 Dec 2017, last revised 30 May 2018

Contact author: j renes at cs ru nl

Available format(s): PDF | BibTeX Citation

Version: 20180530:131250 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]