Paper 2021/1082

Some remarks on how to hash faster onto elliptic curves

Abstract

This article proposes four optimizations of indifferentiable hashing onto (prime-order subgroups of) ordinary elliptic curves over finite fields $\mathbb{F}_{\!q}$. One of them is dedicated to elliptic curves $E$ without non-trivial automorphisms provided that $q \equiv 2 \ (\mathrm{mod} \ 3)$. The second deals with $q \equiv 2, 4 \ (\mathrm{mod} \ 7)$ and an elliptic curve $E_7$ of $j$-invariant $-3^3 5^3$. The corresponding section plays a rather theoretical role, because (the quadratic twist of) $E_7$ is not used in real-world cryptography. The other two optimizations take place for the subgroups $\mathbb{G}_1$, $\mathbb{G}_2$ of pairing-friendly curves. The performance gain comes from the smaller number of required exponentiations in $\mathbb{F}_{\!q}$ for hashing to $E(\mathbb{F}_{\!q})$, $E_7(\mathbb{F}_{\!q})$, and $\mathbb{G}_2$ as well as from the absence of necessity to hash directly onto $\mathbb{G}_1$ in certain settings. In particular, the last insight allows to drastically speed up verification of the aggregate BLS signature incorporated in many blockchain technologies. The new results affect, for example, the pairing-friendly curve BLS12-381 (the most popular in practice at the moment) and a few plain curves from the American standard NIST SP 800-186. Among other things, a taxonomy of state-of-the-art hash functions to elliptic curves is presented. Finally, the article discusses how to hash over highly $2$-adic fields $\mathbb{F}_{\!q}$.