EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS
Vol. 10, No. 2, 2017, 363-391
ISSN 1307-5543 – www.ejpam.com
Published by New York Business Global

On Indifferentiable Deterministic Hashing into Elliptic
Curves

Nafissatou Diarra1, Djiby Sow1,∗, Ahmed Youssef Ould Cheikh Khlil1

1 Laboratoire d’Algèbre, de Cryptographie, de Géométrie Algébrique et Aplications (LAC-
GAA, Cheikh Anta Diop University, Dakar, Senegal

Abstract. In this paper, we give new deterministic encodings based on Elligator’s model, for
some families of elliptic curves. These encodings are almost-injective and easily invertible. This
allows to make points in the image set of the encoding indistinguishable from uniform string of
bits, which is useful for applications in censorship circumvention. Following the idea of Farashahi
et al., we show that our encodings are well-distributed. And thus they give rise to hash functions
constructions indifferentiable from random oracles.

Key Words and Phrases: deterministic encodings, elliptic curves, random oracle, indifferentiable
hashing

1. Introduction

In Elliptic Curve Cryptography, many protocols [18] and encryption schemes (like the
the identity based-encryption of Boneh and Franklin [2]) need to hash into the group of
points of an elliptic curve. The main idea is the following: the image of a message (a
random string) m by the hash function F is F (m) = f(h(m)), where h is a classical
hash function and f is an encoding function that maps a point of Fq to an element of
the elliptic curve. As discussed by Brier et al. in [6], the construction H(m) = f(h(m)),
where f is a constant-time encoding and h is a classical hash function modeled as a
random oracle, can not replace a random oracle to the group of points of the elliptic curve
(excepted for some special encodings, such as Boneh and Franklin’s one [2]). In 2013,
Farashahi et al. [14] defined the notion of admissible encodings, which allow them to give
a sufficient condition for an encoding f to be indifferentiable from a random oracle. But
this is not applicable to the constant-time encodings (such as Icart’s encoding) since they
are not admissible. Hence, Farashahi et al. [14] proposed a more general construction
H(m) = f(h1(m)) + . . .+ f(hs(m)), which preserves the indifferentiability notion if the hi
are modeled as random oracles and s is strictly greater than the genus of the curve.

∗Corresponding author.

Email addresses: fifiramatou@gmail.com (N. Diarra), sowdjibab@yahoo.fr (D. Sow),
ahmed.youssef@ucad.edu.sn (A.Y.O.C. Khlil)

http://www.ejpam.com 363 c© 2017 EJPAM All rights reserved.



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 364

On another side, ECC has many applications on Internet (SSL/TLS, SSH, Tor [10],
Bitcoin,...); but it presents at least one drawback: for applications in censorship circum-
vention, points of elliptic curves are easy to distinguish from uniform random strings if
a suitable implementation is not used. The problem of making points of elliptic curves
indistinguishable from uniform random strings was investigated by Möller [11], Bernstein
et al. [4], Tibouchi [17].

The first approach is Möller’s one. In 2004 [11], Möller proposed to modify protocols
so that transmitted points lie either on the given elliptic curve or in its quadratic twist
[5]. But this approach imposes twist-security. The second approach, called Elligator,
is the one proposed by Bernstein et al. in [4]. It is based on the construction of an
efficient injective and invertible encoding ψ that maps a subset S ⊆ Fq (where q prime
and S ∩ −S = {0}), to the group E(Fq) of an elliptic curve E over Fq. Since the map
is injective and invertible, Bernstein et al. consider that a point P ∈ Im(ψ) of the curve
can be viewed as the string representation of the unique ψ−1(P ). Moreover, if q is chosen
such that #S is relatively close to a power of 2, then a uniform P ∈ Im(ψ) will have a
close to uniform bit string representation. This method has the advantage to not impose
additional security requirements on the quadratic twist of the curve, but it relies on the
existence of the injective encoding ψ.

Recently [17], Tibouchi proposed a new method, called Elligator-Squared, which sup-
ports more elliptic curves than Elligator. While Elligator is used to represent a point P
in the curve by a preimage under an injective encoding, in Elligator-Squared, a point P
in the curve is represented by a randomly sampled preimage under a surjective map.

In Binary-Elligator-Squared [5], a comparison between Elligator and Elligator-Squared
is done. Elligator is better for protocols using a fixed base point (such as static ECDH),
but Elligator-Squared is better for protocols using a variable base point (such as ElGamal
encryption). Even if Elligator-Squared constructs a surjective map, it uses an injective
encoding as Elligator. To our knowledge, only a few examples of such encodings exist
[5, 4, 13, 12]. This is one of the motivations of this paper.

Organization of the paper:

• Section 2 recalls some definitions about square roots in finite fields (2.1) and gives
an overview of existing encodings into elliptic curves (2.2).

• Sections 3 and 4 present the contributions of this paper as follows:

– In section 3, we revisit Elligator’s methods for constructing almost-injective and
invertible encodings for some models of curves: (3.1) generalized Huff curves
x(ay2 − 1) = y(bx2 − 1), (3.2) classical Huff curves αx(y2 − 1) = βy(x2 − 1),
(3.3) Edwards curves x2 + y2 = 1 + dx2y2 and (3.4) Weierstrass model y2 =
x3 + ax2 + c.

– Section 4 begins by a review of well-distributed encodings (4.1), as defined in
[6, 14]. Then we show (4.3) how one can obtain a hash function indifferentiable
from a random oracle using one of the previous encodings and following the
methodology in [6, 14].



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 365

2. Preliminaries

2.1. Squares and square roots

Let q be an odd prime power.

(i) The quadratic character is the function χ defined by χ : Fq → Fq : u 7→ χ(u) =
u(q−1)/2 and verifying: χ(u) = 1 if u is a non-zero square; χ(u) = −1 if u is a
non-square; and χ(u) = 0 if u = 0. The following properties are also verified:
χ(uv) = χ(u) ·χ(v) for any u, v ∈ Fq; χ(a2) = 1 for any a ∈ F∗q ; and if q ≡ 3 mod 4,
χ(−1) = −1, χ(χ(u)) = χ(u), for any u ∈ Fq. If q ≡ 1 mod 4, then χ(−1) = 1.

(ii) Define F2
q = {a2 : a ∈ Fq} (see [4]). A square root function

√
for Fq is defined

by:
√

: F2
q → Fq : a2 7→

√
a2 = ±a. For q ≡ 3 mod 4, a

q+1
4 is called the

principal square root of a; therefore one can take the principal square root as a

square-root function, i.e., take
√
F2
q = F2

q . For an odd prime q, one can take
√

F2
q =

{0, 1, ..., q−12 }.

2.2. An overview of existing encodings into elliptic curves

We give here an overview of main existing encodings for elliptic curves.

2.2.1. Trivial encoding

For an elliptic curve Ea,b : y2 = x3 + ax + b, the simplest way to construct a point of
Ea,b is to use the trivial encoding, also known as the try-and-increment method. The
idea is to pick a x-coordinate and try to deduce the y-coordinate by computing a square
root: choose a random element u ∈ F∗q and compute u3 + au + b; and then test whether

u3 + au+ b is a square in Fq. If it’s the case, then returns (x, y) = (u,±
√
u3 + au+ b) as

a point of the curve. Otherwise, one can choose another u in Fq and try again. But this
method has at least one drawback, that is it cannot run in constant time: the number of
operations depends on the input u. In practice the input u is the message m we want to
hash; thus running this algorithm can allow the attacker to guess some information about
m.

2.2.2. Encoding for supersingular curves

A supersingular curve over Fq is an elliptic curve E such that |E(Fq)| = q + 1. For q ≡ 2
mod 3, the curve defined by Eb : y2 = x3+b is a supersingular one. In their identity-based
scheme[2], Boneh and Franklin proposed the function f : u 7→ ((u2−b)

1
3 , u) that constructs

a point of Eb, given any u ∈ Fq. This function allows them to construct the public key
Qid(a point on the supersingular curve) corresponding to the identity id ∈ {0, 1}∗. But it
is well-known that supersingular curves are useless for cryptographic concerns because of
the MOV attack[1]: that is the DLP on Eb can be reduced to the DLP in Fq. To avoid
these attack, a large q should be used.



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 366

2.2.3. The SWU algorithm

In 2006[15], Shallue and van de Woestjine proposed an algorithm that generates, in poly-
nomial time, a point of an elliptic curve Ea,b given by its Weierstrass equation.
Let Fq be a finite field of characteristic at least 5, and g(x) = x3 + ax + b be a polyno-
mial in Fq[x], with a 6= 0. We know from the Skalba’s theorem [16] that there exist four
non-constant rational functions X1(t), X2(t), X3(t), X4(t) ∈ Fq(x) such that:

g(X1(t
2)) · g(X2(t

2)) · g(X3(t
2)) = (X4(t))

2 (1)

It follows that at less one one the g(Xi(u
2)) must be a quadratic residue in the finite field

Fq, given any u ∈ Fq such that u2 is not a pole of the Xi’s, i = 1, 2, 3.
From identity (1), one can deduce an encoding function to the curve Ea,b : y2 = g(x).

It suffices to set (x, y) = (Xi(u
2),
√
g(Xi(u2))), where i is the smallest indice such that

g(Xi(u
2)) is a quadratic residue.

Even if this construction defines a constant-time encoding, it presents at least one draw-
back. In fact, the rational functions Xi(t) are large and complex enough to make them
difficult to implement. And there is no deterministic polynomial time for computing a
square root in Fq, unless making additional hypotheses on q. For example, when q ≡ 3
mod 4, then computing a square root is simply an exponentiation.

2.2.4. Icart’s function

Let q = 2 mod 3; so the map x 7→ x3 is a bijection and then computation of a cubic
root can be done as an exponentiation. In [9], Icart defined a new encoding function,
based on the following idea: intersect the line y = ux + v with the Weierstrass curve
Ea,b : y2 = x3 + ax+ b , with a, b ∈ Fq. He defined the encoding function:

fa,b : Fq → Ea,b

x 7→ fa,b(u) =

(
(v2 − b− u6

27
)1/3 +

u2

3
, ux+ v

)
where v = (3a − u4)/6u. As shown in the paper, this function presents many interesting
properties. In fact, it can be implemented in polynomial time with O(log3 q) operations.
The inverse function f−1a,b is also computable in polynomial time. Icart also showed that

|f−1a,b (P )| ≤ 4, given a point P on the elliptic curve. This results from the fact that to

compute f−1a,b (P ), it’s sufficient to solve the degree 4 polynomial over Fq:

u4 − 6u2x+ 6uy − 3a = 0

Moreover, Icart showed that the cardinal of the image set Im(fa,b) is greater than q/4 and
made the following conjecture(proved later by Tibouchi and Fouque in [8]): the size of

Im(fa,b) is approximately
5

8
of the size of the curve Ea,b.



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 367

2.2.5. Encoding and extraction for Hessian curves

Let d ∈ Fq with d3 6= 1. A Hessian curve(a curve with a point of order 3) Hd over Fq is
given by the equation x3 + y3 + 1 = 3dxy. For q ≡ 2 mod 3, Farashahi[7] applied Icart’s
method to the set Hd(Fq) of Fq-rational points of Hd. He obtained the function:

hd : Fq 7→ Hd(Fq)
u 7→ hd(u) = (x, y)

defined by

• hd(u) = (x, y) if u 6= −1, where x = −u
(
d3u3+

u3 + 1

)1/3

, v = −
(
d3u3+

u3 + 1

)1/3

+ du;

• and hd(u) = O if u = −1, where O is the point at infinity.

The map hd is well-defined since hd(u) is a point of Hd(Fq), for u ∈ Fq. This encoding
function for Hessian curves is less general than Icart’s one, but has many other interesting
properties. In fact, Farashahi showed that the size of the image set hd(Fq) is at least q/2
an that the inverse function h−1d can be easily described. He also studied the possibility
to extract random bits from the image hd(u) of an element u ∈ Fq.

2.2.6. Injective encoding for Edwards curves: Elligator-1

An Edwards curve Ed defined over Fq is a model of elliptic curve given by the equation:
Ed : x2 + y2 = 1 + dx2y2 with d /∈ {0, 1} and d is not a square.

In [4], Bernstein et al. defined an encoding that maps an element of Fq to a point of
the curve Ed. Their work used the general method proposed by Fouque et al. in [13]. Note
that, in their updated paper [12], Fouque et al. have also proposed an explicit encoding
for Edwards curves, based on their previous work [13]. The encoding process of Bernstein
et al. in [4] is described in the following theorem:

Theorem 1. Let q be a prime power congruent to 3 modulo 4. Let s be a nonzero element
of Fq with (s2 − 2)(s2 + 2) 6= 0. Define c = 2/s2. Then c(c − 1)(c + 1) 6= 0. Define
r = c+ 1/c and d = −(c+ 1)2/(c− 1)2. Then r 6= 0, and d is not a square. The following
elements of Fq are defined for each t ∈ Fq \ {0, 1}:

u = (1− t)/(1 + t), v = u5 + (r2 − 2)u3 + u;

X = χ(v)u, Y = (χ(v)v)(q+1)/4χ(v)χ(u2 + 1/c2);

x = (c− 1)sX(1 +X)/Y, y = (rX − (1 +X)2)/(rX + (1 +X)2).

Furthermore x2 + y2 = 1 + dx2y2; uvXY x(y + 1) 6= 0 and Y 2 = X5 + (r2 − 2)X3 +X.

The authors also showed that the image set of the map can be easily described. Fur-
thermore, this map can be used for injective encoding into the curve, considering only half
of the points of Fq.



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 368

3. Elligator’s methods revisited for various curves

In this section, we investigate the problem of constructing Almost-Injective and In-
vertible Encodings (AIIE) for some forms of curves, such as generalized Huff curves
x(ay2 − 1) = y(bx2 − 1), classical Huff curves αx(y2 − 1) = βy(x2 − 1), Edwards curves
x2 +y2 = 1+dx2y2 and the Weierstrass model y2 = x3 +ax2 +c. Our encodings are based
on the Elligator method due to Bernstein et al. [4], and their almost-injectivity means
that their restriction to a large enough subset of Fq is injective.

3.1. An AIEE for the generalized Huff model x(ay2 − 1) = y(bx2 − 1)

Fouque, Joux and Tibouchi proposed a method in [13], to construct an injective encod-
ing for an elliptic curve, viewed as a quotient of an odd hyperelliptic curve. The elliptic
curves compatible with their encoding are of the form: y2 = x3±4x2 +Ax (see [13], pages
11-12). They have updated their work in [12]. Bernstein et al., based on the work in [13],
have proposed in [4], an injective encoding for the Edward’s curve Ed : x2+y2 = 1+dx2y2,
where d is not a square. In [13] and [12], an explicit encoding was not proposed for the
special case of generalized Huff curve x(ay2 − 1) = y(bx2 − 1), with ab(a− b) 6= 0. As in
[4], our main contribution in this section is to adapt Elligator-1’s method (as well as those
of Fouque et al.) to generalized Huff curves.

Theorem 2. Let q ≡ 3 mod 4. Let c ∈ Fq such that c(c−1)(c+1) 6= 0. Let A = −(c− 1
c )

2;

then A 6= 0 and A is not a square. Let s =
c+ 1

c− 1
; then s 6= ±1. Let λ ∈ F∗q; define

b =
λ2

1− s2
and a = −bs2. Then a + b is a square, ab is not a square and ab(a − b) 6= 0.

Under the previous hypotheses, for each element z ∈ Fq \ {−1, 1}, the following elements
are well-defined:

u = (1− z)/(1 + z); v = −u5 + (c2 + 1/c2)u3 − u; X = χ(v)u;

Y = χ(v · (c2u2 − 1))
√
χ(v)v; α =

λ

2
=

√
a+ b

2
;

x =
(1 +X)(bX − α2(1 +X)2)

bαY
and y =

(1 +X)(aX − α2(1 +X)2)

aαY
.

Moreover, we have: Y 2 = −X5 + (2−A)X3 −X and x(ay2 − 1) = y(bx2 − 1).

Proof.

(i) Let us show that A 6= 0 and A is not a square.

• If A = 0 then c = 1/c so we have c2 = 1 and c = ±1 which is a contradiction.

• If A is a square, then we have −1 = A(c/c2 − 1)2 is a square which is a
contradiction since q = 3 mod 4.

(ii) Let us show that s 6= ±1 and b is well-defined.



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 369

• s = 1⇒ c− 1 = c+ 1 which is impossible.

• s = −1⇒ c− 1 = −c− 1⇒ 2c = 0 which is impossible since c 6= 0.

(iii) Let us show that a+ b is a square and ab(a− b) 6= 0.

• In fact, we have a+ b = −bs2 + b = b(1− s2) = λ2 which is a square.

• ab 6= 0 since a and b are both non-zero. We have a− b = 0⇒ −b(s2 + 1) = 0,
which is impossible.

(iv) By hypothesis, u is well-defined and u 6= 0. Suppose that v = 0; so u(−u4 + (c2 +
1/c2)u2 − 1) = 0. Since u 6= 0, then we have −u4 + (c2 + 1/c2)u2 − 1 = 0. Thus
u2 = −c2 or u2 = −1/c2 contradicting the fact that −1 is not a square.

(v) Since uv 6= 0 by above results, then X 6= 0.

(vi) Let us show that 1 + X 6= 0. If 1 + X = 0 then we have u = −χ(v) and v =
(χ(v))5−(c2+1/c2)(χ(v))3+χ(v) = χ(v)−(c2+1/c2−1)χ(v) = −χ(v)(c2+1/c2−2).
So we find v = −χ(v)(c− 1/c)2, then χ(v) = −χ(v), which is a contradiction.

(vii) Since X 6= 0 and Y 2 = −X5 + (c2 + 1/c2)X3 −X, similarly as 4, we have Y 6= 0.

(viii) We have−X5 + (c2 + 1/c2)X3 − X = −(χ(v)u)5 + (c2 + 1/c2)(χ(v)u)3 − χ(v)u =
χ(v)[−u5 + (c2 + 1/c2)u3 − u] = χ(v)v = Y 2.

(ix) x and y are well-defined since Y 6= 0.

(x) (x, y) verifies x(ay2 − 1) = y(bx2 − 1)?
At first we show that α4(X4−(2−A)X2+1) = (bX−α2(1+X)2)(aX−α2(1+X)2).
In fact, we have:
(bX−α2(1+X)2)(aX−α2(1+X)2) = abX2−bα2X(X2+2X+1)−aα2(X3+2X2+
X)+α4(1+4X+6X2 +4X3 +X4) = X4(α4)+X3(4α4− (a+b)α2)+X2(ab+6α4−
2α2(a+ b)) +X(4α4 − α2(a+ b)) + α4. Then using 4 = (a+ b)/α2 and A = ab/α4

yields that (bX − α2(1 +X)2)(aX − α2(1 +X)2) = α4(X4 − (2−A)X2 + 1). Since
a and b are not square, thus (ay2 − 1)(bx2 − 1) 6= 0. Now, we have:

bx2 − 1

ay2 − 1
=
a

b
· (1 +X)2(bX − α2(1 +X)2)2 − bα2Y 2

(1 +X)2(aX − α2(1 +X)2)2 − aα2Y 2

=
a

b
·
(
bX − α2(1 +X)2

aX − α2(1 +X)2

)
·

 (1 +X)2(bX − α2(1 +X)2)− bα2Y 2

bX−α2(1+X)2

(1 +X)2(aX − α2(1 +X)2)− aα2Y 2

aX−α2(1+X)2


=
a

b
·
(
bX − α2(1 +X)2

aX − α2(1 +X)2

)
·

 (1 +X)2(bX − α2(1 +X)2) + bα2X(X4−(2−A)X2+1)
bX−α2(1+X)2

(1 +X)2(aX − α2(1 +X)2) + aα2X(X4−(2−A)X2+1)
aX−α2(1+X)2


=
a

b
·
(
bX − α2(1 +X)2

aX − α2(1 +X)2

)
·
[
α2(1 +X)2(bX − α2(1 +X)2) + bX(aX − α2(1 +X)2)

α2(1 +X)2(aX − α2(1 +X)2) + aX(bX − α2(1 +X)2)

]
=
a

b
·
(
bX − α2(1 +X)2

aX − α2(1 +X)2

)
·
(
abX2 − α4(1 +X)4

abX2 − α4(1 +X)4

)
=
a

b
·
(
bX − α2(1 +X)2

aX − α2(1 +X)2

)
=
x

y



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 370

In the situation of the previous theorem, we can write x =
(1 +X)(bX − α2(1 +X)2)

bαY

= g(z) and y =
(1 +X)(aX − α2(1 +X)2)

aαY
= h(z). Therefore, we can define the encoding

function as follows.

Definition 1. The encoding function for the generalized Huff curve
E : x(ay2 − 1) = y(bx2 − 1) with ab(a− b) 6= 0 is the function φa,b : Fq → E(Fq) defined
as follows: φa,b(±1) = (0, 0); and φa,b(z) = (x, y) = (g(z), h(z)) if z 6= ±1.

NB: Our encoding function for generalized Huff curves does not include classical Huff
curves, because in our algorithm, ab is not a square, hence a and b cannot be square
simultaneously.

Proposition 1. In the situation of definition (1), if z ∈ Fq then −z ∈ φ−1a,b(φa,b(z)).

Proof. Let z ∈ Fq; if z = ±1 then φa,b(z) = (0, 0) = φa,b(−z) by definition. So we
can suppose that z 6= 1,−1. Let z′ = −z and define u′, v′, X ′, Y ′, x′, y′ from z′, with
(x′, y′) = φa,b(z

′). To show that (x, y) = (x′, y′), as in [4], we will compare u′ to u, v′ to v,
X ′ to X, Y to Y ′ and finally compute (x′, y′) = φa,b(z

′).

(i) u′ = 1−z′
1+z′ = 1+z

1−z = 1
u .

(ii) v′ = −u′5+(c2+1/c2)u′3−u′ = − 1
u5

+(c2+1/c2) 1
u3
− 1
u = v

u6
. Note that χ(v′) = χ(v).

(iii) X ′ = χ(v′)u′ = χ(v)u′ = χ(v)
u = 1

uχ(v) = 1
X .

(iv) Y ′ = χ(v′ · (c2u′2 − 1)/c)
√
χ(v′)v′ = χ(v′) · χ(u′2 − 1/c2)

√
χ(v′)v′. For the second

factor of Y ′, recall that v′ = v/u6 and χ(v′) = χ(v); so
√
χ(v′)v′ =

√
χ(v)v
u6

=√
χ(v)v
χ(u)2u6

=
χ(u)
√
χ(v)v

u3
.

Since χ((u2−1/c2)2c2u4) = 1, we have χ(u′2−1/c2) = χ((u′2−1/c2)(u2−1/c2)2c2u4)
. Thus, we have: χ(u′2 − 1/c2) = χ(u2(c2 − u2)(u2 − 1/c2)2).

Since v = −u5 + (c2 + 1/c2)u3 − u = −u(u2 − c2)(u2 − 1/c2), we then have χ(u′2 −
1/c2) = χ(uv(u2 − 1/c2)).

Finally, Y ′ = χ(v′)·χ(u′2−1/c2)
√
χ(v′)v′ = 1

u3

(
χ(u2)χ(v2)χ(u2 − 1/c2)

√
χ(v′)v′

)
=

Y

χ(v)u3
=

Y

(χ(v)u)3
=

Y

X3
.

(v) Since y′ = (1+X′)(aX′−α2(1+X′)2)
aαY ′ , X ′ = 1/X and Y ′ = Y/X3, then we have y′ =

X3

(
(1 + 1/X)(a/X − α2(1 + 1/X)2

aαY

)
=
X(X + 1)(aX − α2(1 +X)2)

aαY
= y, as de-

sired.

(vi) As for y′, one can show that x′ = x.



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 371

Hence we conclude that φa,b(−z) = φa,b(z), for every z ∈ Fq.

Proposition 2. In the situation of definition 1, if (x, y) ∈ φa,b(Fq) then: x 6= y and

1− 4α2η is a square, where η =
bx− ay
ab(x− y)

with α2 =
a+ b

4
.

Proof. Let (x, y) ∈ φa,b(Fq); by theorem 2, we know that x =
(1 +X)(bX − α2(1 +X)2)

bαY

and y =
(1 +X)(aX − α2(1 +X)2)

aαY
.

• x = y ⇒ a = b which is impossible.

• We have
x

y
=
a

b

(
bX − α2(1 +X)2

aX − α2(1 +X)2

)
and we obtain the equation X2+X(2− 1

ηα2
)+

1 = 0, where η =
bx− ay
ab(x− y)

. The discriminant δ =
1

(ηα2)2
(1−4ηα2) of this equation

has to be a square. This leads to 1− 4ηα2 is a square, as desired.

Proposition 3. For z ∈ Fq \ {±1}, the set of preimages of φa,b(z) is {−z, z}.

Proof.

• {z,−z} ⊆ φ−1a,b(φa,b(z)) follows from proposition 1.

• Let z ∈ Fq and z′ ∈ Fq such that φa,b(z
′) = φa,b(z). Define, as in the proof of

theorem 1 and in proposition 2, the following elements:

– for z: u, v,X, Y, x, y;

– for z1 = −z: u1, v1, X1, Y1, x1 = x, y1 = y;

– for z′: u′, v′, X ′, Y ′, x′ = x, y′ = y.

By the previous proposition and since x = x′ = x1, y = y′ = y1, we have η = η′ = η1.
So X, as well as X1 and X ′ are solutions of the equation F 2 + F (2− 1

ηα2 ) + 1 = 0.

Since X = 1/X1 then X 6= X1. In fact X = X1 implies that X2 = 1⇒ X = ±1⇒
χ(v)u = ±1; thus u = ±1 and 1−z

1+z = ±1, which is impossible if z 6= 0.

Now let us discuss the following cases.

– If X ′ = X: let us prove that χ(v) = χ(v′), u′ = u and z′ = z. Now we

have x =
(1 +X)(bX − α2(1 +X)2)

bαY
=

(1 +X)(bX − α2(1 +X)2)χ(v)

bαχ(c2u2 − 1)
√
χ(v)v

; but

u = χ(v)X so x =
(1 +X)(bX − α2(1 +X)2)χ(v)

bαχ(c2X2 − 1)
√
χ(v)v

and thus

χ(v) = χ
(
bα(1 +X)(bX − α2(1 +X)2)(c2X2 − 1)

)
. Similarly we have χ(v′) =

χ
(
bα(1 +X ′)(bX ′ − α2(1 +X ′)2)(c2X ′2 − 1)

)
. Since x = x′ and X = X ′, we

have χ(v) = χ(v′); therefore u′ = u and z′ = z.



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 372

– If X ′ = X1: as above we have χ(v′) = χ(v1), u
′ = u1 and z′ = z1.

Proposition 4. Let (x, y) ∈ E(Fq). If x − y 6= 0 and 1 − 4α2η is a square, with η =
bx− ay
ab(x− y)

, there exists z ∈ Fq such that φa,b(z) = (x, y).

Proof. Let (x, y) ∈ E(Fq) such that x − y 6= 0 and 1 − 4α2η is a square, where

η =
bx− ay
ab(x− y)

. The discriminant δ of the equation F 2 + F (2 − 1
ηα2 ) + 1 = 0 is then a

square, since 1 − 4α2η is a square. So there is at least one solution X = −1
2(2 − 1

ηα2 ) +
1

2ηα2 (1− 4α2η)(q+1)/4. Note that the two quantities

(1 +X)(bX − α2(1 +X)2)

αbx
and

(1 +X)(aX − α2(1 +X)2)

αay
are the same. In fact, as a

solution of the previous equation, X verifies X2 = −X(2− 1
ηα2 )−1; so bX−α2(1+X)2 =

X(bη − 1)

η
and aX−α2(1+X)2 =

X(aη − 1)

η
. Thus, we have

bX − α2(1 +X)2

aX − α2(1 +X)2
=

1− bη
1− aη

.

From η =
bx− ay
ab(x− y)

, we deduce that
x

y
=
a(1− bη)

b(1− aη)
; so

a(bX − α2(1 +X)2)

b(aX − α2(1 +X)2)
=
x

y
and

(1 +X)(bX − α2(1 +X)2)

αbx
=

(1 +X)(aX − α2(1 +X)2)

αay
.

Now we define Y =
(1 +X)(bX − α2(1 +X)2)

αbx
=

(1 +X)(aX − α2(1 +X)2)

αay
.

(i) First, we verify that Y 2 = −X5 + (2 − A)X3 − X. In fact, x and y are such that
bx2 − 1

ay2 − 1
=
x

y
; that is

a

b
(

(1 +X)2(bX − α2(1 +X)2)2 − bα2Y 2

(1 +X)2(aX − α2(1 +X)2)2 − aα2Y 2
) =

a

b
(
bX − α2(1 +X)2

aX − α2(1 +X)2
).

We have (1 +X)2(bX −α2(1 +X)2(ax−α2(1 +X)2)2−aα2Y 2(bX −α2(1 +X)2) =
(1 +X)2(aX − α2(1 +X)2(bx− α2(1 +X)2)2 − bα2Y 2(aX − α2(1 +X)2).
⇒ α4Y 2(1 +X)2(b−a) = X(1 +X)2(a− b)(bX−α2(1 +X)2)(aX−α2(1 +X)2).(*)

But recall from the proof of theorem 2 that (bX −α2(1 +X)2)(aX −α2(1 +X)2) =
α4(X4 − (2−A)X2 + 1). So (*) yields to:
α4Y 2(1 +X)2(b− a) = α4X(1 +X)2(a− b)(X4 − (2−A)X2 + 1). Finally we have
Y 2 = −X5 + (2−A)X3 −X as desired.

(ii) Define β = χ
(
Y (c2X2 − 1)

)
and u = βX.

(iii) Define v = −u5 + (c2 + 1/c2)u3 − u.

Now, we have v = β
(
−X5 + (c2 + 1/c2)X3 −X

)
. Since Y 2 = −X5+(2−A)X3−X

and q ≡ 3 mod 4, then v = βY 2 and χ(v) = χ(β) = β. From u = βX and β = χ(v),
we deduce that X = χ(v)u and Y 2 = βv = χ(v)v.

(iv) χ(v) = β = χ
(
Y (c2X2 − 1)

)
= χ

(
Y (X2 − 1/c2)

)
⇒ χ(Y ) = χ(v)χ

(
X2 − 1/c2

)
.

So Y = (χ(v)v)(q+1)/4χ(v)χ
(
X2 − 1/c2

)
.



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 373

(v) Finally let z =
1− u
1 + u

; so φa,b(t) = (x, y) by the previous construction. Note that z

is well-defined since u = ±X and X 6= 1, and z 6= ±1.

Efficiency of φa,b and φ−13 : As in Elligator-1 [4], the definitions of u, v,X, Y, x, y in
theorem 2 involve divisions by c, 1 + c, 1− c and αY , two computations of the quadratic
character χ (namely χ(v) and χ(u2 − 1/c2)), a square-root computation and some mul-
tiplications. One can reduce the number of multiplications, for example by factoring
v = −u5 + (c2 + 1/c2)u3 − u as v = −u(u2 − c2)(u2 − 1/c2). And u2 − 1/c2 can be
reused when computing Y = χ(v) · χ(u2 − 1/c2) ·

√
χ(v)v. The computation of χ(v)

and χ(u2 − 1/c2) can be replaced by exponentiations, and the square-root computation
is also replaced by an exponentiation with exponent a(q+1)/4 since q ≡ 3 mod 4. For
P = (x, y) ∈ Ea,b, checking wether or not P is in Im(φa,b) requires few multiplications,
one inversion and a computation of χ(1− 4α2η), where η = (bx− ay)/(ab(x− y)).

Elligator-Squared approach with Elligator-3 encoding: Recently [17], Tibouchi
proposed a new method, called Elligator-Squared, which supports more elliptic curves than
Elligator, and uses a surjective map to represent a point in the curve by its preimage under
this map. In fact, any P ∈ E(Fq) is represented by its randomly sampled preimage under
an admissible encoding of the form f⊗2 : (u, v) 7→ f(u) + f(v), where f : Fq → E(Fq) is
any encoding. In the same paper, Tibouchi gave a list of known encodings that meet the
requirements of Elligator-Squared construction, namely well-bounded encodings.

As for Elligator-1 encoding [4], the Elligator-squared construction can be applied to
our new Elligator-3 encoding. In fact, φa,b can be expressed in terms of a degree 2 covering
h : H → E of E by a certain elliptic curve H of genus 2 [17, 13]. Hence, using lemma 3 in
[17], one shows that φa,b is 2−well-distributed and is also a (2, 2)-well-bounded encoding,
since any P ∈ E(Fq) has at most 2 preimages (see proposition 3).

Also note that Elligator-3 encoding φa,b can be used to build a hash function into the
elliptic curve. But it cannot be directly used in the BLS signature scheme [3]. This results
from the fact that not all points of the elliptic curve are representable since the image set
does not cover the whole curve. And in the BLS signature scheme, which is a full-domain
signature scheme, all points need to be representable. Nevertheless, we can overcome this
limitation by combining Elligator-3 encoding and Elligator-Squared approach. In fact, the
resulting construction φ⊗2a,b : (u, v) 7→ φa,b(u) + φa,b(v), which we call Elligator-3-Squared,
is a surjective one.

3.2. An AIEE for the classical Huff model αx(y2 − 1) = βy(x2 − 1)

The classical Huff model αx′(y′2− 1) = βy′(x′2− 1) is included in the generalized Huff
model x(ay2−1) = y(bx2−1). In fact, one can simply set a = α2, b = β2 and then use the
change of variables (x, y) → (x′ = βx, y′ = αy). But the previous method is not directly
applicable to the classical Huff model, since the product ab has to be a non-square in Fq.
This is not the case when a = α2 and b = β2. To avoid these problems, one can possibly



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 374

use the translation suggested in [12], page 13.
In this section, we propose an encoding function for the classical Huff model αx(y2 −
1) = βy(x2 − 1) with αβ(α2 − β2)(α2 + β2) 6= 0, using Elligator-2 method as in [4].
Elligator-2 method’s propose an injective encoding for Weierstrass curves of the form
y2 = x3 + Ax2 + Bx. With this method, to encode into another form (such as Edwards,
Huff,...), it is necessary to use a birational equivalence. We propose the following algorithm
which allows to encode directly into Huff curves, without using any birational equivalence.

We begin by giving the following algorithm.

Algorithm 1.

Input: α, β ∈ Fq such that αβ(α2−β2)(α2+β2) 6= 0, u a non-square in Fq and r ∈ Fq
verifying α2 + uβ2r2 6= 0;
Output: A point (x, y) ∈ Eα,β : αx(y2 − 1) = βy(x2 − 1);

1. v =
β(α2 + uβ2r2)

α(α2 + β2)
;

2. ε = χ (v(αv − β)(α− βv));

3. t =
1

2

(
ε

(
1 + v2

v
− α

β
− β

α

)
+

(
α

β
+
β

α
+
v2 − 1

v

))
;

4. x = −ε
√
t(αt− β)

α− βt
;

5. y =
x

t
;

6. Return (x, y);

Theorem 3. Let q be a prime power, α, β ∈ Fq such that αβ(α2 − β2)(α2 + β2) 6= 0, u
a non-square in Fq and define the set R = {r ∈ Fq : α2 + uβ2r2 6= 0}. Let Eα,β be the
elliptic curve defined over Fq by αx(y2 − 1) = βy(x2 − 1). Then algorithm 1 defines a
deterministic encoding φα,β : R→ Eα,β, r 7→ φα,β(r) = (x, y).

Proof.

(i) Let us show that v is well-defined and v 6= 0:

By the hypothesis on α and β, we have α(α2 +β2) 6= 0; so v is well-defined. Suppose
that v = 0; this implies that α2 + uβ2r2 = 0, which is impossible by the definition
of R. Thus v 6= 0.



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 375

(ii) We show that ε is well-defined and ε 6= 0:

In fact, suppose that α−βv = 0; this implies that α2(α2 +β2)−β2(α2 +uβ2r2) = 0

and then r2 =
α4

uβ4
. This cannot happen since u is not a square in Fq; so ε is

well-defined.

Now suppose that ε = 0; so v(αv − β) = 0 and then αv − β since v 6= 0. But
αv − β = 0 ⇒ αβ(α2 + uβ2r2) − αβ(α2 + β2) = 0 ⇒ uαβ3r2 − αβ3 = 0 ⇒ r2 = 1

u ;
contradiction since u is not a square. Finally we have ε 6= 0, that is ε = ±1.

(iii) Let us show that t is well-defined and t 6= 0:

First see that αβv 6= 0; so t is well-defined. To show that t 6= 0, we have to consider
the cases where ε = 1 and where ε = −1.

• if ε = 1, then t = v 6= 0.

• if ε = −1, then t =
v(α2 + β2)− αβ

αβv
. Suppose that v(α2 + β2) − αβ = 0; so

β(α2 + uβ2r2)

α(α2 + β2)
= v =

αβ

α2 + β2
. This implies that uβ2r2 = 0 which is impossible

since r ∈ R \ {0}. Hence t 6= 0.

Finally t is well-defined and t 6= 0.

(iv) We show that x is well-defined and x 6= 0:

For this, we must show that
t(αt− β)

α− βt
is well-defined and is a non-zero square. As

previously, for t, we have to consider the cases where ε = 1 and where ε = −1.

• if ε = 1, then t = v and α− βt = α− βv = 0 which is impossible as previously

shown. Moreover we have χ

(
t(αt− β)

α− βt

)
= χ

(
v(αv − β)

α− βv

)
= ε = 1. Hence

we conclude that x is well-defined when ε = 1.

• if ε = −1, then t =
v(α2 + β2)− αβ

αβv
. Suppose that α − βt = 0; this implies

that βv = α and then r2 =
α4

uβ4
; contradiction since χ(u) = −1. Thus the

quantity
t(αt− β)

α− βt
is well-defined. Moreover we have:

χ

(
t(αt− β)

α− βt

)
=χ

(
α(αv − β)(v(α2 + β2)− αβ)

vβ3(α− βv)

)
=χ

(
αv − β
v(α− βv)

)
· χ
(
αβ
(
v(α2 + β2)− αβ

))
=ε · χ

(
αβ
(
v(α2 + β2)− αβ

))
= −χ

(
αβ
(
v(α2 + β2)− αβ

))



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 376

But χ
(
αβ
(
v(α2 + β2)− αβ

))
= χ

(
αβ

(
uβ3r2

α

))
= χ(u) = −1. Hence we

conclude that χ

(
t(αt− β)

α− βt

)
= 1 and x is well-defined when ε = −1. Further-

more x is a non-zero element of Fq.

(v) y is well-defined since t 6= 0 and y 6= 0 since x 6= 0.

(vi) We show that (x, y) ∈ Eα,β : αx(y2 − 1) = βy(x2 − 1):

In fact
y2 − 1

x2 − 1
=

x2

t2
− 1

x2 − 1
=

x2 − t2

t2(x2 − 1)
=

1

t2

 t(αt−β)
α−βt − t

2

t(αt−β)
α−βt − 1

 =
β

αt2

(
t3 − t
t2 − 1

)
=

β

αt
=
βy

αx
.

Hence we have αx(y2 − 1) = βy(x2 − 1), which ends the proof.

Proposition 5. For any r ∈ R, the set of preimages of φα,β(r) is {r,−r}.

Proof. It is obvious that φα,β(−r) = φα,β(r) since the definition of φα,β only uses r2.
Now let r′ ∈ R such that φα,β(r′) = φα,β(r). We want to show that r′ = r or r′ = −r.
From r′ we define the elements v′, ε′, t′, x′, y′ as in theorem 3. So φα,β(r′) = φα,β(r) ⇒
x′ = x and y′ = y. Furthermore we have t′ = t and then −ε′

√
t(αt−β)
α−βt = −ε

√
t(αt−β)
α−βt .

So ε′ = ε; and we have v′ = v by replacing ε′ by ε in t′ = t. Finally v = v′ implies that
r′2 = r2, that is r′ = ±r.

Proposition 6. In the situation of theorem 3, we have:

(i) Im(φα,β) is the set of (x, y) ∈ Eα,β such that:

• χ
(
uαβxy(α2 + β2 − αβ y

x
)
)

= 1 if x /∈
√
F2
q.

• and χ

(
uαβxy(α2 + β2 − αβx

y
)

)
= 1 if x ∈

√
F2
q;

(ii) For (x, y) ∈ Im(φα,β), define t =
x

y
and z =

t(αt− β)

α− βt
; so x ∈ {

√
z,−
√
z}.

Let r defined as follows:

r =
1

β

√
α(x(α2 + β2)− αβy)

uβy
if x = −

√
z; and r = α

√
αx

uβ(y(α2 + β2)− αβx)
if

x =
√
z. Then r ∈ R and φα,β(r) = (x, y).

Proof.

(i) For this statement, we have to show two things. The first one is that every (x, y) ∈
Im(φα,β) verifies the conditions mentioned above; the second is that any point
(x, y) ∈ Ea,b verifying these conditions, is in Im(φα,β).



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 377

• Let (x, y) ∈ Im(φα,β); so there exists r ∈ R \ {0} such that the elements

t =
x

y
, ε, v are defined as in theorem 3. We consider two cases:

– if ε = 1, so x = −

√
t(αt− β)

α− βt
/∈
√

F2
q and

x

y
= t = v =

β(α2 + uβ2r2)

α(α2 + β2)
.

Let us show that χ
(
uαβxy(α2 + β2 − αβ y

x
)
)

= 1. In fact, we have:

uαβxy(α2 + β2 − αβ y
x

) =uαby2(t(α2 + b2)− αb) = uαβy2

(
β(α2 + uβ2r2)

α
− αβ

)
=uαβy2

(
uβ3r2

α

)
= u2β4r2y2 which is a square.

– if ε = −1, so x =

√
t(αt− β)

α− βt
∈
√
F2
q and

x

y
= t =

v(a2 + b2)− ab
abv

. Let us

show that χ

(
uαβxy(α2 + β2 − αβx

y
)

)
= 1. In fact, we have:

uαβxy(α2 + β2 − αβx
y

) =uαβx2
(
α2 + β2 − αβt

t

)
= uαβx2

(
αβ

vt

)
=uαβx2

(
α2β2

v(α2 + β2)− αβ

)
= uαβx2

(
α3

uβr2

)
=
α4x2

r2
which is a square.

• Now let (x, y) ∈ Eα,β such that χ
(
uαβxy(α2 + β2 − αβ y

x
)
)

= 1 if x /∈
√

F2
q

and χ

(
uαβxy(α2 + β2 − αβx

y
)

)
= 1 if x ∈

√
F2
q .

We define r =
1

β

√
α(x(α2 + β2)− αβy)

uβy
if the first condition is verified; and

r = a

√
αx

uβ(y(α2 + β2)− αβx)
otherwise. First see that r is well-defined and

r 6= 0 in both cases since uαβxy(α2 + β2 − αβ y
x

) and uαβxy(α2 + β2 − αβx
y

)

are non-zero squares. Now let us show that r ∈ R.

– if r =
1

β

√
α(x(α2 + β2)− αβy)

uβy
, then α2+uβ2r2 = α2+uβ2

(
α
(
x(α2 + β2)− αβy

)
uβ3y

)
=
αx(α2 + β2)

βy
6= 0 since x 6= 0 and α(α2 + β2) 6= 0.

– if r = α

√
αx

uβ(y(α2 + β2)− αβx)
, then α2+uβ2r2 = α2+uβ2

(
α2(αx)

uβ (y(α2 + β2)− αbx)

)
=

α2y(α2 + β2)

y(α2 + β2)− αβx
6= 0 since y 6= 0 and α(α2 + β2) 6= 0.



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 378

Hence we have showed that r is well-defined and that r ∈ R \ {0}. Then
φα,β(r) = (x, y) follows from the following proof.

(ii) As previously, we consider two cases:

• First case: x = −
√
z /∈

√
F2
q and r =

1

β

√
α(x(α2 + β2)− αβy)

uβy
. Since r ∈

R \ {0}, we can define v, ε, t, x and y from r as in theorem 3. We have:

v =
β(α2 + uβ2r2)

α(α2 + β2)
=

β

α(α2 + β2)

(
α2 +

α
(
x(α2 + β2)− αβy

)
βy

)
=
αx(α2 + β2)

αy(α2 + β2)
=
x

y
.

ε =χ

(
v(αv − β)

α− βv

)
= χ

(
x
y (αxy − β)

α− β xy

)
= χ

(
x(αx− βy)

y(αy − βx)

)

But from the curve equation we know that
αx− βy
αy − βx

= xy; so ε = χ(x2) = 1.

Then t = v =
x

y
= t, x = −

√
t(αt− β)

α− βt
= −

√
t(αt− β)

α− βt
= −
√
z = x and

y =
x

t
=
x

t
= y. Hence we conclude that φ′(r) = (x, y) = (x, y).

• Second case: x =
√
z ∈

√
F2
q and r = α

√
αx

uβ(y(α2 + β2)− αβx)
. Since r ∈

R \ {0}, we can define v, ε, t, x and y from r as in theorem 3. We have:

v =
β(α2 + uβ2r2)

α(α2 + β2)
=

β

α(α2 + β2)

(
α2 +

α3βx

y(α2 + β2)− αβx

)
=

αβy

y(α2 + β2)− αβx
.

ε =χ

(
v(αv − β)

α− βv

)
= χ

 αβy
y(α2+β2)−αβx

(
α2βy

y(α2+β2)−αβx − β
)

α− αβ2y
y(α2+β2)−αβx


=χ

(
β3y(αx− βy)

α(αy − βx) (y(α2 + β2)− αβx)

)
= χ

(
β3xy2

α (y(α2 + β2)− αβx)

)
=χ
(
αβx

(
y(α2 + β2)− αβx

))
= −1 since χ

(
uαβxy(α2 + β2 − αβ y

x
)
)

= 1.

ε = −1 implies that t =
v(α2 + β2)− αβ

αβv
=

αβy(α2+β2)
y(α2+β2)−αβx − αβ

α2β2y
y(α2+β2)−αβx

=
x

y
= t. So

x =

√
t(αt− β)

α− βt
=

√
t(αt− β)

α− βt
=
√
z = x and y =

x

t
=
x

t
= y.



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 379

Hence we conclude that (x, y) ∈ Im(φα,β).

Efficiency of φα,β and φ−1α,β: For any r ∈ R, computing φα,β(r) takes 2 inver-

sions, 1 square-root computation, one computation of the quadratic character χ and some
multiplications. One can use Euclid’s algorithm to compute the inverses; note that the
computation of χ can be replaced by an exponentiation (with exponent (q − 1)/2); and if
q ≡ 3 mod 4, the square-root computation is also replaced by an exponentiation. Invert-
ing φα,β takes one essential exponentiation, the square-root computation to obtain r, and
one inversion.

Extending φα,β: We can extend the definition of φα,β on Fq as follows:

(i) if q ≡ 1 mod 4: we have R = F∗q . Define the function φα,β by φα,β(r) = φα,β(r) if

r ∈ R, and φα,β(0) = (0, 0).

(ii) if q ≡ 3 mod 4: We choose u = −1; then we have R = F∗q \
{
±α
β

}
. If in addition

α2 + β2 is not a square, define the function φα,β by:

• φα,β(r) = φα,β(r) if r ∈ R;

• φα,β(r) =

(
β
√
−(α2 + β2)

α2
,
β2
√
−(α2 + β2)

α(α2 + β2)

)
if r = ±α

β
;

• φα,β(0) = (0, 0).

We call φα,β the AIEE-For-Huff.

3.3. An AIIE for the classical Edwards model x2 + y2 = 1 + dx2y2

With Elligator-2’s method [4], to encode on Edwards curves, it is necessary to use a
birational equivalence. In this section, we propose an algorithm which encodes directly an
element of Fq to a point of an Edwards curves Ed : x2 + y2 = 1 + dx2y2, where d is not a
square, and without any birational equivalence.

Theorem 4. Let q be an odd prime power, and d ∈ F∗q such that d 6= ±1,−2 and d
is not a square. Let u be a nonzero non-square and let R be a subset of Fq defined by
R = {r ∈ F∗q : ur2 + 1 6= 0, ur2(1− d)− (1 + 3d) 6= 0, ur2(1 + 3d)− (1− d) 6= 0}.
For any non-zero r ∈ R, the following elements are well-defined:

v =
(d− 1)ur2 − 3− d
ur2(d− 1) + 1 + 3d

; ε = χ[(1− v2)(1− dv2)];

x =
ε(v + 1)(dv + 1) + dv2 − 1

2d(v + 1) + (1− d)
; y = −ε

√
1− x2

1− dx2
.

Furthermore, ε 6= 0 and x2 + y2 = 1 + dx2y2.

Proof.



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 380

(i) v is well-defined by the definition of the set R.

(ii) Since d is not a square, then ε is well-defined. Now let us show that ε 6= 0. Suppose
that 1−v = 0; this implies that ur2(d−1)+3d+1−(d−1)ur2+3+d = 0⇒ d = −1;
impossible by our hypothesis on d. Suppose that 1+v = 0 ; thus ur2(d−1)+d−1 = 0
and ur2 + 1 = 0. This is impossible by the definition of the set R. Finally ε is well-
defined and is non-zero.

(iii) x is well-defined when 2d(v+ 1) + 1−d 6= 0. Suppose that 2d(v+ 1) + 1−d = 0; this
implies that 2d(d−1)ur2−2d(3+d)+2dur2(d−1)+2d(1+3d)+ur2(1−d)(d−1)+
(1− d)(1 + 3d) = 0⇒ 4dur2(d− 1)−ur2(d− 1)2− 4d(1− d) + (1− d)(1 + 3d) = 0⇒
(d−1)

(
4dur2 − ur2(d− 1) + 4d− 1− 3d

)
= 0. This leads to ur2(1+3d)+(d−1) = 0,

which contradicts the definition of R.

(iv) y is well-defined when 1− dx2 6= 0 and χ
(

1−x2
1−dx2

)
= 1. At first, recall that d is not

a square by hypothesis; so 1− dx2 6= 0. Now let us show that
1− x2

1− dx2
is a non-zero

square. For this, we must consider two cases:

• If ε = 1, then x = v and χ
(

1−x2
1−dx2

)
= χ

(
1−v2
1−dv2

)
= ε = 1.

• If ε = −1, then x = −(v+1)(d+1)+(d−1)
2d(v+1)+(1−d) . Let H(x) = 1−x2

1−dx2 = (1−x)(1+x)
1−dx2 . Our

objective now is to write χ(H(x)) in function of χ(H(v)), and then use the fact
that χ(H(v)) = ε = −1. First we compute 1− x, 1 + x, 1− dx2 and find:
[2d(v + 1) + (1− d)] (1 + x) = (v + 1)(d− 1);
[2d(v + 1) + (1− d)] (1− x) = (v + 1)(3d+ 1) + 2(1− d);
and [2d(v + 1) + (1− d)]2 (1− dx2) = (d− 1)2(1− dv2).

Then H(x) =
(1− x)(1 + x)

1− dx2
=

((v + 1)(3d+ 1) + 2(1− d)) · [(v + 1)(d− 1)]

(d− 1)2(1− dv2)

=
(v + 1)[(v + 1)(3d+ 1) + 2(1− d)]

(d− 1)(1− dv2)
=

H(v)

1− v

(
(v + 1)(3d+ 1) + 2(1− d)

d− 1

)
,

where H(v) = (1− v)(1 + v)/(1− dv2). Replace v by its value to see that:

(v+ 1)(1 + 3d) + 2(1−d) =
2(d− 1)[(1 + ur2)(1 + 3d)− ur2(d− 1)− (1 + 3d)]

ur2(d− 1) + (1 + 3d)

and (1− v)(d− 1) =
4(d+ 1)(d− 1)

ur2(d− 1) + (1 + 3d)
; so (v+1)(3d+1)+2(1−d)

(1−v)(d−1) = ur2.

Since r 6= 0 in R, then χ(H(x)) = χ(H(v)) · χ(ur2) = 1 as desired.

Hence (1−x2)/(1−dx2) is a non-zero square and y is well-defined. Moreover (x, y) verifies
x2 + y2 = 1 + dx2y2.

Definition 2. In the situation of theorem 4, the encoding function for the Edwards curve
Ed : x2 + y2 = 1 + dx2y2 is the function φd : R→ Ed : r 7→ φd(r) = (x, y).

The following proposition characterizes the image set of the function φd.



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 381

Proposition 7. (i) For r ∈ R, the set of preimages of φd(r) is {−r, r}.

(ii) Im(φd) is the set of (x, y) ∈ Ed such that 1 − x2 6= 0, x 6= −(d+ 1)

2d
and χ[u(d −

1)(1− x)(x(3d+ 1) + d+ 3)] = 1.

(iii) Let (x, y) ∈ Im(φd) and define r as follows:

r =

√
x(3d+ 1) + d+ 3

u(d− 1)(1− x)
, if y /∈

√
F2
q, and r =

√
(d− 1)(1− x)

u[x(3d+ 1) + d+ 3)]
, if y ∈

√
F2
q.

Then r ∈ R and φd(r) = (x, y).

Proof.

(i) It is obvious that φd(−r) = φd(r) since the definition of φd only uses r2. Now let
r′ ∈ R such that φd(r

′) = φd(r). We want to show that r′ = r or r′ = −r.
From r′ we define the elements v′, ε′, t′, x′, y′ as in theorem 4. So φd(r

′) = φd(r) ⇒
x′ = x and y′ = y. Thus we have −ε′

√
(1−x2)
1−dx2 = −ε

√
(1−x2)
1−dx2 . So ε′ = ε; and we have

v′ = v by replacing ε′ by ε in x′ = x. Finally v = v′ implies that r′2 = r2, that is
r′ = ±r.

(ii) Forward part: Let (x, y) ∈ Im(φ4), we need to show 1 − x2 6= 0, x 6= −d+1
2d and

χ[u(d − 1)(1 − x)(x(3d + 1) + d + 3)] = 1. Since (x, y) ∈ Im(φ4), then there exists
r ∈ R such that φ4(r) = (x, y). From r, define v and ε as in theorem 4.

If ε = 1, then x = v =
(d− 1)ur2 − 3− d
ur2(d− 1) + 1 + 3d

. We have 1 + x =
2(d− 1)(ur2 + 1)

ur2(d− 1) + 1 + 3d
,

1 − x =
4(d+ 1)

ur2(d− 1) + 1 + 3d
and x + d+1

2d =
(d− 1)[(3d+ 1)ur2 + d− 1]

2d[(d− 1)ur2 + 1 + 3d]
, thus

1 + x 6= 0, 1 − x 6= 0 and x 6= −d+1
2d , by definition of R. Moreover, we have

x(3d+ 1) + d+ 3 =
4ur2(d− 1)(d+ 1)

ur2(d− 1) + 1 + 3d
; hence u(d− 1)(1− x)(x(3d+ 1) + d+ 3) =

16u2r2(d− 1)2(d+ 1)2

(ur2(d− 1) + 1 + 3d)2
which is a nonzero square by definition of R, as desired.

If ε = −1, then x =
−(v + 1)(d+ 1) + (d− 1)

2d(v + 1) + (1− d)
=

d− 1− ur2(d+ 3)

ur2(3d+ 1) + d− 1
. We have 1−

x =
4ur2(d+ 1)

ur2(3d+ 1) + d− 1
, 1+x =

2(d− 1)(ur2 + 1)

ur2(1 + 3d) + d− 1
and x+d+1

2d =
(d− 1)[ur2(d− 1) + 1 + 3d]

2d[ur2(1 + 3d) + d− 1]
,

thus 1 + x 6= 0, 1 − x 6= 0 and x 6= −d+1
2d , by definition of R. Moreover, we have

x(3d+ 1) + d+ 3 =
4(d− 1)(d+ 1)

ur2(3d+ 1) + d− 1
; hence u(d− 1)(1− x)(x(3d+ 1) + d+ 3) =

16u2r2(d− 1)2(d+ 1)2

(ur2(d− 1) + 1 + 3d)2
, which is a nonzero square by definition of R, as desired.



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 382

Reverse part: Let (x, y) ∈ Ed such that 1 − x2 6= 0, x 6= −d+1
2d and χ[u(d − 1)(1 −

x)(x(3d+1)+d+3)] = 1. We want to show that (x, y) ∈ Im(φd). For this, we consider
the cases where y = −

√
(1− x2)/(1− dx2) and where y =

√
(1− x2)/(1− dx2).

• If y = −
√

(1− x2)/(1− dx2), put r =
√

x(3d+1)+d+3
u(d−1)(1−x) then r is well defined.

First we need to show that r ∈ R. We have:

- r 6= 0, since χ[u(d− 1)(1− x)(x(3d+ 1) + d+ 3)] = 1,

- ur2 + 1 = 0⇒ 1 + x = 0 which is impossible,

- ur2(1− d)− (1 + 3d) = 0⇒ 4(d− 1)(d+ 1) = 0 which is impossible,

- ur2(1 + 3d)− (1− d) = 0⇒ x = −d+1
2d which is impossible.

Now, from r, define v, ε, x and y as in theorem 4. Our objective is to show that
x = x and y = y.
From (d − 1)ur2 − (3 + d) = 4x(d + 1)/(1 − x) and ur2(d − 1) + (1 + 3d) =

4(d + 1)/(1 − x), we deduce v = x. So ε = χ
(

1−x2
1−dx2

)
= 1 and x = v = x.

Finally we have y = −ε
√

1−x2
1−dx2 = y.

• If y =
√

(1− x2)/(1− dx2), put r =
√

(d−1)(1−x)
u[x(3d+1)+d+3)] , then r is well defined.

As for previous case, first, we need to prove that r ∈ R. We have:

- r 6= 0, since χ[u(d− 1)(1− x)(x(3d+ 1) + d+ 3)] = 1,

- ur2 + 1 = 0⇒ 1 + x = 0 which is impossible,

- ur2(1− d)− (1 + 3d) = 0⇒ x = −d+1
2d = 0 which is impossible,

- ur2(1 + 3d)− (1− d) = 0⇒ 4(d− 1)(d+ 1) = 0 which is impossible.

Now let us define v, ε, x and y from r. Replacing r by its value in v, we

find v =
−2− x(d+ 1)

d+ 1 + 2dx
and

1− v2

1− dv2
=

(d− 1)(1 + x)(x(1 + 3d) + d+ 3)

(d− 1)2(1− dx2)
=(

(1 + x)(1− x)

1− dx2

)(
(x(1 + 3d) + d+ 3)

(d− 1)(1− x)

)
.

Recall that (x, y) is in Ed and that χ

(
(x(1 + 3d) + d+ 3)

(d− 1)(1− x)

)
= −1 by hypoth-

esis, thus ε = −1 .

From v =
−2− x(d+ 1)

d+ 1 + 2dx
, we have x =

−(v + 1)(d+ 1) + (d− 1)

2d(v + 1) + (1− d)
= x. We

deduce that y = −ε
√

1− x2

1− dx2
=

√
1− x2

1− dx2
= y. Thus φd(r) = (x, y) as

desired.

(iii) Follows from the previous part of the proof.

Efficiency of φd and φ−1d :

For any r ∈ R, computing φd(r) takes 3 inversions, one computation of χ, one square-
root computation and some multiplications. Elligator-2 method [4] applied to Edwards



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 383

curves by using a birational equivalence, takes 5 inversions, one computation of χ, one
square-root computation and some multiplications. One can use Euclid’s algorithm to
compute the inverses, or use an exponentiation; note that the computation of χ can be
replaced by an exponentiation (with exponent (q−1)/2); and if q ≡ 3 mod 4, the square-
root computation is also replaced by an exponentiation. And as in [4], the computation
of χ can be combined into the square-root computation as follows. First compute a power

of 1−v2
1−dv2 as above, obtaining a square root of

1− v2

1− dv2
if

1− v2

1− dv2
is a square. If the square

of this power turns out to match
1− v2

1− dv2
then ε = 1 and x = v. Otherwise ε = −1

and
1− x2

1− dx2
= ur2

(
1− v2

1− dv2

)
(by definition of ur2, see proof of theorem 4); multiply the

previous power by r and by a precomputed power of u to obtain a square root of
1− x2

1− dx2
.

Similar comments apply to computing φ−1d ; there is one square-root computation, one
inversion and few multiplications. Also note that q is not required to be congruent to 3
modulo 4 to encode all points of Fq, as said in the next remark.

Extension of φd:

Our objective now is to extend the encoding function φd : R → E(Fq) to φd : Fq →
E(Fq). For this,we put φd(r) = φd(r) ∀r ∈ R and we must send all points r in Fq \ R to
points P in E(Fq)\Im(φd) via φd. For constructing such a point P in E(Fq)\Im(φd), we use
the characterization of the encoding φd (see proposition 7). Furthermore, if r, r′ ∈ Fq \R,
with r 6= r′, we need to have φd(r) 6= φd(r

′) in order to preserve the almost-injectivity of
φd. We can extend the definition of φd on Fq as follows.

(i) If χ((1 − d)(1 + 3d)) = 1 then R = F∗q when q ≡ 1 mod 4 and R = F∗q \ {±
√
−1
u }

when q ≡ 3 mod 4, thus we need 1 and 2 points in E(Fq) \ Im(φd) respectively
in order to extend φ4. Since (1, 0) and (−1, 0) are in E(Fq) \ Im(φd) by the above
characterization of Im(φd), then we propose the following:

(a) If q ≡ 1 mod 4: put φd(0) = (1, 0).

(b) If q ≡ 3 mod 4: put φd(0) = (1, 0) and φ4(±
√
−1
u ) = (−1, 0).

(ii) If χ((1 − d)(1 + 3d)) = −1 then R = F∗q \
{
±
√

1−d
u(1+3d) ,±

√
1+3d
u(1−d)

}
when q ≡ 1

mod 4 and R = F∗q \
{
±
√
−1
u ,±

√
1−d

u(1+3d) ,±
√

1+3d
u(1−d)

}
when q ≡ 3 mod 4, thus we

need 3 and 4 points in E(Fq)\ Im(φd) respectively in order to extend φ4. Since (1, 0)
and (−1, 0) are in E(Fq) \ Im(φd) by the above characterization of Im(φd), then we
need two other points in E(Fq) \ Im(φd). There exist different methods for doing
this. We propose in the following at least two examples.

(a) Example 1: If χ((d − 1)(d + 3)) = 1, then (0, 1), (0,−1) ∈ E(Fq) \ Im(φd),
therefore, we choose:



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 384

i. φd(0) = (1, 0), φ4

(
±
√

1−d
u(1+3d)

)
= (0,−1) and φ4

(
±
√

1+3d
u(1−d)

)
= (0, 1),

when q ≡ 1 mod 4 .

ii. φd(0) = (1, 0), φ4(±
√
−1/u) = (−1, 0), φ4

(
±
√

1−d
u(1+3d)

)
= (0,−1) and

φ4

(
±
√

1+3d
u(1−d)

)
= (0, 1) when q ≡ 3 mod 4.

(b) Example 2: If χ(−2(1 + d)) = 1, then
(
− d+3

1+3d , 2
√
−2(d+ 1)/(d− 1)

)
,(

− d+3
1+3d ,−2

√
−2(d+ 1)/(d− 1)

)
∈ E(Fq) \ Im(φd), therefore, we choose:

i. φd(0) = (1, 0), φ4

(
±
√

1−d
u(1+3d)

)
=
(
− d+3

1+3d , 2
√
−2(d+ 1)/(d− 1)

)
and

φ4

(
±
√

1+3d
u(1−d)

)
=
(
− d+3

1+3d ,−2
√
−2(d+ 1)/(d− 1)

)
, when q ≡ 1 mod 4

.

ii. φd(0) = (1, 0), φ4(±
√
−1/u) = (−1, 0),

φ4

(
±
√

1−d
u(1+3d)

)
=
(
− d+3

1+3d , 2
√
−2(d+ 1)/(d− 1)

)
and φ4

(
±
√

1+3d
u(1−d)

)
=(

− d+3
1+3d ,−2

√
−2(d+ 1)/(d− 1)

)
when q ≡ 3 mod 4.

We call φd the AIEE-For-Edwards.

3.4. An AIIE for the Weierstrass model y2 = x3 + ax2 + c

In this section, we propose an injective encoding for the the Weierstrass model y2 =
x3 + ax2 + c with char(Fq) = 3. The encoding comes from the following algorithm.

Algorithm 2.
Input: a, c ∈ Fq (with char(Fq) = 3) such that χ(−ac) = 1, u a non-square in Fq, r ∈ F∗q;
Output: A point (x, y) on Ea,c : y2 = x3 + ax2 + c;

1. s2 = − c
a

;

2. v =
ur2 − s2

s
;

3. ε = χ(v3 + av2 + c);

4. x =
v

2

(
1 +

s+ εv

s+ v

)
;

5. y = −ε
√
x3 + ax2 + c;

6. Return (x, y);

Theorem 5. Let a, c ∈ Fq (with char(Fq) = 3) such that χ(−ac) = 1, u a non-square in
Fq and r ∈ F∗q. Let Ea,c be the elliptic curve defined over Fq by y2 = x3 + ax2 + c. Then
algorithm 2 defines a deterministic encoding φa,c : F∗q → Ea,c, r 7→ φa,c(r) = (x, y).



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 385

Proof.

(i) By hypothesis c 6= 0 and a 6= 0; so v is defined. v = 0 ⇔ u = (r/s)2; contradiction
since u is not a square.

(ii) v3 + av2 + c 6= 0 since c 6= 0. This implies that ε 6= 0.

(iii) Suppose that v + s = 0; so ur2 = 0 which is impossible by our hypothesis on u and
r. Thus x is defined and x 6= 0, since v 6= 0.

(iv) We show that x3 + bx2 + c is a square. The first case is when ε = 1; so x = v and
χ(x3 + ax2 + c) = χ(v3 + av2 + c) = ε = 1. For the second case we have ε = −1;

so x =
sv

v + s
. Recall that as2 = −c, (s + v)3 = s3 + v3 and sv + s2 = ur2. So

(v+ s)3(x3 + ax2 + c) = s3v3 + as2v2(v+ s) + cv3 + cs3 = s3(v3 + av2 + c) and then
χ(x3 + ax2 + c) = χ(s(v + s))χ(v3 + av2 + c) = −χ(sv + s2) = −χ(ur2) = 1.
Hence x3+ax2+c is a non-zero square in both cases. Furthermore y2 = x3+ax2+c.

Proposition 8. In the situation of theorem 5, the following results hold:

(i) For r ∈ F∗q, the set of preimages of φa,c(r) under φa,c is {−r, r}.

(ii) Im(φa,c) is the set of (x, y) ∈ Ea,c such that χ(us(s + x)) = 1 if y /∈
√

F2
q, and

χ(us(s− x)) = 1 if y ∈
√

F2
q.

(iii) For (x, y) ∈ Im(φa,c), let r defined as follows:

r =
√

(s(s+ x))/u if y /∈
√

F2
q r = s

√
s/(u(s− x)) if y ∈

√
F2
q.

Then φa,c(r) = (x, y).

Proof.

(i) Same proof as proof of proposition 5.

(ii) Forward part: we show that any (x, y) ∈ Im(φa,c) verifies χ(us(s+x)) = χ(us(s−
x)) = 1. In fact, let r ∈ F∗q such that φa,c(r) = (x, y); and define v, ε from r. If

ε = 1, then x = v; so us(s + x) = us(s + v) = us

(
s+

ur2 − s2

s

)
= u2r2. Thus

χ(us(s + x)) = 1. If ε = −1, then x =
sv

s+ v
; so us(s − x) = us

(
s− sv

s+ v

)
=

us3

s+ v
= us3

(
1

s+ ur2−s2
s

)
=
s4

r2
. Thus χ(us(s− x)) = 1.

Reverse part: let (x, y) ∈ Ea,c such that χ(us(s − x))(if y =
√
x3 + ax2 + c) or

χ(us(s+ x)) = 1(if y = −
√
x3 + ax2 + c). We show that (x, y) ∈ Im(φa,c).

We consider the following two cases:



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 386

• if y = −
√
x3 + ax2 + c, let r =

√
s(s+ x)/u 6= 0; then define v, ε, x, y from r as

in theorem 6. So v =
ur2 − s2

s
=
s(s+ x)− s2

s
= x and ε = χ(v3 + av2 + c) =

χ(x3 + ax2 + c) = 1. This implies that x = v = x and y = −ε
√
x3 + ax2 + c =

−
√
x3 + ax2 + c = y. Hence (φa,c)(r) = (x, y) and (x, y) ∈ Im(φa,c).

• if y =
√
x3 + ax2 + c, let r = s

√
s/(u(s− x)) 6= 0 since us(s − x) is a non-

zero square. So define v, ε, x, y from r as in theorem 6. We then have v =

ur2 − s2

s
=

s3

s−x − s
2

s
=

sx

s− x
. Recall that as2 = −c and (s− v)3 = s3 − v3; so

(s− x)3(v3 + av2 + c) = s3x3 + as2x2(s− x) + c(s3 − x3) = s3(x3 + ax2 + c)⇒
ε = χ(v3 + av2 + c) = χ(s(s− x)) = −1 since χ(us(s− x)) = 1 by hypothesis,

and χ(u) = −1. Now replacing ε by −1 and v by
sx

s− x
in x shows that

x = x. Furthermore we have y = −ε
√
x3 + ax2 + c =

√
x3 + ax2 + c = y and

we conclude that (x, y) ∈ Im(φa,c).

(iii) Follows from the proof of the second statement.

Extending φa,c: As above, if f has a root, then we can use Elligator-2 method

[4]. For this case also, suppose that f(x) = x3 + ax2 + c 6= 0, ∀x ∈ Fq. Then R = F∗q . We

propose here to extend φa,c to Fq. Let φa,c : Fq → E(Fq) defined as follows:

• φa,c(r) = φa,c(r) = (x, y) if r ∈ R = F∗q ;

• for r = 0, let d ∈ Fq and put c =
−(d2 − a3 + a)2

a5
. Then −ac is a square and

f(s) =
s2d2

a2
is also a square. We use this result to extend φa,c as follows: φa,c(0) =(

s,
√
f(s)

)
.

We call φa,c the AIEE-For-WeierstrassChar3.

4. Hashing into elliptic curves

Brier et al. [6] showed that the construction H(m) = f(h1(m)) + f(h2(m)) is indif-
ferentiable from a random oracle, where f is the Icart’s encoding [9] and the h1, h2 are
modeled as random oracles. To show the indifferentiability, they bounded the statistical
distance between the distribution defined by their construction and the uniform distribu-
tion. Farashahi et al. [14] generalized the result of Brier et al. to all known deterministic
encodings to elliptic (and hyperelliptic curves). In fact, they showed that given a deter-
ministic encoding f , the construction H(m) = f(h1(m)) + . . . f(hs(m)) is indifferentiable
from a random oracle, if the hi are modeled as random oracles and s is strictly greater
than the genus of the target curve. Our objective here is to apply these results to one of
our encodings, namely the encoding φd for the Edwards curve x2 + y2 = 1 + dx2y2.



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 387

4.1. Admissible and well-distributed encodings

We recall the following definitions and theorems from [14] and [17].

Definition 3. Let S,R be two finite sets and F a function from S to R. Then F is an
ε-admissible encoding if it satisfies the following properties:

(i) computable, that is F is computable in deterministic polynomial time;

(ii) regular: for s uniformly distributed in S, the distribution of F (s) is ε-statistically
indistinguishable from the uniform distribution in R;

(iii) samplable: there is an efficient randomized algorithm I such that for any r ∈ R,
I(r) induces a distribution that is ε-statistically indistinguishable from the uniform
distribution in F−1(r).

F is an admissible encoding if ε is a negligible function of the security parameter.

Definition 4. Let E be an elliptic curve over Fq and a function φ : Fq → E(Fq).

(i) φ is a B-well-distributed encoding for a certain constant B > 0, if for any

nontrivial character ξ of E(Fq), the following holds:

∣∣∣∣∣∣
∑
r∈Fq

ξ(φ(r))

∣∣∣∣∣∣ ≤ B
√
q. If B

doesn’t depend on the security parameter (that allows to chose q) then φ is said to
be well-distributed.

(ii) φ is a (d,B)-well-bounded encoding, for positive constants d,B, if φ is B-well-
distributed and each point in E(Fq) have at most d preimages under φ.

Theorem 6.
Let h : T = T (Fq) → E = E(Fq) be a non constant morphism of curves, and ξ be
any nontrivial character of E(Fq). Assume that h does not factor through a nontrivial
unramified morphism Z → E, then∣∣∣∣∣∑

P∈T
ξ(h(P ))

∣∣∣∣∣ ≤ (2ĝ − 2)
√
q

, where ĝ is the genus of T . Furthermore, if q is odd and λ is a non constant rational
function on T , we have∣∣∣∣∣∑

P∈T
ξ(h(P ))χ(λ(P ))

∣∣∣∣∣ ≤ (2ĝ − 2 + 2 deg λ)
√
q



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 388

4.2. Indifferentiable Hashing

Let E be a curve with a Fq-rational point and J be its jacobian.

Theorem 7. [14]
If f : Fq → E(Fq) is a B-well-distributed encoding into E, then the statistical distance
between the distribution defined by the construction (u1, . . . , us) 7→ f(u1) . . . f(us) on J(Fq)
and the uniform distribution is bounded as follows:∑

D∈J(Fq)

∣∣∣∣Ns(D)

qs
− 1

#J(Fq)

∣∣∣∣ ≤ Bs

qs/2

√
#J(Fq)

where Ns(D) = #{(u1, . . . us ∈ (Fq)s : f(u1) + . . . f(us) = D} for D ∈ J(Fq).

As said in [14], this theorem shows that f is a well-distributed encoding and if s is
greater than the genus of the curve, the distribution of the new construction is statistically
indistinguishable from the uniform distribution. Moreover, it is admissible if f is also
computable and samplable, and the hash function m 7→ f(h1(m)) + . . . + f(hs(m)) is
indifferentiable from a random oracle if the h1, . . . , hs are modeled as random oracles into
Fq.

4.3. Application to the encoding φd

In this section, we apply the results and proofs of Farashahi et al. [14] (for the Shallue-
Woestijne-Ulas encoding) to one of our previous encodings. We will show that the encoding
φd over the Edwards curve x2 + y2 = 1 + dx2y2 when q ≡ 3 mod 4 is well-distributed,
and thus give rise to a indifferentiable hash function construction.

Recall that φd is an efficient almost-injective and invertible encoding from the subset
R = {r ∈ F∗q : ur2 + 1 6= 0, ur2(1 − d) − (1 + 3d) 6= 0, ur2(1 + 3d) − (1 − d) 6= 0} to the
elliptic curve Ed : x2 + y2 = 1 + dx2y2, and let Ω = Fq \R. By the invertibility of φd, we
know that for (x, y) ∈ Im(φd), there exists two preimages r,−r such that φd(±r) = (x, y).
When q = 3 mod 4, we have:

y =

√
1− x2

1− dx2
⇒ χq(y) = 1 and y = −

√
1− x2

1− dx2
⇒ χq(y) = −1. Thus:

- χq(y) = −1⇔ r2 =
(d− 1)(1− x)

u[x(3d+ 1) + d+ 3)]
Eq− (0)

- χq(y) = 1⇔ r2 =
x(3d+ 1) + d+ 3

u(d− 1)(1− x)
Eq− (1).

From now, the proof is similar to the one of of Farashahi et al (in [14] subsection 5.3).
By equation Eq − (1), we define the coverings hi : Ci → E, i = 0, 1, by the smooth

projective curve whose function fields (denoted Fq(x, y, r)) is the extension of Fq(x, y)
given by Eq− (i).

Since r is a rational function on Ci, we have a morphism fi : Ci → P1, such that
any point in A1(Fq) \ Ω has exactly two preimages in Ci for one of i = 0, 1, and none in



N. Diarra, D. Sow, A.Y.O.C. Khlil / Eur. J. Pure Appl. Math, 10 (2) (2017), 363-391 389

the other. Since q = 3 mod 4, then these two preimages are conjugate under y → −y.
Therefore, exactly one of them satisfies χq(y) = (−1)i. Let P ∈ Ci be that preimage; so
φd(u) = hi(P ).

Theorem 8. For any nontrivial character ξ of Ed(Fq), the following holds when q ≡ 3
mod 4: ∣∣∣∣∣∣

∑
r∈Fq

ξ(φd(r))

∣∣∣∣∣∣ ≤ 12
√
q + 31.

Proof. Let r ∈ R, Ω = Fq \ R and hi : Ci → Ed (i = 0, 1) defined as previously; also
define Ωi = {P ∈ Ci : fi(P ) ∈ Ω}. So we can write:

∑
r∈R

ξ(φd(r)) =
∑

P∈C0(Fq)\Ω0, χ(y)=+1

ξ(h0(P )) +
∑

P∈C1(Fq)\Ω1, χ(y)=−1

ξ(h1(P )) (*).

Also observe that:
1

2

∑
P∈Ci(Fq), χ(y)=0

ξ(hi(P )) +
∑

P∈Ci(Fq), χ(y)=(−1)i

ξ(hi(P )) =
∑

P∈Ci(Fq)
ξ(hi(P )) ·

(
1 + (−1)iχ(y)

2

)
.(**)

One can see that the first term of the left-hand side of this equality contains at most
2 · 2 = 4 terms, when expressing y2 in terms of x and by Eq− (0) and Eq− (1).
To estimate the right-hand side of the equality, one can use theorem 6. In fact, by

Eiseinstein criterion, h0 and h1 are totally ramified over points such that x =
−d− 3

3d+ 1
; so

they cannot factor through any unramified covering of Ed. Hence, applying theorem 6, we
have: ∑

P∈Ci(Fq)

ξ(hi(P )) ·
(

1 + (−1)iχ(y)

2

)
≤ (2gi − 2 + deg(y))

√
q

where gi is the genus of Ci and deg(y) is the degree of y seen as a rational function on
Ci. Denote by eP the ramification index at P and by di the degree of hi; since the hi are

ramified only at x =
−d− 3

3d+ 1
, then by the Riemann-Hurwitz formula and using the fact that

any point has two conjugate preimages, we have 2gi−2 = di(2gEd−2)+
∑

P∈Ci(eP −1) =

di(2 · 1− 2) + 2(2− 1) +
∑

P∈Ci,x 6=−t
(eP − 1) = 0 + 2 + 0 = 2. Hence Ci is a curve of genus

gi = 2.
On the other side, we have deg(y) = [Fq(x, y, r) : Fq(x, y)] · [Fq(x, y) : Fq(y)] = 2 ·2 = 4.

Finally, we have:∑
P∈Ci(Fq)

ξ(hi(P )) ·
(

1 + (−1)iχ(y)

2

)
≤ (2 · 2− 2 + 4)

√
q = 6

√
q.



REFERENCES 390

Now it follows from (*) and (**) that:∣∣∣∣∣∑
r∈R

ξ(φd(r))

∣∣∣∣∣ = 2 ·

 ∑
P∈Ci(Fq)

ξ(hi(P )) ·
(

1 + (−1)iχ(y)

2

)
− 1

2

∑
P∈Ci(Fq), χ(y)=0

ξ(hi(P ))

 + #Ω0 + #Ω1 ≤

2(6
√
q − 2) + #Ω0 + #Ω1 = 12

√
q − 4 + #Ω0 + #Ω1 .

This leads to

∣∣∣∣∣∣
∑
r∈Fq

ξ(φd(r))

∣∣∣∣∣∣ ≤ 12
√
q − 4 + #Ω0 + #Ω1 + #Ω. But from the definition of

the set R, Ω has at most 1 + 6 = 7 elements. Hence using the facts that Ωi = {P ∈ Ci :
fi(P ) ∈ Ω} and fi is of degree 2 (since any point in A1(Fq) \Ω has exactly two preimages

in Ci), so #Ωi ≤ 2#Ω = 14. Finally, we have

∣∣∣∣∣∣
∑
r∈Fq

ξ(φd(r))

∣∣∣∣∣∣ ≤ 12
√
q + 31.

Corollary 1. Let h1, h2 : {0, 1}∗ → Fq be two hash functions modeled as random oracles.
Then the construction H : m 7→ φd(h1(m)) + φd(h2(m)) is indifferentiable from a random
oracle.

Proof. By the previous theorem, we know that the encoding φd is (12 + 31q−1/2)-well-
distributed. From theorem 1 and theorem 2 in [14], we deduce that is H regular. It is
admissible since it is clearly computable and samplable (see [6], [14]). Hence we conclude
that m 7→ f(h1(m)) + f(h2(m)) is indifferentiable from a random oracle when h1, h2 are
modeled as random oracles.

5. Conclusion

We have proposed new encoding functions for various forms of elliptic curves. Our
encodings are almost injective and easily invertible. This is useful for constructing indif-
ferentiable hash functions following the idea of Farashahi et al.

References

[1] Tatsuaki Okamoto Alfred Menezes and Scott A. Vanstone. Reducing elliptic curve
logarithms to logarithms in a finite field. IEEE Transactions on Information Theory,
39(5):1639–1646, 1993.

[2] Dan Boneh and Matthew K. Franklin. Identity-based encryption from the weil pairing.
In CRYPTO (2001), LNCS, Springer, 2139(3):213–229, 2001.

[3] B. Lynn D. Boneh and H. Shacham. Short signatures from the weil pairing. In
ASIACRYPT, LNCS, Springer, 2248:514–532, 2001.

[4] Anna Krasnova Daniel J. Bernstein, Mike Hamburg and Tanja Lange. Elligator:
Elliptic-curve points indistinguishable from uniform random strings. ACM CCS, 2013.



REFERENCES 391

[5] Chen Qian et al. Diego F. Aranha, Pierre-Alain Fouque. Binary elligator squared.
Available at http://www.researchgate.net/publication/268333288, November 2004.

[6] Jean-Sébastien Coron Thomas Icart et al. Eric Brier. Efficient Indifferentiable Hash-
ing into Ordinary Elliptic Curves. In CRYPTO (2010), LNCS, Springer, 6223:237–
254, 2010.

[7] Reza Rezaeian Farashahi. Efficient indifferentiable hashing into ordinary elliptic
curves. In AFRICACRYPT (2011), LNCS, Springer, 6737:278–289, 2011.

[8] Pierre-Alain Fouque and Mehdi Tibouchi. Estimating the size of the image of deter-
ministic hash functions to elliptic curves. In LATINCRYPT (2010), LNCS, Springer,
6212:81–91, 2010.

[9] Thomas Icart. How to hash into elliptic curves. In CRYPTO (2009), LNCS, Springer,
5677:303–316, 2009.

[10] The Tor Project Inc. Tor. Available at www.torproject.org, September 2015.

[11] Bodo Möller. A public-key encryption scheme with pseudo-random ciphertexts. ES-
ORICS, LNCS, Springer, 3193:335–351, 2004.

[12] A. Joux P.-A. Fouque and M. Tibouchi. Injective encodings to elliptic curves. In
Information Security and Privacy - 18th Australasian Conference, LNCS, Springer,
7959:16, July 2013.

[13] Antoine Joux Pierre-Alain Fouque and Mehdi Tibouchi. Injective encodings to elliptic
curves. In ACISP (2013), LNCS, Springer, 7959:203–218, 2013.

[14] Igor E. Shparlinski et al. Reza R. Farashahi, Pierre-Alain Fouque. Indifferentiable
deterministic hashing to elliptic and hyperelliptic curves. Mathematics of Computa-
tion, 82(281):491–512, January 2013.

[15] Andrew Shallue and Christiaan Van de Woestijne. Construction of rational points
on elliptic curves over finite fields. In ANTS (2006), LNCS, Springer, 4076:510–524,
2006.

[16] Mariusz Skalba. Points on elliptic curves over finite fields. Acta Arith., 117:293–301,
2005.

[17] Mehdi Tibouchi. Elligator squared: Uniform points on elliptic curves of prime order
as uniform random strings. To appear in Financial Cryptography, LNCS, Springer,
2014.

[18] Philip D. MacKenzie Victor Boyko and Sarvar Patel. Provably secure password-
authenticated key exchange using diffie-hellman. In EUROCRYPT (2000), LNCS,
Springer, 1807:156171, 2001.