1 Introduction

Since its invention in the early 2000s, pairing-based cryptography [8] has become more and more popular every year, for example in secure multi-party computations. One of the latest reviews of standards, commercial products and libraries for this type of cryptography is represented in [15, Sect. 4.1].

Let \({\mathbb {F}}_{\!q}\) be a finite field of \(\mathrm {char}({\mathbb {F}}_{\!q}) > 3\) and \(E_b\!: y^2 = x^3 + b\) be an elliptic \({\mathbb {F}}_{\!q}\)-curve whose the j-invariant is 0. The priority is given to the curves \(E_b\), because the pairing computation on them is the most efficient (see [8, Sect. 4]). The paper’s focus is on ordinary curves, because supersingular ones pose special challenges for security by virtue of [8, Remark 2.22]. And according to [18, Example V.4.4] the ordinariness of \(E_b\) results in the restriction \(q \equiv 1 \ (\mathrm {mod} \ 3)\), i.e., \(\omega := \root 3 \of {1} \in {\mathbb {F}}_{\!q}\), where \(\omega \ne 1\). Today, the most popular pairing-friendly curve in the industry is the Barreto–Lynn–Scott curve BLS12-381 [22, Sect. 2.1] for which \(\lceil \log _2(q) \rceil = 381\).

Many pairing-based protocols (for example, the BLS multi-signature [2, Sect. 3], [3]) use a hash function of the form \(H\!: \{0,1\}^* \rightarrow E_b({\mathbb {F}}_{\!q})\). There is the regularly updated draft [9] (see also [8, Sect. 8]) on the topic of hashing to elliptic curves. Due to [9, Sect. 10] it is highly desirable and often inevitable that H is indifferentiable from a random oracle [4, Definition 2] and constant-time, that is the computation time of its value is independent of an input argument.

Almost all such previously proposed hash functions are obtained as the composition \(H := e^{\otimes 2} \circ {\mathfrak {h}}\) of a hash function \({\mathfrak {h}}\!: \{0,1\}^* \rightarrow {\mathbb {F}}_{\!q}^2\) and the tensor square

$$\begin{aligned} e^{\otimes 2}\!: {\mathbb {F}}_{\!q}^2 \rightarrow E_b({\mathbb {F}}_{\!q}) \qquad e^{\otimes 2}(t_1,t_2) := e(t_1) + e(t_2) \end{aligned}$$

of some map \(e\!: {\mathbb {F}}_{\!q} \rightarrow E_b({\mathbb {F}}_{\!q})\). Such a map is often called encoding. In this case the indifferentiability of H follows from [4, Theorem 1] if \({\mathfrak {h}}\) is indifferentiable and \(e^{\otimes 2}\) is admissible in the sense of [4, Definition 4].

The fastest known encodings to the curves \(E_b\) are Elligator 2 [1, Sect. 5] and the Wahby–Boneh “indirect” map [22] (building on the simplified SWU map [4, Sect. 7]). Both (resp. H) can be implemented with the cost of one (resp. two) exponentiation(s) in \({\mathbb {F}}_{\!q}\) whenever \(q \not \equiv 1 \, (\mathrm {mod} \ 8)\). The other quite famous Icart encoding [11] is available if and only if \(q \equiv 2 \ (\mathrm {mod} \ 3)\), i.e., it is useless in the pairing context. The Icart approach is based on the fact that under the mentioned condition there is a unique cubic root \(\root 3 \of {a} \in {\mathbb {F}}_{\!q}\) given \(a \in {\mathbb {F}}_{\!q}\). Nevertheless, as is shown by this article, the cubic root ideology also works (in a completely different way) in the opposite case \(q \equiv 1 \ (\mathrm {mod} \ 3)\).

This article essentially improves our ideas from [12]. There provided that \(\sqrt{b}\in {\mathbb {F}}_{\!q}\) we construct one more encoding e whose the tensor square \(e^{\otimes 2}\) is admissible. Moreover, e equally requires only one exponentiation in \({\mathbb {F}}_{\!q}\). However in this work (also for \(\sqrt{b}\in {\mathbb {F}}_{\!q}\)) we directly provide an admissible map \(h\!: {\mathbb {F}}_{\!q}^2 \rightarrow E_b({\mathbb {F}}_{\!q})\) approximately with the same cost as e and such that \(h(t,t) = \pm e(t)\). In other words, the tensor square is superfluous in this situation and hence we get rid of one exponentiation in \({\mathbb {F}}_{\!q}\). Let us also remark that h is given by quite simple formulas with small coefficients unlike the Wahby–Boneh encoding.

The same idea is applicable to the famous SWU (Shallue–van de Woestijne–Ulas) encoding [8, Sect. 8.3.4] with the cost of two exponentiations in \({\mathbb {F}}_{\!q}\). It is based on the seminal work [19, Lemma 3] of Skałba, where the author derives a map \({\mathbb {F}}_{\!q}^2 \rightarrow E({\mathbb {F}}_{\!q})\) for any elliptic \({\mathbb {F}}_{\!q}\)-curve E of \(j(E) \ne 0\). The research society refused this map, because it is determined by fairly cumbersome formulas in comparison with those of the SWU encoding. This article restores justice by implicitly showing that the result of Skałba is more valuable than its refinements of Shallue, van de Woestijne, and Ulas. Nevertheless, it still remains open the existence question of an indifferentiable hash function to the ordinary curve E with the cost of one exponentiation in \({\mathbb {F}}_{\!q}\).

2 Geometric results

As mentioned above, we are only interested in \(q \equiv 1 \ (\mathrm {mod} \ 3)\), i.e., \(\omega := \root 3 \of {1} \in {\mathbb {F}}_{\!q}^*\), where \(\omega \ne 1\). Consider the two different cubic \({\mathbb {F}}_{\!q}\)-twists \(E_b^{(j)}\) (for \(j \in \{1,2\}\)) of the given curve \(E_b = E_b^{(0)}\). There is on \(E_b^{(i)} \subset {\mathbb {A}}^{\!2}_{(x_i,y_i)}\) (for \(i \in \{0,1,2\}\)) the \({\mathbb {F}}_{\!q}\)-automorphism \([\omega ](x_i,y_i) := (\omega x_i, y_i)\) of order 3. Take the quotient \(T := (E_b \!\times \! E_b^{(1)} \!\times \! E_b^{(2)})/[\omega ]^{\times 3}\) with respect to the diagonal action of \([\omega ]\). This is a Calabi–Yau threefold according to [14, Sect. 1.3]. By the way, the SWU encoding (as well as Skałba’s map) deals with another Calabi–Yau \({\mathbb {F}}_{\!q}\)-threefold.

Without loss of generality, suppose that \(\root 3 \of {b}\not \in {\mathbb {F}}_{\!q}\). In the opposite case, one can start from \(E_b^{(1)}\) or \(E_b^{(2)}\) (see details in Appendix). Under our assumption, the elliptic curves are determined by the equations \(E_b^{(i)}\!: y^2_i = b^ix_i^3 + b \simeq _{{\mathbb {F}}_{\!q}} E_{b^{2i + 1}}\). The next lemma is proved in a similar way as [5, Lemma 2.1].

Lemma 1

At least up to a birational \({\mathbb {F}}_{\!q}\)-isomorphism, T has the affine model

$$\begin{aligned} T\!: {\left\{ \begin{array}{ll} y_1^2 - b = b (y_0^2 - b) t_1^3, \\ y_2^2 - b = b^2 (y_0^2 - b) t_2^3 \end{array}\right. } \ \subset \quad {\mathbb {A}}^{\!5}_{(y_0,y_1,y_2,t_1,t_2)}, \end{aligned}$$

where \(t_j := x_j/x_0\).

We can look at T as a curve in \({\mathbb {A}}^{\!3}_{(y_0,y_1,y_2)}\) given as the intersection of two quadratic surfaces over \({\mathbb {F}}_{\!q}(t_1, t_2)\), where the latter denotes the rational function field in two variables \(t_1, t_2\) over the constant field \({\mathbb {F}}_{\!q}\). Nevertheless, below it will be more convenient to work over the subfield \(F := {\mathbb {F}}_{\!q}(s_1, s_2)\), where \(s_j := t_j^3\).

Throughout the paper we rely on some Magma calculations [13] that can be verified in the free calculator on the official site of this computer algebra system.

Lemma 2

[13] T/F is an elliptic curve having a short Weierstrass form \(W\!: y^2 = x^3 + a_4x + a_6\) with the coefficients

$$\begin{aligned} \begin{array}{l} a_4 := -3(b^2 s_1s_2 + \omega ^2 s_1 + \omega bs_2)(b^2 s_1s_2 + \omega s_1 + \omega ^2 bs_2), \\ a_6 := -(b^2 s_1s_2 - 2s_1 + bs_2)(2b^2 s_1s_2 - s_1 - bs_2)(b^2 s_1s_2 + s_1 - 2bs_2). \end{array} \end{aligned}$$

In particular, the discriminant and j-invariant of W equal

$$\begin{aligned} \begin{array}{l} \Delta = \big ( 2^2 3^3bs_1s_2 (bs_1 - 1)(b^2 s_2 - 1)(s_1 - bs_2) \big )^2, \\ j = \big ( 2^4 3^2 ( b^2 s_1 s_2 + \omega s_1 + \omega ^2 b s_2 ) ( b^2 s_1 s_2 + \omega ^2 s_1 + \omega b s_2 ) \big )^3 / \Delta . \end{array} \end{aligned}$$

Theorem 1

[13] There is a point \(\psi \in W(F)\) with the coordinates

$$\begin{aligned} x = b(2bs_1 - 1)s_2 - (3bs_1 - 2)s_1, \qquad y = 3\sqrt{b}(2\omega + 1) s_1(bs_1 - 1)(bs_2 - s_1). \end{aligned}$$

It corresponds to a point \(\varphi \in T(F)\) whose the coordinates are the irreducible fractions \(y_i(t_1,t_2) := \mathrm {num}_i/\mathrm {den}\), where

$$\begin{aligned} \mathrm {num}_0&:= \sqrt{b} \cdot \! \big ( b^2 s_1^2 - 2b^3 s_1 s_2 + 2b s_1 + b^4 s_2^2 + 2b^2 s_2 - 3 \big ), \\ \mathrm {num}_1&:= \sqrt{b} \cdot \! \big ( {-}3b^2 s_1^2 + 2b^3 s_1 s_2 + 2b s_1 + b^4 s_2^2 - 2b^2 s_2 + 1 \big ), \\ \mathrm {num}_2&:= \sqrt{b} \cdot \! \big ( b^2 s_1^2 + 2b^3 s_1 s_2 - 2b s_1 - 3b^4 s_2^2 + 2b^2 s_2 + 1 \big ), \\ \mathrm {den}&:= b^2 s_1^2 - 2b^3 s_1 s_2 - 2b s_1 + b^4 s_2^2 - 2b^2 s_2 + 1. \end{aligned}$$

Moreover, \(\sum _{i=0}^2 y_i(t_1,t_2) + \sqrt{b} = 0\).

It is remarkable that the functions \(y_i(t,t)\) are nothing but (up to the minus sign) those from [12, Theorem 1]. Besides, the important case \(b=4\) gives

$$\begin{aligned} \begin{aligned} \mathrm {num}_0&= 2 \!\cdot \!\big ( 2^4 s_1^2 - 2^7 s_1 s_2 + 2^3 s_1 + 2^8 s_2^2 + 2^5 s_2 - 3 \big ), \\ \mathrm {num}_1&= 2 \!\cdot \!\big ( {-}2^4 3 s_1^2 + 2^7 s_1 s_2 + 2^3 s_1 + 2^8 s_2^2 - 2^5 s_2 + 1 \big ), \\ \mathrm {num}_2&= 2 \!\cdot \!\big ( 2^4 s_1^2 + 2^7 s_1 s_2 - 2^3 s_1 - 2^8 3 s_2^2 + 2^5 s_2 + 1 \big ), \\ \mathrm {den}&= 2^4 s_1^2 - 2^7 s_1 s_2 - 2^3 s_1 + 2^8 s_2^2 - 2^5 s_2 + 1. \end{aligned} \end{aligned}$$

In other words, \(T/{\mathbb {F}}_{\!q}\) is an elliptic threefold whose the elliptic fibration is the projection to \(t_1, t_2\). In these terms, \(\varphi \!: {\mathbb {A}}^{\!2}_{(t_1,t_2)} \dashrightarrow T\) is an \({\mathbb {F}}_{\!q}\)-section of the given fibration. In particular, \(\mathrm {Im}(\varphi )\) is a rational \({\mathbb {F}}_{\!q}\)-surface. In turn, W is a global minimal Weierstrass form for T. These and other notions of the theory of elliptic threefolds see, e.g., in [10]. For completeness, the much simpler theory of elliptic surfaces is well represented in [17].

If the point \(\phi _0 := \big ( \sqrt{b}, \sqrt{b}, \sqrt{b}\,\big )\) is chosen as the neutral element of the Mordell–Weil group T(F), then as shown in [13] its 2-torsion subgroup \(T(F)[2] = \{ \phi _i \}_{i=0}^3\), where

$$\begin{aligned} \phi _1 := \big ( \sqrt{b}, -\sqrt{b}, -\sqrt{b}\,\big ), \qquad \phi _2 := \big ( {-}\sqrt{b}, \sqrt{b}, -\sqrt{b}\,\big ), \qquad \phi _3 := \big ( {-}\sqrt{b}, -\sqrt{b}, \sqrt{b}\,\big ). \end{aligned}$$

The next theorem clarifies why \(\psi \) has the simplest coordinates among infinite order points from W(F).

Theorem 2

Consider F as the rational function field \(k_1(s_2)\) (resp. \(k_2(s_1))\) over the constant field \(k_1 := {\mathbb {F}}_{\!q}(s_1)\) (resp. \(k_2 := {\mathbb {F}}_{\!q}(s_2))\). Then, taking into account the lattice structure with respect to the height pairing,

$$\begin{aligned} T(F) \simeq W(F) \simeq \mathrm {A}_1^{\!*} \oplus ({\mathbb {Z}}/2)^2, \qquad \text {moreover}, \qquad W(F)/W(F)_{\mathrm {tor}} = \langle \psi \rangle . \end{aligned}$$

Proof

Since \(T/k_j\) is obviously a rational surface, \(W/k_j\) is also so. With the help of [13] we get that the singular fibers of the Kodaira–Néron model of \(W/k_j\) have the types \(\mathrm {I}_2, \mathrm {I}_2, \mathrm {I}_2, \mathrm {I}_0^*\) in Kodaira’s notation. Consequently \(W\big ( \overline{k_1}(s_2) \big ) \simeq W\big ( \overline{k_2}(s_1) \big ) \simeq \mathrm {A}_1^{\!*} \oplus ({\mathbb {Z}}/2)^2\) according to [17, Table 8.2]. Further, [13] allows to compute the canonical height of \(\psi \), which turns out to equal 1/2. This is also the minimal norm of the lattice \(\mathrm {A}_1^{\!*}\). Thus the theorem is proved. \(\square \)

We do not claim that \(T(F)/T(F)_{\mathrm {tor}} = \langle \varphi \rangle \) with respect to \(\phi _0\) as the neutral element of T(F), because this point does not correspond to that at infinity on W/F. We chose \(\phi _0\) just to describe T(F)[2] in a more canonical way.

For the sake of compactness we put

$$\begin{aligned} \beta := -3\sqrt{b}, \qquad \infty := (1:0) \in {\mathbb {P}}^1, \qquad P_0 := (0, \sqrt{b}) \in E_b, \qquad \mathcal {O}:= (0:1:0) \in E_b. \end{aligned}$$

Denote by \(\mathrm {Num}_i\) (resp. \(\mathrm {Den}\)) the homogenization of \(\mathrm {num}_i\) (resp. \(\mathrm {den}\)) with respect to a new variable \(t_0\). For \(y \in {\mathbb {F}}_{\!q}\) consider on \({\mathbb {P}}^2_{(t_0:t_1:t_2)}\) the pencil of the \({\mathbb {F}}_{\!q}\)-sextics

$$\begin{aligned} C_{i,y}\!: \mathrm {Num}_i = \mathrm {Den}\!\cdot \!y, \qquad C_{i,\infty } = C_{\infty }\!: \mathrm {Den}= 0 \end{aligned}$$

and the \({\mathbb {F}}_{\!q}\)-conics \(D_{i,y} := \pi (C_{i,y})\), where

$$\begin{aligned} \pi \!: {\mathbb {P}}^2 \rightarrow {\mathbb {P}}^2 \qquad \pi (t_0 : t_1 : t_2) := (t_0^3 : t_1^3 : t_2^3). \end{aligned}$$

Also, let \(L_i\!: t_i = 0\),

$$\begin{aligned} R_0 := (1:0:0), \qquad R_1 := (0:1:0), \qquad R_2 := (0:0:1) \end{aligned}$$

and \({\mathbf {Q}}_k := \pi ^{-\!1}(Q_k)\), where

$$\begin{aligned} Q_{0} := (0 : b : 1), \qquad Q_{1} := (b^2 : 0 : 1), \qquad Q_{2} := (b : 1 : 0). \end{aligned}$$

Below we formulate a few simple lemmas, which are readily checked. By the way, the indices \(i \pm 1\) will always mean the operations ± modulo 3.

Lemma 3

The order 3 projective \({\mathbb {F}}_{\!q}\)-transformations

give the isomorphisms

as well as

$$\begin{aligned} \tau (R_i) = \tau ^\prime (R_i) = R_{i+1}, \qquad \tau ^\prime (Q_i) = Q_{i+1}. \end{aligned}$$

It is worth noting that the curves \(D_{i,\pm \sqrt{b}}\) (and hence \(C_{i,\pm \sqrt{b}}\)) are reducible over \({\mathbb {F}}_{\!q}\). Indeed,

$$\begin{aligned} D_{0, \sqrt{b}}\!: t_0(t_0 - b t_1 - b^2 t_2) = 0, \qquad D_{0, -\sqrt{b}}\!: (t_0 - b t_1 + b^2 t_2)(t_0 + b t_1 - b^2 t_2) = 0.\quad \end{aligned}$$
(1)

Lemma 4

There are the following equalities. First,

$$\begin{aligned} D_{i,y} \cap D_\infty = D_{i,0} \cap D_\infty = \{Q_k\}_{k=0}^2. \end{aligned}$$

Second,

$$\begin{aligned} D_{0,y} \cap D_{1,y} = \{ Q_k \}_{k=0}^2 \cup \big \{ \big ( b^2(y - \sqrt{b}) : b(y - \sqrt{b}) : 4y \big ) \big \} \end{aligned}$$

for \(y \ne \pm \sqrt{b}\). Third,

$$\begin{aligned} \begin{array}{ll} D_{i,y} \cap L_i = \{Q_i\}, &{} \qquad D_{0,y} \cap L_1 = \big \{ Q_1, \big ( b^2(y - \sqrt{b}) : 0 : y - \beta \big ) \big \}, \\ D_\infty \cap L_k = \{Q_k\}, &{} \qquad D_{0,y} \cap L_2 = \big \{ Q_2, \big ( b(y - \sqrt{b}) : y - \beta : 0 \big ) \big \} \end{array} \end{aligned}$$

also for \(y \ne \pm \sqrt{b}\).

Lemma 5

The set of singular points

$$\begin{aligned} \mathrm {Sing}(C_{i,y}) = \left\{ \begin{array}{ll} {\mathbf {Q}}_i &{} \mathrm{\ if}\quad y \not \in \{\pm \sqrt{b}, \beta , \infty \}, \\ {\mathbf {Q}}_i \cup \{R_i\} &{} \mathrm{\ if}\quad y = \beta , \\ \cup _{k=0}^2{\mathbf {Q}}_k &{} \mathrm{\ if}\quad y = \infty . \end{array}\right. \end{aligned}$$

Moreover, \(R_i \in C_{i,\beta }\) is an ordinary point of multiplicity 3 and all other singularities are cusps regardless of y.

Theorem 3

For \(y \ne \pm \sqrt{b}\) the curves \(C_{i,y}\) are absolutely irreducible.

Proof

The cases \(y \in \{ \beta , \infty \}\) are immediately processed by Magma [13]. In compliance with Lemma 5 for another y the curve \(C_{i,y}\) has only 3 cusps, hence it has no more than 3 different absolutely irreducible components \(F_0, F_1, F_2\). Consider the transformations

Since they are of order 3, for any \(k, \ell , m \in \{0,1,2\}\), \(\ell \ne m\) the case , is not possible, otherwise \(F_\ell = F_m\). Also, given \(\ell \) note that for all k if and only if \(F_\ell \) is a Fermat cubic or the line \(L_m\) for some m. Consequently either \(F_0, F_1\) are Fermat cubics or \(F_0, F_1, F_2\) are conics conjugate by \(\chi _k\) for some (or, equivalently, any) k.

It is checked in [13] that the second case does not occur. In the first one, we obtain the decomposition \(D_{i,y} = \pi (F_0) \cup \pi (F_1)\) into lines. However it is easily shown that the discriminant of the conic \(D_{i,y}\) equals \(\pm 4b^6(y - \sqrt{b})(y + \sqrt{b})^2\), hence it is non-degenerate for \(y \ne \pm \sqrt{b}\). \(\square \)

Hereafter we assume that \(y \ne \pm \sqrt{b}\). Let \(\sigma _{i,y}\!: C^\prime _{i,y} \rightarrow C_{i,y}\) be the corresponding normalization morphisms. As is well known,

Further, we have the coverings \(\pi _{i,y} := \pi \circ \sigma _{i,y} \!: C^\prime _{i,y} \rightarrow D_{i,y}\) whose the Galois group is clearly isomorphic to \(({\mathbb {Z}}/3)^2\).

Theorem 4

For \(y \notin \{\beta , \infty \}\) the geometric genus \(g(C_{i,y}) = 7\). Also, \(g( C_{i, \beta }) = 4\), \(g(C_\infty ) = 1\).

Proof

Denote by \(r_y\) the number of ramified points \(Q \in D_{i,y}\). Since \(\pi _{i,y}\) is a Galois covering, the well defined ramification index \(e_Q \in \{3,9\}\) (see, e.g., [20, Corollary 3.7.2]). It is obvious that \(Q \in L_k\) for some \(k \in \{0,1,2\}\). Moreover, the case \(e_Q = 9\) may occur only for \(Q \in \{R_k\}_{k=0}^2\). From Lemmas 3, 4 it follows that

$$\begin{aligned} \#(D_{i,y} \cap L_i) = 1,\qquad \#(D_{i,y} \cap L_{i-1}) = \#(D_{i,y} \cap L_{i+1}) = \left\{ \begin{array}{ll} 1 &{} \mathrm{\ if}\quad y = \infty ,\\ 2 &{} \mathrm{\ otherwise}. \end{array}\right. \end{aligned}$$

Moreover, \(R_{i-1}, R_{i+1} \notin D_{i,y}\), but \(R_i \in D_{i,y}\) if and only if \(y = \beta \). Therefore \(r_{y} = 5\) for \(y \notin \{\beta , \infty \}\), \(r_{\beta } = 4\), and \(r_{\infty } = 3\). Besides, according to Lemma 5 for all points \(Q \in D_{i,y} \cap (\cup _{k=0}^2L_k)\) we have \(e_{Q} = 3\). Applying the Riemann–Hurwitz formula [18, Theorem II.5.9] to \(\pi _{i,y}\), we eventually obtain \(g(C_{i,y}) = 3r_y - 8\). \(\square \)

3 New hash function

This paragraph clarifies how the \({\mathbb {F}}_{\!q}\)-section \(\varphi \!: {\mathbb {A}}^{\!2}_{(t_1,t_2)} \dashrightarrow T\) from Theorem 1 results in a constant-time map \(h\!: {\mathbb {F}}_{\!q}^2 \rightarrow E_b({\mathbb {F}}_{\!q})\). First of all, for \(a \in {\mathbb {F}}_{\!q}^*\) denote by \( \big ( \frac{a}{q} \big )_{\!3} := a^{(q-1)/3}\) the cubic residue symbol, which is trivially a group homomorphism \({\mathbb {F}}_{\!q}^* \rightarrow \{\omega ^i\}_{i=0}^2\).

Lemma 6

[7, Remark 2.3] An element \(a \in {\mathbb {F}}_{\!q}^*\) is a cubic residue if and only if \( \big ( \frac{a}{q} \big )_{\!3} = 1\). Moreover, in this case

To be definite, we put \(\omega := \big ( \frac{b}{q} \big )_{\!3} \) (\(\ne 1\) by our assumption). Also, let us consider only \(q \not \equiv 1 \, (\mathrm {mod} \ 27)\).

Letting \(g_i := y_i^2 - b\) for \(i \in \{0,1,2\}\), we get \(T\!: \big \{ g_j = b^j g_0 t_j^3 \) for \(j \in \{1,2\}\). It is obvious that \(\big \{\! \big ( \frac{g_i}{q} \big )_{\!3} \big \}_{\!i=0}^{\!2} = \{\omega ^i\}_{i=0}^2\) whenever \(g_i, t_j \in {\mathbb {F}}_{\!q}^*\). Besides, denote by \(n \in \{0,1,2\}\) the position number of an element \(t_1 \in {\mathbb {F}}_{\!q}^*\) in the set \(\big \{ \omega ^i t_1 \big \}_{i=0}^{2}\) ordered with respect to some order in \({\mathbb {F}}_{\!q}^*\). For example, if q is a prime, then this can be the usual numerical one.

One of crucial components of h is the auxiliary map

$$\begin{aligned} \begin{aligned} h^\prime \!: T({\mathbb {F}}_{\!q}) \rightarrow E_b({\mathbb {F}}_{\!q})\qquad h^\prime (y_0, y_1, y_2, t_1, t_2) := {\left\{ \begin{array}{ll} \begin{array}{lll} \!\! \big ( \root 3 \of {g_0},\, y_0 \big ) &{}\quad \text {if}\quad g_0 = 0 \ \text{ or } \, \big ( \frac{g_0}{q} \big )_{\!3} = 1, \\ \!\! \big ( \root 3 \of {g_1},\, y_1 \big ) &{}\quad \text {if}\quad \big ( \frac{g_0}{q} \big )_{\!3} = \omega ^2, \\ \!\! \big ( \root 3 \of {g_2},\, y_2 \big ) &{}\quad \text {if}\quad \big ( \frac{g_0}{q} \big )_{\!3} = \omega . \end{array} \end{array}\right. } \end{aligned} \end{aligned}$$

Unfortunately, in this form the value of \(h^\prime \) is computed with the cost of two exponentiations in \({\mathbb {F}}_{\!q}\): the first for \( \big ( \frac{g_0}{q} \big )_{\!3} \) and the second for \(\root 3 \of {g_i}\). Instead, we give an equivalent definition of \(h^\prime \) (up to the automorphisms \([\omega ]^i\)).

  • The case \(q \equiv 4 \ (\mathrm {mod} \ 9)\). Under this assumption

    $$\begin{aligned} \Big ( \frac{\omega }{q} \Big )_{\!3} = \omega ^{(q-1)/3} = \omega ^{(q-4)/3} \!\cdot \!\omega = \omega ^{3(q-4)/9} \!\cdot \!\omega = \omega . \end{aligned}$$

    Let \(\theta := g_0^{(8q-5)/9}\) and \(c_j := \root 3 \of {(b/\omega )^j} \in {\mathbb {F}}_{\!q}^*\). We obtain

    $$\begin{aligned} g_j = b^j g_0 t_j^3 = (c_j\theta t_j)^3 \qquad \mathrm {if} \qquad \theta ^3 = \omega ^j g_0, \ \mathrm {i.e.}, \ \Big ( \frac{g_0}{q} \Big )_{\!3} = \omega ^{3-j}. \end{aligned}$$

    It is easily shown that

    $$\begin{aligned} \begin{aligned} h^\prime \!: T({\mathbb {F}}_{\!q}) \rightarrow E_b({\mathbb {F}}_{\!q})\qquad h^\prime (y_0, y_1, y_2, t_1, t_2) = {\left\{ \begin{array}{ll} \begin{array}{lll} \!\! \big ( \omega ^n \theta ,\, y_0 \big ) &{}\quad \text {if}\quad \theta ^3 = g_0, \\ \!\! \big ( c_1 \theta t_1,\, y_1 \big ) &{}\quad \text {if}\quad \theta ^3 = \omega g_0, \\ \!\! \big ( c_2 \theta t_2,\, y_2 \big ) &{}\quad \text {if}\quad \theta ^3 = \omega ^2 g_0. \end{array} \end{array}\right. } \end{aligned} \end{aligned}$$

    Since

    $$\begin{aligned} \theta ^3 = g_0^{-(q-4)/3} = g_0^{q-1 - (q-4)/3} = g_0^{(2q+1)/3} = g_0^{2(q-1)/3} \!\cdot \!g_0, \end{aligned}$$

    this map is well defined everywhere on \(T({\mathbb {F}}_{\!q})\). It is worth noting that \(\theta \) can be computed with the cost of one exponentiation in \({\mathbb {F}}_{\!q}\) even if \(g_0\) is given as a fraction u/v for \(u \in {\mathbb {F}}_{\!q}\), \(v \in {\mathbb {F}}_{\!q}^*\). Indeed,

    $$\begin{aligned} \theta = (u/v)^{(8q-5)/9} = u^{(8q-5)/9} \!\cdot \!v^{(q-4)/9} = u^3 (u^8v)^{(q-4)/9}. \end{aligned}$$
    (2)

  • The case \(q \equiv 10 \ (\mathrm {mod} \ 27)\) (relevant for BLS12-381). Take any \(\zeta := \root 9 \of {1} \in {\mathbb {F}}_{\!q}^*\) such that \(\zeta ^3 = \omega \). In this case

    $$\begin{aligned} \Big ( \frac{\zeta }{q} \Big )_{\!3} = \zeta ^{(q-1)/3} = \omega ^{(q-1)/9} = \omega ^{(q-10)/9} \!\cdot \!\omega = \omega ^{3(q-10)/27} \!\cdot \!\omega = \omega . \end{aligned}$$

    Let \(\theta := g_0^{(2q+7)/27}\) and \(c_j := \root 3 \of {(b/\zeta )^j} \in {\mathbb {F}}_{\!q}^*\). Given \(i \in \{0,1,2\}\) we obtain

    $$\begin{aligned} g_j = b^j g_0 t_j^3 = (c_j\theta t_j)^3/\omega ^i \qquad \mathrm {if} \qquad \theta ^3 = \omega ^i \zeta ^j g_0, \ \mathrm {i.e.}, \ \Big ( \frac{g_0}{q} \Big )_{\!3} = \omega ^{3-j}. \end{aligned}$$

    It is easily shown that

    $$\begin{aligned} \begin{aligned} h^\prime \!: T({\mathbb {F}}_{\!q}) \rightarrow E_b({\mathbb {F}}_{\!q}) \qquad h^\prime (y_0, y_1, y_2, t_1, t_2) = {\left\{ \begin{array}{ll} \begin{array}{lll} \!\! \big ( \omega ^n \theta / \zeta ^i,\, y_0 \big ) &{}\quad \text {if}\quad \exists i\!: \theta ^3 = \omega ^i g_0, \\ \!\! \big ( c_1 \theta t_1 / \zeta ^i,\, y_1 \big ) &{}\quad \text {if}\quad \exists i\!: \theta ^3 = \omega ^i \zeta g_0, \\ \!\! \big ( c_2 \theta t_2 / \zeta ^i,\, y_2 \big ) &{}\quad \text {if}\quad \exists i\!: \theta ^3 = \omega ^i \zeta ^2 g_0. \end{array} \end{array}\right. } \end{aligned} \end{aligned}$$

    Since

    $$\begin{aligned} \theta ^3 = g_0^{(2q+7)/9} = g_0^{2(q-1)/9} \!\cdot \!g_0, \end{aligned}$$

    this map is well defined everywhere on \(T({\mathbb {F}}_{\!q})\). It is worth noting that \(\theta \) can be computed with the cost of one exponentiation in \({\mathbb {F}}_{\!q}\) even if \(g_0\) is given as a fraction u/v for \(u \in {\mathbb {F}}_{\!q}\), \(v \in {\mathbb {F}}_{\!q}^*\). Indeed,

    $$\begin{aligned} \begin{aligned} \theta&= (u/v)^{(2q+7)/27} = u^{(2q+7)/27} \!\cdot \!v^{q-1 - (2q+7)/27} = u^{(2q+7)/27} \!\cdot \!v^{(25q - 34)/27} = \\&= u \!\cdot \!u^{2(q-10)/27} \!\cdot \!v^3 v^{5(5q - 23)/27} = uv^8 (u^2 v^{25})^{(q - 10)/27}. \end{aligned} \end{aligned}$$
    (3)

The cases \(q \equiv 7 \ (\mathrm {mod} \ 9)\) and \(q \equiv 19 \ (\mathrm {mod} \ 27)\) are processed in a similar way. To be definite, throughout the rest of the article we will deal with the modified version of \(h^\prime \). Finally, we come to the map desired

$$\begin{aligned} \begin{aligned} h\!: {\mathbb {F}}_{\!q}^2 \rightarrow E_b({\mathbb {F}}_{\!q}) \qquad h(t_1, t_2) := {\left\{ \begin{array}{ll} \begin{array}{ll} \!\! P_0 &{}\quad \mathrm {if} \quad t_1t_2 = 0, \\ \!\! \mathcal {O}&{}\quad \mathrm {if}\quad \mathrm {den}(t_1, t_2) = 0, \\ \!\! (h^\prime \circ \varphi )(t_1, t_2) &{}\quad \mathrm {otherwise}. \end{array} \end{array}\right. } \end{aligned} \end{aligned}$$

We emphasize that in the definition of \(h^\prime \) (a fortiori, in \(\varphi \)) the cubic residue symbol does not appear. Further, by returning the value of h in (weighted) projective coordinates, we entirely avoid inversions in the field. Besides, the constants \(\omega \), \(c_j\) (and \(\zeta \), \(\zeta ^{-\!1} = \zeta ^8\) if \(q \equiv 10 \ (\mathrm {mod} \ 27)\)) are found once at the precomputation stage. By the way, in the formulas (2), (3) we take \(u := \mathrm {num}_0^2 - b\!\cdot \!\mathrm {den}^2\) and \(v := \mathrm {den}^2\). Calculating the value \(\theta \) every time no matter whether \(t_0t_1uv = 0\) or not, we eventually obtain

Remark 1

When \(q \not \equiv 1 \, (\mathrm {mod} \ 27)\), the map h is computed in constant time, namely in that of one exponentiation in \({\mathbb {F}}_{\!q}\).

4 Indifferentiability from a random oracle

Theorem 5

For any point \(P \in E_b({\mathbb {F}}_{\!q}) \setminus \{\pm P_0, \mathcal {O}\}\) we have

$$\begin{aligned} \begin{array}{ll} | \#h^{-\!1}(P) - (q+1) | \leqslant 7\lfloor 2\sqrt{q} \rfloor + 6. &{} \quad \textit{In \ turn,} \qquad |\#h^{-\!1}(P_0) - 3q| \leqslant \lfloor 2\sqrt{q} \rfloor , \\ |\#h^{-\!1}(-P_0) - 2(q+1)| \leqslant 2\lfloor 2\sqrt{q} \rfloor , &{} \quad \textit{and} \qquad |\#h^{-\!1}(\mathcal {O}) - (q+1)| \leqslant \lfloor 2\sqrt{q} \rfloor . \end{array} \end{aligned}$$

Proof

All the inequalities follow from the Hasse–Weil–Serre bound [20, Theorem 5.3.1] for the number of \({\mathbb {F}}_{\!q}\)-points on a projective non-singular absolutely irreducible \({\mathbb {F}}_{\!q}\)-curve.

First, suppose that \(h(t_1, t_2) = \pm P_0\). Then \(t_1t_2 = 0\) or \(\theta = g_0 = 0\). In the first case, \(h(0, t_2) = h(t_1, 0) = P_0\). In the second one, \((1:t_1:t_2) \in C_{0,\pm \sqrt{b}}\). These curves decompose as \(C_{0,\sqrt{b}} = L_0 \cup F_0\) and \(C_{0,-\sqrt{b}} = F_1 \cup F_2\), where \(F_k\) are Fermat cubics (cf. the equations (1)). The latter are obviously elliptic curves (of j-invariant 0). In accordance with Lemma 4 we have \((C_{0,\pm \sqrt{b}} \cap C_\infty )({\mathbb {F}}_{\!q}) = \emptyset \). Note also that \((F_1 \cap F_2)({\mathbb {F}}_{\!q}) = (L_i \cap F_k)({\mathbb {F}}_{\!q}) = \emptyset \) for all \(i,k \in \{0,1,2\}\).

In turn, \((C_\infty \cap L_k)({\mathbb {F}}_{\!q}) = \emptyset \) according to Lemma 4, hence \(h^{-\!1}(\mathcal {O}) = C_\infty ({\mathbb {F}}_{\!q})\). Besides, \(\mathrm {Sing}(C_\infty )({\mathbb {F}}_{\!q}) = \emptyset \) (see Lemma 5). As a result, we obtain the bijection . Finally, the geometric genus \(g(C_\infty ) = 1\) by virtue of Theorem 4.

Now take \(P = (x,y) \in E_b({\mathbb {F}}_{\!q}) \setminus \{\pm P_0, \mathcal {O}\}\). The case \(y = \beta \) does not occur, because \(\beta ^2 - b = 8b\) is not a cubic residue in \({\mathbb {F}}_{\!q}\). In compliance with Lemmas 3, 4 we see that

$$\begin{aligned} (C_{i,y} \cap C_\infty )({\mathbb {F}}_{\!q}) = (C_{i,y} \cap C_{i+1,y})({\mathbb {F}}_{\!q}) = (C_{i,y} \cap L_i)({\mathbb {F}}_{\!q}) = \emptyset , \qquad \#(C_{i,y} \cap L_k)({\mathbb {F}}_{\!q}) \leqslant 3 \end{aligned}$$

for all \(i,k \in \{0,1,2\}\). Besides, the x-coordinates of \(h(t_1, t_2)\) and \(h(\omega t_1, t_2)\) (resp. \(h(t_1, \omega t_2)\)) are always different if \(i \in \{0,1\}\) (resp. \(i = 2\)), because \(\theta (t_1, t_2) = \theta (\omega t_1, t_2) = \theta (t_1, \omega t_2)\). Therefore

$$\begin{aligned} h^{-\!1}\big ( \big \{ P, [\omega ](P), [\omega ]^2(P) \big \} \big ) \ = \ \bigsqcup _{i=0}^2h^{-\!1}\big ( [\omega ]^i(P) \big ) \ = \ \bigsqcup _{i=0}^2 C_{i,y}({\mathbb {F}}_{\!q}) \setminus (L_{i-1} \cup L_{i+1}). \end{aligned}$$

Since \(\# h^{-\!1}\big ( [\omega ]^i(P) \big ) = \# h^{-\!1}\big ( [\omega ]^{i+1}(P) \big )\), we obtain

$$\begin{aligned} 3 \!\cdot \!\#h^{-\!1}(P) = \sum _{i=0}^2\# C_{i,y}({\mathbb {F}}_{\!q}) \setminus (L_{i-1} \cup L_{i+1}). \end{aligned}$$

Consequently,

$$\begin{aligned} \sum _{i=0}^2 (\# C_{i,y}({\mathbb {F}}_{\!q}) - 6) \leqslant 3 \!\cdot \!\#h^{-\!1}(P) \leqslant \sum _{i=0}^2 \# C_{i,y}({\mathbb {F}}_{\!q}). \end{aligned}$$

Further, \(\#C_{i,y}({\mathbb {F}}_{\!q}) = \#C_{i+1,y}({\mathbb {F}}_{\!q})\) according to Lemma 3. Thus

$$\begin{aligned} 3 (\#C_{i,y}({\mathbb {F}}_{\!q}) - 6) \leqslant 3 \!\cdot \!\#h^{-\!1}(P) \leqslant 3 \!\cdot \!\#C_{i,y}({\mathbb {F}}_{\!q}) \end{aligned}$$

and hence

$$\begin{aligned} | \#h^{-\!1}(P) - \#C_{i,y}({\mathbb {F}}_{\!q}) | \leqslant 6. \end{aligned}$$

At the same time, Theorem 4 says that \(g(C_{i,y}) = 7\). Besides, \(\mathrm {Sing}(C_{i,y})({\mathbb {F}}_{\!q}) = \emptyset \) (see Lemma 5). As a result, . We eventually obtain

$$\begin{aligned} | \#h^{-\!1}(P) - (q+1) | \leqslant | \#h^{-\!1}(P) - \#C_{i,y}({\mathbb {F}}_{\!q}) | + |\#C_{i,y}({\mathbb {F}}_{\!q}) - (q+1)| \leqslant 6 + 7\lfloor 2\sqrt{q} \rfloor . \end{aligned}$$

The theorem is proved. \(\square \)

Corollary 1

The map \(h\!: {\mathbb {F}}_{\!q}^2 \rightarrow E_b({\mathbb {F}}_{\!q})\) is surjective at least for \(q \geqslant 211\).

Corollary 2

The distribution on \(E_b({\mathbb {F}}_{\!q})\) defined by h is \(\epsilon \)-statistically indistinguishable from the uniform one [4, Definition 3], where \(\epsilon := 16q^{-1/2} + O(q^{-1})\).

Proof

For any point \(P \in E_b({\mathbb {F}}_{\!q})\) put

$$\begin{aligned} \delta (P):= & {} \left| \dfrac{\#h^{-\!1}(P)}{q^2} - \dfrac{1}{\#E_b({\mathbb {F}}_{\!q})} \right| \ \leqslant \ \left| \dfrac{\#h^{-\!1}(P)}{q^2} - \dfrac{1}{q} \right| + \left| \dfrac{1}{q} - \dfrac{1}{\#E_b({\mathbb {F}}_{\!q})} \right| \\= & {} \dfrac{|\#h^{-\!1}(P) - q|}{q^2} + \dfrac{|\#E_b({\mathbb {F}}_{\!q}) - q|}{q \!\cdot \!\#E_b({\mathbb {F}}_{\!q})} \ \leqslant \ \dfrac{|\#h^{-\!1}(P) - q|}{q^2} + \dfrac{ \lfloor 2\sqrt{q} \rfloor + 1 }{q (q + 1 - \lfloor 2\sqrt{q} \rfloor )}\\= & {} \dfrac{|\#h^{-\!1}(P) - q|}{q^2} + \dfrac{2}{q^{3/2}} + O\Big ( \dfrac{1}{q^2} \Big ). \end{aligned}$$

If \(P \not \in \{\pm P_0, \mathcal {O}\}\) from Theorem 5 we obtain

$$\begin{aligned} \delta (P) = \dfrac{16}{q^{3/2}} + O\Big ( \dfrac{1}{q^2} \Big ). \end{aligned}$$

Similarly,

$$\begin{aligned} \delta (P_0) = \dfrac{2}{q} + O\Big ( \dfrac{1}{q^{3/2}} \Big ), \qquad \delta (-P_0) = \dfrac{1}{q} + O\Big ( \dfrac{1}{q^{3/2}} \Big ), \qquad \delta (\mathcal {O}) = \dfrac{4}{q^{3/2}} + O\Big ( \dfrac{1}{q^2} \Big ). \end{aligned}$$

Thus

$$\begin{aligned} \sum _{P \in E_b({\mathbb {F}}_{\!q})} \delta (P) \ \leqslant \ (q + \lfloor 2\sqrt{q} \rfloor - 2) \Big ( \dfrac{16}{q^{3/2}} + O\Big ( \dfrac{1}{q^2} \Big ) \Big ) + \dfrac{3}{q} + O\Big ( \dfrac{1}{q^{3/2}} \Big ) \ = \ \dfrac{16}{q^{1/2}} + O\Big ( \dfrac{1}{q} \Big ). \end{aligned}$$

The corollary is proved. \(\square \)

For \(t_2 \in {\mathbb {F}}_{\!q}\) consider the encoding \(h_{t_2}\!: {\mathbb {F}}_{\!q} \rightarrow E_b({\mathbb {F}}_{\!q})\) of the form \(h_{t_2}(t_1) := h(t_1,t_2)\). By definition, \(h_0(t_1) = P_0\) for any \(t_1 \in {\mathbb {F}}_{\!q}\). Nevertheless, by analogy with [12, Theorem 2] we can prove the next lemma. Its main difference is that \(h_{t_2}(t_1) = h_{t_2}(\omega t_1)\) whenever \(\root 3 \of {g_2} \in {\mathbb {F}}_{\!q}\), hence 10 appears instead of 6.

Lemma 7

For \(t_2 \in {\mathbb {F}}_{\!q}^*\) and \(P \in E_b({\mathbb {F}}_{\!q})\) we have \(\#h_{t_2}^{-\!1}(P) \leqslant 10\) and hence \(q/10 \leqslant \#\mathrm {Im}(h_{t_2})\).

By this lemma [4, Algorithm 1] still works well in the case of h. Indeed, for \(P \in E_b({\mathbb {F}}_{\!q})\) pick uniformly at random \(t_2 \in {\mathbb {F}}_{\!q}\) and then find uniformly at random \(t_1 \in h_{t_2}^{-\!1}(P)\). For instance, when \(P \not \in \{\pm P_0, \mathcal {O}\}\), the latter consists in computing a non-zero \({\mathbb {F}}_{\!q}\)-root (if any) of the polynomial \(C_{i, y} \in {\mathbb {F}}_{\!q}[t_1]\) of degree 6 for i chosen randomly. The shape of \(C_{i, y}\) allows to do this with the help of successive extraction of the square and cubic roots. We eventually obtain

Remark 2

The map h is samplable [4, Definition 4].

Remarks 1, 2 and Corollary 2 imply that h is admissible in the sense of [4, Definition 4]. Finally, using [4, Theorem 1], we establish

Corollary 3

Consider the composition \(H := h \circ {\mathfrak {h}} \!: \{0,1\}^* \rightarrow E_b({\mathbb {F}}_{\!q})\) of a hash function \({\mathfrak {h}}\!: \{0,1\}^* \rightarrow {\mathbb {F}}_{\!q}^2\) and h. The hash function H is indifferentiable from a random oracle if \({\mathfrak {h}}\) is so.