Cryptology ePrint Archive: Report 2020/526

Efficient Montgomery-like formulas for general Huff's and Huff's elliptic curves and their applications to the isogeny-based cryptography

Robert Dryło and Tomasz Kijko and Michał Wroński

Abstract: In this paper for elliptic curves provided by Huff's equation $H_{a,b}: ax(y^2-1) = by(x^2-1)$ and general Huff's equation $G_{\overline{a},\overline{b}}\ :\ {\overline{x}}(\overline{a}{\overline{y}}^2-1)={\overline{y}}(\overline{b}{\overline{x}}^2-1)$ and degree 2 compression function $f(x,y) = xy$ on these curves, herein we provide formulas for doubling and differential addition after compression, which for Huff's curves are as efficient as Montgomery's formulas for Montgomery's curves $By^2 = x^3 + Ax^2 + x$. For these curves we also provided point recovery formulas after compression, which for a point $P$ on these curves allows to compute $[n]f(P)$ after compression using the Montgomery ladder algorithm, and then recover $[n]P$. Using formulas of Moody and Shumow for computing odd degree isogenies on general Huff's curves, we have also provide formulas for computing odd degree isogenies after compression for these curves. Moreover, it is shown herein how to apply obtained formulas using compression to the ECM algorithm. In the appendix, we present examples of Huff's curves convenient for the isogeny-based cryptography, where compression can be used.

Category / Keywords: public-key cryptography / general Huff's curves and Huff's curves and compression on elliptic curves and isogeny-based cryptography and ECM method

Date: received 5 May 2020, last revised 15 Jul 2020

Contact author: robert drylo at wat edu pl,tomasz kijko@wat edu pl,michal wronski@wat edu pl

Available format(s): PDF | BibTeX Citation

Version: 20200715:101204 (All versions of this report)

Short URL: ia.cr/2020/526


[ Cryptology ePrint archive ]