Paper 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.