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

The present article provides a novel hash function $\mathcal{H}$ to any elliptic curve of $j$-invariant $\neq 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\u27s 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\u27s algorithm costs $\approx 2\log_2(q)$ multiplications in $\mathbb{F}_{\!q}$. In turn, original Tonelli--Shanks\u27s square root algorithm and all of its subsequent modifications have the asymptotic complexity $\Theta(\log(q) + g(\nu))$, where $\nu$ is the $2$-adicity of $\mathbb{F}_{\!q}$ and a function $g(\nu) \neq O(\nu)$. As an example, it is shown that Müller’s algorithm actually needs several times fewer multiplications in the field $\mathbb{F}_{\!q}$ (whose $\nu = 96$) of the standardized curve NIST P-224