Paper 2023/121

Hashing to elliptic curves over highly $2$-adic fields $\mathbb{F}_{\!q}$ with $O(\log(q))$ operations in $\mathbb{F}_{\!q}$

Abstract

The current article provides a new deterministic hash function $\mathcal{H}$ to almost any elliptic curve $E$ over a finite field $\mathbb{F}_{\!q}$, having an $\mathbb{F}_{\!q}$-isogeny of degree $3$. Since $\mathcal{H}$ just has to compute a certain Lucas sequence element, its complexity always equals $O(\log(q))$ operations in $\mathbb{F}_{\!q}$ with a small constant hidden in $O$. In comparison, whenever $q \equiv 1 \ (\mathrm{mod} \ 3)$, almost all previous hash functions need to extract at least one square root in $\mathbb{F}_{\!q}$. Over the field $\mathbb{F}_{\!q}$ of $2$-adicity $\nu$ this amounts to $O(\log(q) + \nu^2)$ operations in $\mathbb{F}_{\!q}$ for the Tonelli--Shanks algorithm and $O(\log(q) + \nu^{3/2})$ ones for the recent Sarkar algorithm. A detailed analysis shows that $\mathcal{H}$ is several times faster than earlier state-of-the-art hash functions to the curve NIST P-224 (for which $\nu = 96$) from the American standard NIST SP 800-186.