Indifferentiable hashing to ordinary elliptic \(\mathbb{F}_{q} \)-curves of \(j=0\) with the cost of one exponentiation in \(\mathbb{F}_{q} \) (Q2115746)

On of the most important branches of elliptic curve cryptography is the pairing cryptography, especially in secure multi-party computations. It uses mainly elliptic curves \(E_b : y^2 = x^3+b\) defined over finite fields \(\mbox{F}_q \) of characteristic \(> 3\) whose the \(j\)-invariant is 0, since the pairing computations on them is the most efficient. Many pairing-based protocols (for example, the BLS multi-signature scheme) use a hash function of the form \(H : \{0, 1\}^* \rightarrow E_b(\mbox{F}_q)\). It is desirable that \(H\) is indifferentiable from a random oracle and constant time, that is the computation time of its value is independent of an input argument. All such previously proposed hash functions compute two exponentiations in \(\mbox{F}_q\). In this paper, provided that \(\sqrt{b}\in \mbox{F}_q\) and \(q \not \equiv 1\ (\bmod\ 27)\), a new constant-time hash function \(H : \{0, 1\}^* \rightarrow E_b(\mbox{F}_q)\) indifferentiable from a random oracle is proposed which computes only one exponentiation in \(\mbox{F}_q\). Note that this work essentially improves the ideas of the author presented in [``Efficient indifferentiable hashing to elliptic curves \(y^2 = x^3 + b\) provided that \(b\) is a quadratic residue'', Preprint, \url{https://eprint.iacr.org/2020/1070}].