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: Montgomery's formulas for doubling and differential addition in $x$-coordinates for elliptic curves $By^2 = x^3 + Ax^2 + x$ are among the most efficient formulas for point multiplication after compression. In general, if $E$ is an elliptic curve over a field $K$, then a degree 2 function $f:E\to K$ such that $f(P) = f(-P)$ for $P\in E$ can be used as a compression and there exist analogous formulas for doubling and differential addition of values $f$ which can be used in the Montgomery ladder algorithm to compute multiplication $[n]f(P) = f([n]P)$ for $n\in \mathbb N$. In this paper we give formulas for doubling and differential addition of the same or similar efficiency as Montgomery's for Huff's and general Huff's curves of odd characteristic and degree 2 compression, which seems to be new for these models of elliptic curves. Additionally, we give formulas for point recovery after compression. We also found efficient formulas for general odd-isogeny computation on Huff's curves and we showed how to apply obtained formulas, especially, to the isogeny based cryptography. Moreover, it was showed how to apply obtained by us formulas using compression to the ECM algorithm. In appendix, we present examples of convenient cryptographic Huff's curves, where presented compression techniques 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

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: 20200505:172532 (All versions of this report)

Short URL: ia.cr/2020/526


[ Cryptology ePrint archive ]