Paper 2023/390

Hashing to elliptic curves through Cipolla–Lehmer–Müller’s square root algorithm

Abstract

The present article provides a novel hash function $\mathcal{H}$ to any elliptic curve of $j$-invariant $\ne 0,1728$ over a finite field ${\mathbb{F}}_q$ of large characteristic. The unique bottleneck of $\mathcal{H}$ consists in extracting a square root in ${\mathbb{F}}_q$ as well as for most hash functions. However, $\mathcal{H}$ is designed in such a way that the root can be found by (Cipolla--Lehmer--)Müller's algorithm in constant time. Violation of this security condition is known to be the only obstacle to applying the given algorithm in the cryptographic context. When the field ${\mathbb{F}}_q$ is highly $2$-adic and $q\equiv 1(\mathrm{mod}3)$, the new batching technique is the state-of-the-art hashing solution except for some sporadic curves. Indeed, Müller's algorithm costs $\approx 2{\log }_2(q)$ multiplications in ${\mathbb{F}}_q$. In turn, original Tonelli--Shanks's square root algorithm and all of its subsequent modifications have the asymptotic complexity $$, where $$ is the $$-adicity of $$ and a function $$. As an example, it is shown that Müller’s algorithm actually needs several times fewer multiplications in the field $$ (whose $$) of the standardized curve NIST P-224.