Pierre-Alain Fouque
email: pierre-alain.fouque@ens.fr

Mehdi Tibouchi
email: tibouchi.mehdi@lab.ntt.co.jp

Indifferentiable Hashing to Barreto-Naehrig Curves

Keywords: Elliptic curve cryptography, BN curves, hashing, random oracle

A number of recent works have considered the problem of constructing constant-time hash functions to various families of elliptic curves over finite fields. In the relevant literature, it has been occasionally asserted that constant-time hashing to certain special elliptic curves, in particular so-called BN elliptic curves, was an open problem. It turns out, however, that a suitably general encoding function was constructed by Shallue and van de Woestijne back in 2006. In this paper, we show that, by specializing the construction of Shallue and van de Woestijne to BN curves, one obtains an encoding function that can be implemented rather efficiently and securely, that reaches about 9/16ths of all points on the curve, and that is well-distributed in the sense of Farashahi et al., so that one can easily build from it a hash function that is indifferentiable from a random oracle.

Introduction

Many elliptic curve-based cryptographic protocols require hashing to an elliptic curve group G: they involve one or more hash functions H : {0, 1} * → G mapping arbitrary values to points on the elliptic curve.

For example, in the Boneh-Franklin identity-based encryption scheme [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF], the public key for identity id ∈ {0, 1} * is a point Q id = H(id) on the curve. This is also the case in many other pairing-based cryptosystems including IBE and HIBE schemes [START_REF] Baek | Identity-based threshold decryption[END_REF][START_REF] Gentry | Hierarchical ID-based cryptography[END_REF][START_REF] Horwitz | Toward hierarchical identity-based encryption[END_REF], signature and identity-based signature schemes [START_REF] Boldyreva | Threshold signatures, multisignatures and blind signatures based on the Gap-Diffie-Hellman-group signature scheme[END_REF][START_REF] Boneh | Aggregate and verifiably encrypted signatures from bilinear maps[END_REF][START_REF] Boneh | Short signatures from the Weil pairing[END_REF][START_REF] Cha | An identity-based signature from Gap Diffie-Hellman groups[END_REF][START_REF] Zhang | ID-based blind signature and ring signature from pairings[END_REF] and identity-based signcryption schemes [START_REF] Boyen | Multipurpose identity-based signcryption (a Swiss army knife for identity-based cryptography)[END_REF][START_REF] Libert | Efficient signcryption with key privacy from Gap Diffie-Hellman groups[END_REF].

Hashing into elliptic curves is also required for some passwords-based authentication protocols such as the SPEKE [START_REF] Jablon | Strong password-only authenticated key exchange[END_REF] and PAK [START_REF] Boyko | Provably secure password-authenticated key exchange using Diffie-Hellman[END_REF] protocols, as well as various signature schemes based on the hardness of the discrete logarithm problem, like [START_REF] Chevallier-Mames | An efficient CDH-based signature scheme with a tight security reduction[END_REF], when they are instantiated over elliptic curves.

In all of those cases, the hash functions are modeled as random oracles in security proofs. However, it is not clear how such a hash function can be instantiated in practice. Indeed, random oracles to groups like Z * p can be easily constructed from random oracles to fixed-length bit strings, for which conventional cryptographic hash functions usually provide acceptable substitutes. On the other hand, constructing random oracles to an elliptic curve even from random oracles to bit strings appears difficult in general, and some of the more obvious instantiations actually break security completely. For example, to construct a hash function H : {0, 1} * → G to an elliptic curve cyclic group G of order N and generated by a given point G, a simple idea might be to choose H(m) = [h(m)] • G, where h is a hash function {0, 1} * → Z N . However, this typically breaks security proofs in the random oracle model. Suppose the proof involves programming the random oracle H by choosing its value P on some input m 0 . If we instantiate H in this naive way, the programming stage requires setting h(m 0 ) to the discrete logarithm of P, which is normally unknown. In fact, in the case of a primitive like BLS signatures [START_REF] Boneh | Short signatures from the Weil pairing[END_REF], this instantiation leads to very simple and devastating attacks (see the discussions in [START_REF] Tibouchi | Hachage vers les courbes elliptiques et cryptanalyse de schémas RSA[END_REF]Ch. 3] or [START_REF] Tibouchi | A note on hasing to BN curves[END_REF]).

In their original short signatures paper [START_REF] Boneh | Short signatures from the Weil pairing[END_REF], Boneh, Lynn and Shacham introduced the first generic construction of a secure hash function to elliptic curves, in the sense that it applies to any target elliptic curve: the so-called "try-andincrement" algorithm. Basically, to hash a message m, one concatenates it with a fixed-length counter c initialized to 0 and computes h(c m), where h is a hash function to the base field of the elliptic curve. If that digest value is the abscissa of a point on the curve, H(m) is set to that point; otherwise, one increments the counter c and tries again. This construction can be shown to be secure provided that the counter length is large enough; however, it is somewhat inefficient, since one may need many iterations before finding a suitable point, and the fact that the length of the computation depends on the input yields to possible side-channel attacks, especially in protocols such as password authenticated key exchange (a concrete attack is given is [START_REF] Tibouchi | A note on hasing to BN curves[END_REF] for a variant of SPEKE [START_REF] Jablon | Strong password-only authenticated key exchange[END_REF]).

In response, more robust, "constant-time" methods have been proposed, starting with a paper by Icart at CRYPTO 2009 [START_REF] Icart | How to hash into elliptic curves[END_REF], and including a number of extensions, generalizations and refinements afterwards [START_REF] Sato | An efficient method of generating rational points on elliptic curves[END_REF][START_REF] Brier | Efficient indifferentiable hashing into ordinary elliptic curves[END_REF][START_REF] Fouque | Deterministic encoding and hashing to odd hyperelliptic curves[END_REF][START_REF] Kammerer | Encoding points on hyperelliptic curves over finite fields in deterministic polynomial time[END_REF][START_REF] Farashahi | Hashing into Hessian curves[END_REF][START_REF] Couveignes | The geometry of flex tangents to a cubic curve and its parameterizations[END_REF]. In essence, these methods are all based on the construction of a suitable algebraic or piecewise algebraic function from the affine line to the target elliptic curve.

Our contributions. None of the methods mentioned above is fully generic: they all rely on certain arithmetic or geometric properties of the target curve. Some involve taking arbitrary cube roots in the base field F q , for example, and hence only apply to the case when q ≡ 2 (mod 3). The remaining ones only work for curves of nonzero j-invariant. In particular, none of those more efficient encodings yield a construction of hash functions to the very important class of Barreto-Naehrig (BN) elliptic curves [START_REF] Barreto | Pairing-friendly elliptic curves of prime order[END_REF], which are the preferred curves for implementing asymmetric pairings nowadays, as they provide essentially optimal parameters for the 128-bit security level. This has led several authors to assert that constant-time hashing to BN curves was an open problem [START_REF] Fouque | Deterministic encoding and hashing to odd hyperelliptic curves[END_REF][START_REF] Pereira | A family of implementation-friendly BN elliptic curves[END_REF].

It turns out, however, that several years prior to Icart's work, Shallue and van de Woestijne had presented a construction [START_REF] Shallue | Construction of rational points on elliptic curves over finite fields[END_REF] that applies to all curves of odd characteristic, as pointed out in [START_REF] Tibouchi | A note on hasing to BN curves[END_REF]. This paper is devoted to making that construction explicit in the case of BN curves, and establishing some properties of it. More precisely, our contributions are as follows:

-we propose an explicit, optimized definition of the Shallue-van de Woestijne encoding to a BN elliptic curve (in Section 3); -using an extension of the technique from [START_REF] Farashahi | On hashing into elliptic curves[END_REF][START_REF] Fouque | Estimating the size of the image of deterministic hash functions to elliptic curves[END_REF], we establish an estimate for the number of points in the image of that encoding (in Section 4): we find that the encoding reaches about 9/16ths of all points on the curve; -like Icart's encoding and many others, this encoding f will not yield a generically secure hash function construction if we simply compose it with a random oracle to the base field (e.g. it is easy to distinguish such a hash function from a random oracle to the curve since its image has a simple algebraic description and only contains a constant fraction of all points). However, we show (in Section 5) that it is well-distributed in the sense of Farashahi et al. [START_REF] Farashahi | Indifferentiable deterministic hashing to elliptic and hyperelliptic curves[END_REF]. This implies that if h 1 , h 2 are random oracles to the base field, then m → f h 1 (m) + f h 2 (m) is a good, generically secure hash function to the BN curve (it is indifferentiable from a random oracle); -finally, we also suggest (in Section 6) a way to implement this encoding function that should thwart side-channel analysis and other physical attacks.

Our approach to establishing the results of Sections 4 and 5, while quite technical, is also of independent interest. Indeed, the Shallue-van de Woestijne encoding fits in a family of various encoding functions to elliptic curves based on works by Schinzel and Ska lba [START_REF] Schinzel | On equations y 2 = x n + k in a finite field[END_REF][START_REF] Ska Lba | Points on elliptic curves over finite fields[END_REF], and while Fouque and Tibouchi [START_REF] Fouque | Estimating the size of the image of deterministic hash functions to elliptic curves[END_REF] and Farashahi et al. [START_REF] Farashahi | Indifferentiable deterministic hashing to elliptic and hyperelliptic curves[END_REF] did tackle a function of that type before, they had to consider only a special case and tweak the formulas significantly, so as to simplify the computations. In this paper, we show how image size estimates and well-distributedness can be obtained for this type of encoding functions without simplifications or generality loss.

Our results apply almost without change to any elliptic curve of the form y 2 = x 3 + b with b = -1 over a finite field F q with q ≡ 7 (mod 12). Pairingfriendly curves obtained by the CM method for discriminant -3 are typically of that form: this includes in particular the curves constructed by Barreto, Lynn and Scott in [2, §3.1] and the curves of embedding degree 18 and 36 obtained by Kachisa, Schaefer and Scott in [START_REF] Kachisa | Constructing brezing-weng pairingfriendly elliptic curves using elements in the cyclotomic field[END_REF], all of which are recommended for pairing implementations at higher security levels (192 to 256-bit security). The elliptic curve group in those cases is not usually of prime order, however (those cases have ρ > 1), so hashing to the prime order subgroup requires multiplying the point obtained with the technique described herein by the cofactor. This does not affect indifferentiability, as was shown in [12, §6.1].

Notation. In the paper, p will always be an odd prime and q an odd prime power. In F q , the finite field with q elements, we denote by χ q : F q → {-1, 0, 1} the nontrivial quadratic character of F * q extended by zero to F q (i.e. χ q (0) = 0 and for a = 0, χ q (a) = 1 if a is a square and -1 otherwise). When q ≡ 3 (mod 4), we write √ a = a (q+1)/4 for any square a ∈ F q .

2 Preliminaries

Barreto-Naehrig elliptic curves

BN curves are a family of pairing-friendly elliptic curves over large prime fields, introduced in 2005 by Barreto and Naehrig [START_REF] Barreto | Pairing-friendly elliptic curves of prime order[END_REF]. They are one of the preferred families for implementing asymmetric pairings nowadays, as they achieve essentially optimal parameters for obtaining bilinear groups at the 128-bit security level. Indeed, BN curves are of prime order (in particular they satisfy ρ = 1) and embedding degree k = 12; thus, the pairing on a BN curve over a 256-bit prime field F p takes its values in the field F p 12 of size 256 × 12 = 3072. Then, solving the discrete logarithm problem both in the group of points of the curve and in F × p k takes time about 2 128 as required [START_REF] Barreto | Pairing-friendly elliptic curves of prime order[END_REF].

The details of the construction of BN curves, based on the CM method, is not really relevant for our purposes. Suffice it to say that Barreto and Naehrig's algorithm outputs an elliptic curve of the form:

E : y 2 = x 3 + b (1)
over a field F p with p ≡ 1 (mod 3) (for convenience, they suggest to pick a p satisfying, more precisely, p ≡ 31 (mod 36)), such that #E(F p ) is prime, together with the generator

3 G = (1, √ b + 1 mod p) ∈ E(F p ).
Moreover, b is typically a very small integer (the smallest > 0 such that b + 1 is a quadratic residue mod p).

Chebotarev density theorem

In [START_REF] Farashahi | On hashing into elliptic curves[END_REF][START_REF] Fouque | Estimating the size of the image of deterministic hash functions to elliptic curves[END_REF], Farashahi, Shparlinski and Voloch on the one hand, and Fouque and Tibouchi on the other, proposed an approach to counting the number of points in the image of an elliptic curve encoding function, based on the Chebotarev density theorem for function fields. We will apply a similar technique to the encoding to BN curves presented hereafter, and will therefore need an effective version of the Chebotarev density theorem. One such version is given in [START_REF] Fried | Field arithmetic, volume 11 of Ergebnisse der Mathematik und ihrer Grenzgebiete[END_REF]Proposition 6.4.8], and if we specialize it to our cases of interest, we obtain: Lemma 1 (Chebotarev). Let K be an extension of F q (x) of degree d < ∞ and L a Galois extension of K of degree m < ∞. Assume F q is algebraically closed in L, and fix some subset S of Gal(L/K) stable under conjugation. Let s = #S and N (S ) the number of places v of K of degree 1, unramified in L, such that the Artin symbol L/K v (defined up to conjugation) is in S . Then

N (S ) - s m q ≤ 2s m (m + g L ) • q 1/2 + m(2g K + 1) • q 1/4 + g L + dm
where g K and g L are the genera of the function fields K and L.

Admissible encodings and indifferentiability

Brier et al. [START_REF] Brier | Efficient indifferentiable hashing into ordinary elliptic curves[END_REF] use Maurer's indifferentiability framework [START_REF] Maurer | Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology[END_REF] to analyze the conditions under which their hash function constructions can be plugged into essentially any scheme4 that is proved secure in the random oracle model in such a way that the proof of security goes through. As shown by Maurer, it suffices that the hash function construction be indifferentiable from a random oracle.

Then, Brier et al. [START_REF] Brier | Efficient indifferentiable hashing into ordinary elliptic curves[END_REF] establish a sufficient condition for a hash function construction into an elliptic curve E to be indifferentiable from a random oracle. It applies to hash functions of the form:

H(m) = F (h(m)),
where F : S → E(F q ) is a deterministic encoding, and h is seen as a random oracle to S. Assuming that h is a random oracle, the construction is indifferentiable whenever F is an admissible encoding into E(F q ), in the sense that it satisfies the following properties:

1. Computable: F is computable in deterministic polynomial time; 2. Regular: for s uniformly distributed in S, the distribution of F (s) is statistically indistinguishable from the uniform distribution in E(F q ); 3. Samplable: there is an efficient randomized algorithm I such that for any P ∈ E(F q ), the distribution of I (P) is statistically indistinguishable from the uniform distribution in F -1 (P).

Well-distributed elliptic curve encodings

Building upon this work by Brier et al., Farashahi et al. introduced a general framework [START_REF] Farashahi | Indifferentiable deterministic hashing to elliptic and hyperelliptic curves[END_REF] to obtain well-behaved hash function construction to elliptic and hyperelliptic curves. The main notion in that framework is that of a welldistributed encoding. In the case of an elliptic curve E, it is defined as follows.

Definition 1 (Farashahi et al.). A function f : F q → E(F q ) is said to be Bwell-distributed for some B > 0 if, for all nontrivial characters χ of E(F q ), the following bound holds:

|S f (χ)| ≤ B √ q, where S f (χ) = u∈Fq χ f (u) . (2)
Let f : F q → E(F q ) be a well-distributed encoding to the elliptic curve E. Then Farashahi et al. prove that the tensor square f ⊗2 :

F 2 q → E(F q ) defined by f ⊗2 (u, v) = f (u) + f (v)
is a regular encoding to E(F q ). More precisely, the statistical distance between the distribution defined by f ⊗2 on E(F q ) and the uniform distribution is bounded above by B 2 • #E(F q )/q, which is negligible.

If the function f is also efficiently computable and samplable in the sense of Section 2.3, then f ⊗2 is admissible, which implies that the hash function:

m → f h 1 (m) + f h 2 (m)
is indifferentiable from a random oracle, and hence can be used in lieu of a random oracle to E(F q ) in essentially any scheme proved secure in the random oracle model.

Another important result of [START_REF] Farashahi | Indifferentiable deterministic hashing to elliptic and hyperelliptic curves[END_REF] is the following consequence of the Riemann hypothesis for curves, which makes it possible to establish the bound (2) in practice.

Lemma 2 ([17, Th. 7]). Let h : X → E be a non constant morphism to the elliptic curve E, and χ be any nontrivial character of E(F q ). Assume that h does not factor through a nontrivial unramified morphism Z → E. Then:

P∈X(Fq) χ(h(P )) ≤ (2g X -2) √ q (3)
where g X is the genus of X. Furthermore, if ϕ is a non constant rational function on X:

P∈X(Fq) χ(h(P )) • χ q (ϕ(P)) ≤ (2g X -2 + 2 deg ϕ) √ q. (4)

The Shallue-van de Woestijne encoding

Let E be any elliptic curve over a finite field F q of odd characteristic with #F q > 5, written is Weierstrass form:

E : y 2 = g(x) = x 3 + Ax 2 + Bx + C.
Shallue and van de Woestijne [START_REF] Shallue | Construction of rational points on elliptic curves over finite fields[END_REF] construct an encoding function f : F q → E(F q ) as follows.

Following the ideas of Schinzel and Ska lba [START_REF] Schinzel | On equations y 2 = x n + k in a finite field[END_REF][START_REF] Ska Lba | Points on elliptic curves over finite fields[END_REF], they first introduce the algebraic threefold V ⊂ P 4 with affine equation

V : y 2 = g(x 1 ) • g(x 2 ) • g(x 3 ),
and observe that if (x 1 , x 2 , x 3 , y) is an F q -rational point on V , then at least one of x 1 , x 2 , x 3 is the abscissa of a point in E(F q ). Indeed, the product g(x 1 ) • g(x 2 ) • g(x 3 ) ∈ F q is a square, so at least one of the factors must be square as well. Then, they establish the following result.

Lemma 3 ([35, Lemma 6]). Put h(u, v) = u 2 + uv + v 2 + A(u + v) + B,
and define:

S : y 2 • h(u, v) = -g(u), ψ : (u, v, y) → v, -A -u -v, u + y 2 , g(u + y 2 ) • h(u, v) • y -1 .
Then ψ is a rational map from the surface S to V that is invertible on its image.

In particular, any point in S(F q ) where ψ is well-defined (i.e. satisfying y = 0) maps to a point in V (F q ), and hence yields a point in E(F q ). Finally, to construct points on S, the authors of [START_REF] Shallue | Construction of rational points on elliptic curves over finite fields[END_REF] note that any plane section of S of the form u = u 0 is birational to a conic, which is non-degenerate as long as:

g(u 0 ) = 0 and 3u 2 0 + 2Au 0 + 4B -A 2 = 0. (5)
If we fix one such value u 0 (it necessarily exists since #F q > 5), the corresponding conic admits a rational parametrization, which gives a rational map φ : A 1 → S.

The encoding function f : F q → E(F q ) is then obtained as mapping a point t ∈ F q to one of the points on E(F q ) of abscissa x i , where ψ •φ(t) = (x 1 , x 2 , x 3 , y) and i ∈ {1, 2, 3} is the smallest index such that g(x i ) is a square.

In the following sections, we make that function f explicit when E is a BN curve as in Section 2.1 (or rather, belongs to a class of elliptic curves that contains BN curves), and establish a number of its properties.

An Encoding to BN Curves

Let us apply the previous construction to the case of an elliptic curve of the form:

E : y 2 = g(x) = x 3 + b
over a field F q of characteristic ≥ 5. We also assume that q ≡ 7 (mod 12) and that g(1) = 1 + b is a nonzero square in F q . As seen in Section 2.1, all those properties are in particular satisfied for BN curves. 5The equation of the surface S defined in Section 2.5 becomes:

S : y 2 • (u 2 + uv + v 2 ) = -u 3 -b.
We consider its section by the plane of equation u = u 0 = 1. This gives a curve of equation:

y 2 • 3 4 + v + 1 2 2 = -1 -b,
and by setting z = v + 1/2 and w = 1/y, we see that it is birational to the conic:

z 2 + (1 + b)w 2 = - 3 4 , (6)
which is non-degenerate since g(1) = 1+b = 0. We can give a convenient rational parametrization of that conic as follows. Since q ≡ 1 (mod 3), (-3) is a quadratic residue in F q . Thus, (z 0 , w 0 ) = ( √ -3/2, 0) is an F q -rational point on the conic [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF]. We parametrize all the other points by setting z = z 0 + tw, which gives:

√ -3 • t + t 2 • w + (1 + b) • w = 0,
and hence:

y = 1 w = - 1 + b + t 2 √ -3 • t v = z 0 + tw -1 = -1 + √ -3 2 + √ -3 • t 2 1 + b + t 2 .
This is well-defined (and y is nonzero) if and only if t = 0 and t 2 = -1 -b, and the second condition is always verified since χ q (-1 -b) = -χ q (1 + b) = -1. Thus, for any t = 0, it follows from Lemma 3 that at least one of the three values:

x 1 = v = -1 + √ -3 2 - √ -3 • t 2 1 + b + t 2 , (7)
x 2 = -1 -v = -1 - √ -3 2 + √ -3 • t 2 1 + b + t 2 , (8)
x 3 = 1 + y 2 = 1 - (1 + b + t 2 ) 2 3t 2 (9)
is the abscissa of a point in E(F q ). Furthermore, we see that these values only depend on t 2 , and hence are invariant under a change of sign for t. As a result, it is natural to map t and -t to opposite points on E(F q ) with one of the previous coordinates. Therefore, we can define the Shallue-van de Woestijne encoding to the BN curve E as follows.

Definition 2. For all t ∈ F * q , let x 1 , x 2 , x 3 ∈ F q be as in Eqs. [START_REF] Boneh | Aggregate and verifiably encrypted signatures from bilinear maps[END_REF] to [START_REF] Boneh | Short signatures from the Weil pairing[END_REF]. The SW encoding to the BN curve E is the map:

f : F * q -→ E(F q ) t -→ x i , χ q (t) • g(x i ) ,
where for each t, i ∈ {1, 2, 3} is the smallest index such that g(x i ) is a square in F q .

The encoding can be extended to all of F q by sending 0 to some arbitrary point in E(F q ). Since x 1 is well-defined and equal to (-1 + √ -3)/2 for t = 0, and g(x 1 ) = 1 + b is a square, a relatively natural choice may be to set:

f (0) = -1 + √ -3 2 , √ 1 + b .

Computing the Image Size

In this section, we estimate the number of points in the image of the Shalluevan de Woestijne encoding f to E(F q ), using a refinement of the techniques from [START_REF] Farashahi | On hashing into elliptic curves[END_REF][START_REF] Fouque | Estimating the size of the image of deterministic hash functions to elliptic curves[END_REF]. We will show that f reaches roughly 9/16ths of all points on the curve, or more precisely, that #f (F * q ) = (9/16) • q + O( √ q) (where the constant in the big-O is universal and will be made explicit).

To obtain that estimate, we first write F * q as the disjoint union of the subsets T 1 , T 2 , T 3 of field elements t such that the corresponding index i in Definition 2 is 1, 2, 3 respectively. In other words:

T 1 = {t ∈ F * q | g(x 1 ) is a square}; T 2 = {t ∈ F * q | g(x 1
) is not a square but g(x 2 ) is}; T 3 = {t ∈ F * q | neither g(x 1 ) nor g(x 2 ) are squares}.

Then, we examine the points in f (T i ) for i = 1, 2, 3.

Clearly, a point (x, y) ∈ f (T 1 ) satisfies:

x = x 1 (t) = -1 + √ -3 2 - √ -3 • t 2 1 + b + t 2
for some t = 0, or equivalently:

t 2 = - (1 + b) • (x -ζ) x -ζ 2 where ζ = -1 + √ -3 2 . ( 10
)
We denote by ω 1 ∈ F q (x) the rational function on the right-hand side of Eq. ( 10). The set f (T 1 ) is thus contained in the set of points (x, y) ∈ E(F q ) such that ω 1 is a nonzero square. And conversely, if (x, y) ∈ E(F q ) satisfies that ω 1 = t 2 for some t = 0, we get x = x 1 (t) and hence (x, y) = f (t) or f (-t) depending on the sign of χ q (y).

Thus, we obtain that f (T 1 ) is the set of points (x, y) ∈ E(F q ) such that ω 1 is a nonzero square. If we denote by K the function field of E, this set is thus in bijection with the set of places of degree 1 in K that split in the quadratic extension L 1 /K with L 1 = K[t]/(t 2 -ω 1 ). We can thus apply Lemma 1 with s = 1 and m = d = 2 to get:

#f (T 1 ) - 1 2 q ≤ (2 + g L1 ) • q 1/2 + 6q 1/4 + g L1 + 4,
where g L1 is the genus of the function field L 1 . After extending the field of scalars to F q , we can see that L 1 is ramified above exactly 4 places of K (corresponding to the two opposite points in E(F q ) where the rational function ω 1 vanishes and the two others where it has a pole), so the Riemann-Hurwitz formula gives g L1 = 3. Hence:

#f (T 1 ) - 1 2 q ≤ 5q 1/2 + 6q 1/4 + 7. ( 11
)
Similarly, a point (x, y) ∈ f (T 2 ) satisfies:

x = x 2 (t) = -1 - √ -3 2 + √ -3 • t 2 1 + b + t 2 ,
for some t = 0, or equivalently:

t 2 = - (1 + b)(x -ζ 2 ) x -ζ where, again, ζ = -1 + √ -3 2 . ( 12
)
Thus, for any point (x, y) ∈ f (T 2 ), the rational function ω 2 on the right-hand side of Eq. ( 12) is a nonzero square. But we clearly have:

ω 1 = (1 + b) 2 ω 2 ,
and it follows that if ω 2 is a nonzero square, then so is ω 1 . As a result, we must have f (T 2 ) ⊂ f (T 1 ). 6 Therefore:

f (F * q ) = f (T 1 ) ∪ f (T 2 ) ∪ f (T 3 ) = f (T 1 ) ∪ f (T 3 ) \ f (T 1 )
and we can thus complete our estimate if we can evaluate the cardinality of

f (T 3 ) \ f (T 1 ). Again, a point (x, y) ∈ E(F q ) is in f (T 3
) if and only if there exists some t ∈ F * q such that neither g(x 1 (t)) nor g(x 2 (t)) is a square, and

x = x 3 (t) = 1 -(1 + b + t 2 ) 2 /(3t 2 )
. The last relation is equivalent to:

t 4 + 3(x -1) + 2(1 + b) t 2 + (1 + b) 2 = 0. ( 13
)
As a biquadratic polynomial over the function field K of E, that polynomial in t, which we denote P (t), is clearly irreducible and has Galois group V 4 (since its constant coefficient is a square; see [28, Th. 2 and 3]). In particular, L ′ 3 = K[t]/(P ) is a Galois extension of K, and its 4 automorphisms send t to ±t and ±(1 + b)/t. Now, the set f (T 3 ) is in bijection with the set of places of K where the polynomial P has at least one root t (necessarily nonzero; and in that case, P splits completely) that further satisfies that neither g(x 1 (t)) nor g(x 2 (t)) is a square, or equivalently, that both -g(x 1 (t)) and -g(x 2 (t)) are nonzero squares. By construction of the Shallue-van de Woestijne encoding, we know that g(x 1 (t)) • g(x 2 (t)) • g(x 3 (t)) is a nonzero square for all t ∈ F * q , so that for any t as above, -g(x 1 (t)) is a nonzero square if and only if -g(x 2 (t)) is a nonzero square. Furthermore, the automorphisms of L ′ 3 = K[t]/(P ) that send t to ±t fix x 1 and x 2 , whereas those that send t to ±(1 + b)/t exchange them, as we can see from the fact that ω 2 = (1 + b) 2 /ω 1 . This ensures that the quadratic extension

L ′′ 3 = L ′ 3 [z]/ z 2 + g(x 1 (t)) of L ′
3 is in fact Galois of degree 8 over K, and f (T 3 ) is in bijection with the set of places of K that split completely in L ′′ 3 . Finally, an element (x, y) ∈ f (T 3 ) is not in f (T 1 ) exactly when ω 1 isn't a nonzero square, i.e. when -ω 1 is a square. As a result, up to possibly two points where -ω 1 vanishes, f (T 3 ) \ f (T 1 ) has the same number of elements as the set of places in K which split completely in the compositum L 3 = L ′′ 3 • K[w]/(w 2 + ω 1 ) (a Galois extension of degree 16, since the two fields are linearly disjoint by inspection of their ramification, as seen below). Thus, we can apply Lemma 1 with s = 1, d = 2 and m = 16 to get:

# f (T 3 ) \ f (T 1 ) - 1 16 q ≤ 2 + g L3 8 • q 1/2 + 6q 1/4 + g L3 8 + 4 + 2,
where g L3 is the genus of the function field L 3 . To compute that genus, we examine the ramification of the various fields involved, after an extension of scalars to F q . Clearly, (F q K)[w]/(w 2 + ω 1 ) is simply ramified over the four places corresponding to the points in E(F q ) with x = ζ or ζ 2 . Thus, that field has genus 4 again. On the other hand, since the discriminant of P is:

∆ = 48 • (1 + b) 2 • (x -1) 2 • 3(x -1) + 4(1 + b) 2 ,
the field F q L ′ 3 is ramified with ramification type (2, 2) over the places corresponding to the points in E(F q ) with x = 1 or x = -(1 + 4b)/3. In turn, F q L ′′ 3 is ramified over the places in F q L ′ 3 where x 1 (t) 3 = -b or x 1 (t) = ∞. This gives 8 values of t, or 16 places of F q L ′ 3 (since each value of t corresponds to one value of x and two of y). Putting everything together and using Abhyankar's lemma, we obtain that the ramification divisor of F q L 3 over F q K has degree 4 • 8 + (4 • 2 • 2 + 16) • 2 = 96. Thus, the Riemann-Hurwitz formula gives 2g L3 -2 = 16 • 0 + 96, hence g L3 = 49 < 7 • 8, and thus:

# f (T 3 ) \ f (T 1 ) - 1 16 q ≤ 9q 1/2 + 6q 1/4 + 13. ( 14
)
Combining Eqs. ( 11) and ( 14), we get the following result, as expected.

Theorem 1. The number of points in the image f (F * q ) of the Shallue-van de Woestijne encoding to a BN curve is bounded as:

#f (F * q ) - 9 16
q ≤ 14q 1/2 + 12q 1/4 + 20.

Remark 1. While somewhat arbitrary, the numbering of the points x 1 , x 2 , x 3 in the definition of the Shallue-van de Woestijne encoding actually matters for the computation of the number of points: for example, it is not difficult to adapt the argument above to see that if the order was reversed, the image size would only be about 7/16 • q instead of 9/16 • q.

5 Obtaining Indifferentiability

In this section, we prove that, while f itself is clearly not an admissible encoding in the sense of Section 2.3, the tensor square f ⊗2 , as defined in Section 2.4, is indeed admissible, and hence the hash function:

m → f h 1 (m) + f h 2 (m) (15)
is indifferentiable from a random oracle when h 1 , h 2 are seen as independent random oracles to F * q . To see this, first note that f ⊗2 is obviously efficiently computable, and it is also samplable: a sketch of a sampling function is as follows. To find a uniformly random preimage (u, v) of some point P ∈ E(F q ), pick v ∈ F * q at random, and find all the preimages of P -f (v) (which can be done by solving three algebraic equations, corresponding to the three "branches" of f ). There are at most 4 such preimages. Then pick i ∈ {1, 2, 3, 4} at random and return the i-th preimage if it exists. Otherwise, start over with another v. The image size computation of the previous section guarantees that the expected number of iterations is finite, which ensures samplability. See [START_REF] Barthe | Verified indifferentiable hashing into elliptic curves[END_REF] for a complete formal treatment of the samplability of Icart's function, which is easily adapted to our case along the lines of the previous sketch.

Thus, all that remains to see to prove admissibility is that f ⊗2 is regular. We will show that using the results of Section 2.4, by proving that f is a welldistributed encoding. We have to bound the following sum:

S f (χ) = t∈F * q χ(f (t))
for every nontrivial character χ of E(F q ). As in the previous section, we break the sum into sums over T 1 , T 2 and T 3 which we treat separately.

To estimate the sum over T 1 , we introduce the covering curve h 1 : X 1 → E corresponding to the extension of function fields L 1 /K (with the notation of Section 4). In other words, a rational point in X 1 (F q ) is a tuple (x, y, t) such that (x, y) ∈ E(F q ) and x = x 1 (t) (or equivalently t 2 = ω 1 (x)). In particular, for any t ∈ T 1 , there are two rational points of X 1 whose third coordinate is t: if we let (x, y) = f (t), these two points are (x, y, t) and (x, -y, t), which map to χ(f (t)) and χ(f (t)) -1 under χ • h 1 . Thus, we get:

P∈X1(Fq) χ(h 1 (P)) = t∈T1 χ(f (t)) + t∈T1 χ(f (t)) -1 + O(1),
where the constant O(1) accounts for a bounded number of exceptional points (ramification, points at infinity). We would like to get rid of the second sum on the right-hand side. For that purpose, note that the "correct" y value corresponding to a given t is the one such that χ q (ty) = 1. It follows that:

P∈X1(Fq) 1 + χ q (ty) 2 χ(h 1 (P)) = t∈T1 χ(f (t)) + O(1),
and hence, by Lemma 2:

t∈T1 χ(f (t)) ≤ 2g X1 -2 + deg X1 (ty) • √ q + O(1) = 12 √ q + O(1), (16)
since g X1 = g L1 = 3 as seen before, and the rational functions t and y over X 1 are of degree 2 and 6 respectively. Similarly, to estimate the character sum:

χ(f (t)), (17)
we introduce the extension L 2 = K[t, z]/ t 2 -ω 2 , z 2 + g(x 1 (t)) of K associated to f over T 2 , and the corresponding covering curve h 2 : X 2 → E. A point in X 2 (F q ) is thus a tuple (x, y, t, z) such that (x, y) ∈ E(F q ), x = x 2 (t), and z is a square root of -g(x 1 (t)) ensuring that g(x 1 (t)) is not a square. For a given t ∈ T 2 , there are four rational points of X 1 whose third coordinate is t, namely (x, ±y, t, ±z) with (x, y) = f (t) and z = -g(x 1 (t)). As with T 1 , we can thus write the character sum [START_REF] Farashahi | Indifferentiable deterministic hashing to elliptic and hyperelliptic curves[END_REF] as:

t∈T2 χ(f (t)) = 1 2 P∈X2(Fq) 1 + χ q (ty) 2 χ(h 2 (P)) + O(1),
where the factor 1/2 accounts for the two values of z. By Lemma 2, it follows that:

t∈T2 χ(f (t)) ≤ 1 2 2g X2 -2 + deg X2 (ty) • √ q + O(1) = 20 √ q + O(1), (18)
since g X2 = g L2 = 13 by inspection of the ramification, and the rational functions t and y over X 2 are of degree 4 and 12 respectively.

Finally, to estimate the character sum:

t∈T3 χ(f (t)),
we introduce the covering curve h 3 : X 3 → E corresponding to the extension L ′′ 3 = K[t, z]/ P (t), z 2 + g(x 1 (t)) of K defined in Section 4. The expression of the character sum is the same as with T 2 :

t∈T3 χ(f (t)) = 1 2 P∈X3(Fq) 1 + χ q (ty) 2 χ(h 3 (P)) + O(1).
By Lemma 2, it follows that:

t∈T3 χ(f (t)) ≤ 1 2 2g X3 -2 + deg X3 (ty) • √ q + O(1) = 30 √ q + O(1), (19)
since g X3 = g L ′′ 3 = 17 by inspection of the ramification, and the rational functions t and y over X 2 are of degree 4 and 24 respectively.

Putting Eqs. ( 16), ( 18) and ( 19) together, we obtain that |S f (χ)| ≤ 62 √ q + O(1) for any nontrivial character χ, and hence f is well-distributed as required.

Using the statistical distance bound given in Section 2.4 together with [12, Th. 1], it follows that for a 2k-bit BN curve, the hash function given by Eq. ( 15) is ε-indifferentiable from a random oracle, where:

ε = 4 • 62 + O(q -1/2 ) 2 • #E(F q ) q • q D ≤ 2 14 + o(1) 2 -k • q D
if we denote by q D the number of queries made by the distinguisher.

Efficient Computation

Finally, we would like to describe a possible implementation of the Shallue-van de Woestijne encoding from Definition 2 that is both efficient and secure against side-channel analysis and other physical attacks. It is not difficult to meet what is more or less the standard of efficiency for elliptic curve encodings, as set by functions like Icart's [START_REF] Icart | How to hash into elliptic curves[END_REF]-namely, that an evaluation of the function should cost one exponentiation in the base field, plus a small, bounded number of faster operations. In the case of our encoding f , we simply need to compute the values x 1 , x 2 , x 3 , and decide, based on χ q (g(x 1 )) , χ q (g(x 2 )), which of those three values will be the abscissa of the output point. This simple implementation has two problems with respect to side-channel attacks, however.

One the one hand, computing the quadratic character is difficult to do in constant time, so the length of that part of the computation may leak information about the input. We propose to alleviate that problem using blinding: instead of computing χ q (g(x 1 )), we evaluate χ q r 2 1 • g(x 1 ) for some random r 1 ∈ F * q . If we then make sure that the quadratic character is implemented in such a way that evaluating χ q (a) and χ q (-a) takes the same time (which isn't hard to achieve), the duration of the computation of the two quadratic characters we need is completely independent of the input.

On the other hand, the naive way to choose the index i of the output abscissa involves several conditional branches. This opens up a (small) risk of timing attacks, as well as (more serious) possibilities for fault injection (i.e. glitch attacks). We avoid that problem by selecting the index using an algebraic formula depending on the two quadratic character values. It suffices to construct a function ψ of two variables such that: ψ(1, 1) = ψ(1, -1) = 1, ψ(-1, 1) = 2, ψ(-1, -1) = 3.

One such function is given by: ψ(α, β) = (α -1) • β mod 3 + 1.

Using that function, we propose the implementation of the encoding given in Algorithm 1.

Algorithm 1 Shallue-van de Woestijne encoding to BN curves.

  t∈T2

  α -1) • β mod 3 + 1 10: return xi, χq r 2 3 • t • x 3 i + b 11: end procedure

Later works such as[START_REF] Pereira | A family of implementation-friendly BN elliptic curves[END_REF] use a different point as the generator, and the corresponding construction does no longer ensure that 1 + b is a square. This only causes a minor inconvenience for our purposes, namely two extra elements of Fq that have to be treated separately in the encoding given in Section 3.

It has recently been pointed out by Ristenpart, Shacham and Shrimpton[START_REF] Ristenpart | Careful with composition: Limitations of the indifferentiability framework[END_REF] that this type of composition result does not apply to literally all cryptographic protocols, but only those which admit so-called "single-stage security proofs". This is not a significant restriction for the purpose at hand, as all protocols constructed so far using elliptic curve-valued hashing satisfy that requirement.

Technically, one can consider BN curves over fields Fp with p ≡ 1 (mod 12) as well, but they are usually avoided in practice, as the condition p ≡ 3 (mod 4) makes square roots more convenient to compute.

It does not matter for our purposes, but that inclusion is usually strict: indeed, f (T2) is smaller that the set of points in E(Fq) with an abscissa of the form x2(t), because the corresponding parameter t must satisfy the additional condition that g(x1(t)) is not a square.

Acknowledgments

We would like to thank Paulo Barreto for suggesting this problem, Sorina Ionica and himself for fruitful discussions, and the reviewers of LATINCRYPT 2012 for numerous useful comments.