International Association
for Cryptologic Research

The present article provides a novel hash function $${\mathcal {H}}$$ H to any elliptic curve of j -invariant $$\ne 0, 1728$$ ≠ 0 , 1728 over a finite field $${\mathbb {F}}_{\!q}$$ F q of large characteristic. The unique bottleneck of $${\mathcal {H}}$$ H consists of extracting a square root in $${\mathbb {F}}_{\!q}$$ F q as well as for most hash functions. However, $${\mathcal {H}}$$ 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}$$ F q is highly 2-adic and $$q \equiv 1 \ (\textrm{mod} \ 3)$$ q ≡ 1 ( 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)$$ ≈ 2 log 2 ( q ) multiplications in $${\mathbb {F}}_{\!q}$$ F q . In turn, original Tonelli–Shanks’s square root algorithm and all of its subsequent modifications have the algebraic complexity $$\varTheta (\log (q) + g(\nu ))$$ Θ ( log ( q ) + g ( ν ) ) , where $$\nu $$ ν is the 2-adicity of $${\mathbb {F}}_{\!q}$$ F q and a function $$g(\nu ) \ne O(\nu )$$ g ( ν ) ≠ O ( ν ) . As an example, it is shown that Müller’s algorithm actually needs several times fewer multiplications in the field $${\mathbb {F}}_{\!q}$$ F q (whose $$\nu = 96$$ ν = 96 ) of the standardized curve NIST P-224.