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.