Elligator Squared
Uniform Points on Elliptic Curves of Prime Orderas Uniform Random Strings
Mehdi Tibouchi
NTT Secure Platform Laboratories
tibouchi.mehdi@lab.ntt.co.jp
Abstract. When represented as a bit string in a standard way, evenusing point compression, an elliptic curve point is easily distinguishedfrom a random bit string. This property potentially allows an adversary
to tell apart network traffic that makes use of elliptic curve cryptography
from random traffic, and then intercept, block or otherwise tamper withsuch traffic.
Recently, Bernstein, Hamburg, Krasnova and Lange proposed a partial
solution to this problem in the form of Elligator: an algorithm for representing around half of the points on a large class of elliptic curves as close
to uniform random strings. Their proposal has the advantage of being
very efficient, but suffers from several limitations:– Since only a subset of all elliptic curve points can be encoded as a string,
their approach only applies to cryptographic protocols transmitting
points that are rerandomizable in some sense.
– Supported curves all have non-trivial 2-torsion, so that Elligator cannot
be used with prime-order curves, ruling out standard ECC parametersand many other cryptographically interesting curves such as BN curves.
– For indistinguishability to hold, transmitted points have to be uniform
in the whole set of representable points; in particular, they cannot betaken from a prime order subgroup, which, in conjunction with the
non-trivial 2-torsion, rules out protocols that require groups of prime
order.
In this paper, we propose an approach to overcome all of these limitations.
The general idea is as follows: whereas Bernstein et al. represent anelliptic curve point P as the bit string ι−1 (P ), where ι is an injective
encoding to the curve (which is only known to exist for some curvefamilies, and reaches only half of all possible points), we propose to use arandomly sampled preimage of P under an admissible encoding of the formf ⊗2 : (u, v) 7→ f (u) + f (v), where f is essentially any algebraic encoding.
Such encodings f exist for all elliptic curves, and the corresponding
admissible encodings f ⊗2 are essentially surjective, inducing a close touniform distribution on the curve.
As a result, our bit string representation is somewhat less compact (about
twice as long as Elligator), but it has none of the limitations above, andcan be computed quite efficiently when the function f is suitably chosen.
Keywords: Elliptic curve cryptography, Point encoding, Circumvention
technology, Anonymity and privacy

1Introduction

Elliptic curves, whose use in public-key cryptography was first suggested by
Koblitz and Miller in the mid-1980s [18,20], offer numerous advantages over more
traditional settings like RSA and finite field discrete logarithms, particularly
higher efficiency and a much smaller key size that scales gracefully with security
requirements. Moreover, they possess a rich geometric structure that enables theconstruction of additional primitives such as bilinear pairings, which have opened
up avenues for novel cryptographic protocols over the past decade, starting with
Joux’s tripartite key agreement [17] and Boneh and Franklin’s construction of an
identity-based encryption scheme [5].
On the Internet, adoption of elliptic curve cryptography is growing in generalpurpose protocols like TLS, SSH and S/MIME, as well as anonymity and privacyenhancing tools like Tor (which favors ECDH key exchange in recent versions)and Bitcoin (which is based on ECDSA).
For circumvention applications, however, ECC presents a weakness: points
on a given elliptic curve, when represented in a usual way (even in compressedform) are easy to distinguish from random bit strings. For example, the usualcompressed bit string representation of an elliptic curve point is essentially the
x-coordinate of the point, and only about half of all possible x-coordinatescorrespond to valid points (the other half being x-coordinates of points of thequadratic twist). This makes it relatively easy for an attacker to distinguish ECC
traffic (the transcripts of multiple ECDH key exchanges, say) from random traffic,
and then proceed to intercept, block or otherwise tamper with such traffic.
Note that while RSA presents a similar weakness, it is both less severe andeasier to mitigate. Namely, an RSA ciphertext or signature with respect to a
public modulus N is usually represented as a bit string of length n = dlog2 N ecorresponding to an integer between 1 and N − 1. This can be distinguished froma random bit string with advantage ≈ (1 − N/2n ), which is usually less than
1/2, and possibly much less for an appropriate choice of N . Moreover, even when
N isn’t close to 2n , it is possible to thwart the distinguishing attack by using
redundant representations, i.e. transmitting representatives of the classes modulo
N chosen in [0, 2n+t ) (see §3.4).
Countering the distinguishers for elliptic curve points is more difficult. One
possible approach is to modify protocols so that transmitted points randomly
lie either on the given elliptic curve or on its quadratic twist (and the curveparameters must therefore be chosen to be twist-secure). This is the approachtaken by Möller [21], who constructed a CCA-secure KEM and a corresponding
hybrid public-key encryption scheme based on elliptic curves, using a binary (toavoid modulus based distinguishers like in RSA) elliptic curve and its twist. Similarly, Young and Yung constructed secure key exchange [26] and encryption [27]without random oracles based on the hardness of DDH in an elliptic curve andits twist.
Möller’s approach has already been deployed in circumvention tools, including
StegoTorus [24], a camouflage proxy for Tor, and Telex [25], an anticensorship
technology that uses a covert channel in TLS handshakes to securely communicate

with friendly proxy servers. However, since protocols and security proofs have tobe adapted to work on both a curve and its twist, this approach is not particularly
versatile, and it imposes additional security requirements (twist-security) on the
choice of curve parameters.
Elligator. A different approach was recently proposed by Bernstein, Hamburg, Krasnova and Lange [4]. Their idea is to leverage an efficiently computable, efficiently invertible algebraic function that maps the integer interval
S = {0, . . . , (p − 1)/2}, p prime, injectively to the group E(Fp ) where E is anelliptic curve over Fp (subject to some conditions on the choice of p and E).
Bernstein et al. observe that, since ι is injective, a uniformly random point P
in ι(S) ⊂ E(Fp ) has a uniformly random preimage ι−1 (P ) in S, and use thatobservation to represent an elliptic curve point P as the bit string representationof the unique integer ι−1 (P ) if it exists. If the prime p is close to a power of 2, a
uniform point in ι(S) will have a close to uniform bit string representation.
This method, which they call Elligator, has numerous advantages over Möller’s
twisted curve method: it is easier to adapt to existing protocols using elliptic
curves, since there is no need to modify them to also deal with the quadratic
twist; it avoids the need to publish a twisted curve counterpart of each public
key element, hence allowing a more compact public key; and it doesn’t impose
additional security requirements like twist-security. But it also has some significant
limitations:– The set ι(S) of elliptic curve points that can be represented as bit strings using
Elligator is of cardinality ≈ p/2, and hence contains only about half of all points
on the curve. As a result, the approach only applies to cryptographic protocols
transmitting points that are rerandomizable in some sense. For example,
Elligator cannot be used in conjunction with a deterministic signature scheme
like BLS [6] (short of using e.g. additional padding).
– Not all elliptic curves are known to admit an injective encoding ι as used in
the construction of Elligator, and all of those curves have order divisible by asmall prime. Bernstein et al. use the injective encoding proposed by Fouque,
Joux and Tibouchi [13], which only exists for curves of order divisible by 4 overfields with p ≡ 3 (mod 4), and another new injective encoding which exists
for curves of even order. The only other known injective encoding to ordinary
curves is due to Farashahi [10] and applies to curves of order divisible by 3.
The Elligator construction cannot be used with any other elliptic curve, and inparticular does not apply to prime-order curves, which make up essentially all
standardized ECC parameters (including NIST [12], SEC 2 [9], Brainpool [19]and ANSSI [1] curves), or to many other cryptographically interesting curves
such as Barreto–Naehrig curves [2].
– For indistinguishability to hold, transmitted points have to be uniform in
ι(S); in particular, they cannot be taken from a strict subgroup, which rules
out protocols that require groups of prime order, since none of the supported
curves has prime order. In particular, many protocols with standard model
security cannot be used with Elligator. For example, Bernstein et al. describe

a hybrid encryption scheme constructed from a slightly modified version of the
ElGamal key encapsulation mechanism in the whole group of points of theirelliptic curve [4, §2.3]. The overall hybrid scheme is secure if the key derivation
function is modeled as a random oracle, but the existence of small divisorsof the group order breaks the semantic security of the underlying standard
model KEM, even though the usual ElGamal KEM is IND-CPA secure in thestandard model.
Our contributions. In this paper, we propose a new approach to overcome
all of these limitations. The general idea is as follows: whereas Bernstein et al.
represent an elliptic curve point P as the bit string ι−1 (P ), where ι is an injective
encoding to the curve (which is only known to exist for some curve families, andreaches only half of all possible points, we propose to use a randomly sampled
preimage of P under an admissible encoding of the form:f ⊗2 : (u, v) 7→ f (u) + f (v),where f is essentially any algebraic encoding. Such encodings f exist for all
elliptic curves, and the corresponding admissible encodings f ⊗2 are essentiallysurjective, inducing a close to uniform distribution on the curve.
As a result, using our approach, all elliptic curve points are representable,
and the bit string representation of a random point on the whole elliptic curve(rather than just a special subset of it) is statistically indistinguishable from arandom bit string. This eliminates the need for repeatedly restarting the protocol
until a representable point is found, and for rerandomizability in general (forexample, full domain hash-like deterministic signatures such as BLS signatures [6],which we mentioned are not directly usable with Elligator, can be used with ourrepresentation algorithm without problem).
In addition, since the kind of encoding functions f we use exist for essentiallyall elliptic curves, including curves of prime as well as composite order, pairingfriendly curves and so on, our method lifts all the limitations that Elligator sets
on curve parameters. In particular, protocols requiring curves of prime order canbe used in our setting.
We also recommend specific choices of the function f that are well-suited tovarious elliptic curve parameters, and propose optimizations of the corresponding
algorithms for representing points as bit strings and back. We find that in mostsetting, our approach is in fact more efficient than Elligator for representing
generated points as bit strings. It is, however, less compact, since a curve pointis represented as two base field elements instead of one.
Organization of the paper. In §2, we introduce notation, definitions anduseful results related to discrete probability distributions, regularity and socalled well-distributed encodings to elliptic curves. In §3, we introduce our main
construction, and state and establish the theorem on which it is based. Finally,in §4, we present concrete choices of functions f which are well-suited to ourapproach, working for large families of curves, and also offer a performancecomparison to Elligator.

2

Preliminaries

2.1

Statistical distance and regularity

For D a probability distribution on a finite set S, we write Pr[s ← D] for the
probability assigned to the singleton {s} ⊂ S by D. The uniform distribution on
S is denoted by US (or just U if the context is clear).
Definition 1 (Statistical distance). Let D and D 0 be two probability distributions on a finite set S. The statistical distance between them is defined as the`1 norm:1X∆1 (D, D 0 ) =Pr[s ← D] − Pr[s ← D 0 ] .
s∈SWe simply denote by ∆1 (D) the statistical distance between D and US :∆1 (D) =Xs∈S

Pr[s ← D] −

1
,
|S|

and say that D is ε-statistically close to uniform when ∆1 (D) ≤ ε. When ∆1 (D)is negligible, we simply say than D is statistically close to uniform.2
The squared Euclidean imbalance ∆22 (D) of D is the square of the `2 norm
between D and US :∆22 (D) =X

2

Pr[s ← D] − 1/|S| .

s∈SDefinition 2 (Pushforward and pullback). Let S, T be two finite sets andF any mapping from S to T . For any probability distribution DS on S, we candefine the pushforward F∗ DS of DS by F as the probability distribution on Tsuch that sampling from F∗ DS is equivalent to sampling a value s ← DS andreturning F (s). In other words:
X





Pr t ← F∗ DS = Pr s ← DS ; t = F (s) = µS F −1 (t) =Pr[s ← DS ],s∈F −1 (t)where µS is the probability measure defined by DS . Similarly, for any probability
distribution DT on T that assigns a nonzero weight µT F (S) to the image ofF , we can define the pullback F ∗ DT of DT by F as the probability distribution
on S such that sampling from F ∗ DT is equivalent to sampling a value t ← DT ,1

An alternate definition frequently found in the literature differs from this one by aconstant factor 1/2. That constant factor is irrelevant for our purposes.
2
For this to be well-defined, we of course need a family of random variables on
increasingly large sets S. Usual abuses of language apply.

returning a uniformly random preimage s ∈ F −1 (t) if one exists, and restarting
otherwise. In other words:Pr s ← F ∗ DT =Pr[t ← DT ]1
·#F −1 (t)µT F (S)wheret = F (s).

Definition 3 (Regularity). Let S, T be two finite sets and F any mappingfrom S to T . We say that F is ε-regular (resp. ε-antiregular) when F∗ US (resp.
F ∗ UT ) is ε-close to the uniform distribution. We may omit ε if it is negligible.
Lemma 1. Let S, T be two finite sets and F an ε-regular mapping from S to
T . Then F satisfies:#F (S)1−≤ ε,#Tand is also a 2ε-antiregular mapping.
Proof. This result is similar to [7, Lemma 3]. Since F is ε-regular, we have:∆1 (F∗ US ) =X

Pr[t ← F∗ US ] −X #F −1 (t)
1
1
=
−
≤ ε.
#T
#S
#T
t∈T

t∈T

On the other hand, that sum is larger than the same sum restricted to T \ F (S),which is:
X
t∈F
/ (S)


#F −1 (t)1
1
#F (S)−= # T \ F (S) · 0 −
=1−
.
#S
#T
#T
#T

Hence the first assertion that 1−#F (S)/#T ≤ ε. Turning to the second assertion,
we compute ∆1 (F ∗ UT ):∆1 (F ∗ UT ) =X

Pr[s ← F ∗ UT ] −

s∈S

=

X
s∈S

1
#S

#T
P r[F (s) ← UT ]
1
 −
·
−1
#F (S)
#S
#F
F (s)

1
1
−
−1
#S
#F (S) · #F
F (s)
s∈S
X
1
1
=
#F −1 (t) ·−#F (S) · #F −1 (t) #S=X

t∈F (S)≤Xt∈F (S)≤ 1−
as required.

1#F −1 (t)1
1−+−
#F (S) #T#T#S#F (S)+ ∆1 (F∗ US ) ≤ 2ε
#T
t
u

2.2

Well-distributed encodings

Let E be an elliptic curve over a finite field Fq , and f : Fq → E(Fq ) any function.
Farashahi et al., in [11], show that regularity properties of the tensor square f ⊗2
defined by:f ⊗2 : F2q → E(Fq )(u, v) 7→ f (u) + f (v)can be derived formally from the behavior of f with respect to characters of
the group E(Fq ). More precisely, they call the function f a well-distributed
encoding
P when it satisfies good bounds with respect to character sums of theform u∈Fq χ(f (u)), for nontrivial characters χ of E(Fq ).
Definition 4. A function f : Fq → E(Fq ) is said to be a B-well-distributed
encoding for a certain constant B > 0 if for any nontrivial character χ of E(Fq ),the following holds:X√
χ(f (u)) ≤ B q.
u∈FqFarashahi et al. then show that if f is a well-distributed encoding, then f ⊗2
is regular. They also provide a bound on the Euclidean imbalance of (f ⊗2 )∗ U .
Lemma 2 ([11, Theorem 3 & Corollary 4]). Let f : Fq → E(Fq ) be a Bwell-distributed encoding, and D = (f ⊗2 )∗ UF2q the distribution on E(Fq ) induced
by f ⊗2 . Then, we have:∆1 (D) ≤B2
qq#E(Fq )

and∆22 (D) ≤B4.
q2

Note that since #E(Fq ) = q + O(q 1/2 ) by the Hasse–Weil bound, this implies∆1 (D) = O(q −1/2 ), so the distribution induced by f ⊗2 on E(Fq ) is indeed
statistically close to uniform.
We also mention a special case of the general geometric result that Farashahi etal. use to show that concrete maps are well-distributed encodings.
Lemma 3 ([11, Theorem 7]). Let h : C → E a morphism over Fq from acurve C of genus g to the elliptic curve E. Assume that h does not factor througha nontrivial unramified morphism Z → E. Then, for all nontrivial characters χof E(Fq ), we have:X√χ h(P ) ≤ (2g − 2) q.
P ∈Fq

3

Our construction

3.1

Elligator Squared

As explained in the introduction, our new approach to representing Fq -points
on an elliptic curve E as bit strings is to fix a suitable point encoding function
f : Fq → E(Fq ), and to use the tensor square function:f ⊗2 : F2q → E(Fq )(u, v) 7→ f (u) + f (v).
A point P ∈ E(Fq ) is then represented as (a bit string representation of) a
uniformly random preimage (u, v) ∈ (f ⊗2 )−1 (P ) ⊂ F2q , and a pair (u, v) isconverted back to a point by applying f ⊗2 .
Leaving aside the question of how elements of F2q are represented as bit string
for now (we discuss it in §3.4), we now describe the type of function f we willconsider, formally define our construction, and state the corresponding main
results. In what follows, we fix a finite field Fq and an elliptic curve E over
Fq . When stating asymptotic results, we implicitly assume as usual that q, E,
and functions depending on them fit in infinite families indexed by a security
parameter λ.
Definition 5. We call a function f : Fq → E(Fq ) a (d, B)-well-bounded encoding, for positive constants d, B, when f is B-well-distributed and all points inE(Fq ) have at most d preimages under f . We may occasionally omit the constant
B or both d and B as appropriate.
Our main result pertaining to well-bounded encodings says that, on the one
hand, if we sample a uniformly random preimage under f ⊗2 of a uniformly
random point P on the curve, we get a pair (u, v) ∈ F2q which is statistically close
to uniform; and on the other hand, that sampling uniformly random preimages
under f ⊗2 can be done efficiently for all points P ∈ E(Fq ) except possibly anegligible fraction of them.
Theorem 1. Let f : Fq → E(Fq ) be a (d, B)-well-bounded encoding. Then, thedistribution on F2q obtained by picking a uniformly random point P in E(Fq ), andthen a uniformly random preimage (u, v) ∈ F2q of P under f ⊗2 if one exists ispε-statistically close to uniform for ε = 2B 2 #E(Fq )/q = O(q −1/2 ). Moreover,there exists a probabilistic algorithm which, on input of any point P ∈ E(Fq ),returns a uniformly random preimage of P under f ⊗2 if it exists, and whose
average running time T (P ) on input P satisfies:T (P ) ≤ Tf −1 + 1 + εT (P ) · d · (Tf + T + T#f −1 )where Tf , T , T#f −1 and Tf −1 are the respective running times of the algorithms
computing f , a subtraction in E(Fq ), the number of preimages of a point underf , and all the preimages of a point under f , and the coefficient εT (P ) is bounded,
for all P except possibly a fraction of ≤ q −1/2 of them, as:
εT (P ) ≤2B 2 + 2= O(q −1/4 ).
q 1/4 − 2B 2

(1)

In other words, for all P ∈ E(Fq ) except possibly a negligible fraction of them,
the time it takes to sample a uniformly random preimage of P under f ⊗2 is one
evaluation of f −1 and about d evaluations of f , of point subtractions on E(Fq )and of the function that counts preimages under f .
Proof. The first assertion says that f ⊗2 is ε-antiregular, which is a direct consequence of Lemma 1 and Lemma 2. We describe the preimage sampling algorithmin §3.3 below. The assertion on the running time is an immediate consequence ofLemmas 4 and 5 from that subsection.
Definition 6. For a given well-bounded encoding f : Fq → E(Fq ), the Elligator
Squared construction for f is the pair formed by a randomized algorithm E(Fq ) →F2q as in Theorem 1, called the Elligator Squared representation algorithm, whichsamples uniform preimages under f ⊗2 , and the deterministic algorithm, called
the Elligator Squared recombination algorithm, which computes the functionf ⊗2 .
3.2

Example: ECDH using Elligator Squared

As an example of how this construction can be used in practice, we describe
a standard elliptic curve Diffie–Hellman key exchange protected with Elligator
Squared. Let P be a generator of E(Fq ) (which we assume is a cyclic group oforder N ), f : Fq → E(Fq ) a well-bounded encoding, and KDF : E(Fq ) → {0, 1}λa key derivation function. To derive a common secret, Alice and Bob proceed asfollows.
1. Alice and Bob generate short term secrets (the values computed by Alice,
resp. Bob, are indicated with indices A, resp. B, below):$(a) Pick a uniformly random r ← {0, . . . , N − 1}.
(b) Compute the point R = rP .
$(c) Sample a random preimage (u, v) ← (f ⊗2 )−1 (R) under f ⊗2 using the
Elligator Squared representation algorithm.
2. Alice sends (uA , vA ) to Bob; Bob sends (uB , vB ) to Alice.
3. Alice uses the Elligator Squared recombination algorithm to compute RB =f ⊗2 (uB , vB ). Similarly, Bob computes RA = f ⊗2 (uA , vA ).
4. Alice computes the shared secret as kAB = KDF(rA RB ), and similarly, Bob
computes it as kAB = KDF(rB RA ).
The transmitted values (uA , vA ) and (uB , vB ) are elements of F2q that are
statistically close to uniform, as shown by Theorem 1, so a transcript of thisprotocol cannot be distinguished from random messages.3
3With the caveat that an actual implementation transmits bit strings rather than field
elements, but this is addressed in §3.4.

Moreover, in contrast with the same protocol implemented with Bernstein etal.’s Elligator [4, §2.3], our approach doesn’t require any kind of rejection sampling
during the computation of the pairs (u, v), and therefore only one elliptic curve
scalar multiplication is needed to generate the short term secrets, compared to an
average of two, and possibly more, with Elligator. Indeed, Theorem 1 ensures thatwith overwhelming probability on the choice of r, the representation algorithm
samples a random preimage of R = rP efficiently.

3.3

The sampling algorithm

Let f : Fq → E(Fq ) be a (d, B)-well-bounded encoding. We now turn to the sampling algorithm for preimages of f ⊗2 whose existence was asserted as Theorem 1.
It is described as Algorithm 1. This algorithm generalizes the sampling algorithm
proposed, but not thoroughly analyzed, by Brier et al. [7, Algorithm 1] for thetensor square of Icart’s encoding [16].

Algorithm 1 Preimage sampling algorithm for f ⊗2 .
1: function SamplePreimage(P )2:repeat$3:u ← Fq4:
Q ← P − f (u)5:t ← #f −1 (Q)$6:j ← {1, . . . , d}7:
until j ≤ t
8:{v1 , . . . , vt } ← f −1 (Q)9:return (u, vj )10: end function

Lemma 4. On all inputs P ∈ E(Fq ) in the image of f ⊗2 , Algorithm 1 terminates
almost surely, and returns a uniformly random preimage of P under f ⊗2 , afteran average of N (P ) iterations of the main loop (Steps 2–7), where:
N (P ) = d ·q#(f ⊗2 )−1 (P ).

On inputs P that have no preimage under f ⊗2 , Algorithm 1 does not terminate.
Proof. The probability to exit the main loop after Step 7 for a given random
choice of u ∈ Fq is t/d, where t = #f −1 P − f (u) (note that since f is d-wellbounded, we know that t is always less or equal to d). As a result, taking all
possible choices of u into account, the overall probability $(P ) to exit the mainloop for a given input P is:$(P ) =

1 X X
1 X #f −1 P − f (u)f (v) = P − f (u)
=
q
d
d·q
u∈Fq

=

1
d·q

u∈Fq v∈Fq

X

 ⊗2

f (u, v) = P =(u,v)∈F2q

1#(f ⊗2 )−1 (P ),d·qwhere [·] is the usual Iverson bracket notation: for a statement U , [U ] = 1 if U istrue and 0 otherwise. As a result, we see that Algorithm 1 does not terminate
when #(f ⊗2 )−1 (P ) = 0, and terminates almost surely otherwise, after an averageof N (P ) = 1/$(P ) = d · q/#(f ⊗2 )−1 (P ) iterations of the main loop as required.
Moreover, all outputs are clearly preimages of P under f ⊗2 , so all it remains toprove is that each preimage is output with equal probability.
Fix a preimage (u0 , v0 ) of P in F2q . The probability that Algorithm 1 outputs(u0 , v0 ) on input P conditionally to the first coordinate being u0 is clearly
1/t0 where t0 = #f −1 P − f (u0 ) . Furthermore, the rejection sampling in themain loop ensures that any given first coordinate u is chosen with probability
proportional to t = #f −1 P − f (u) . As a result, we obtain, using the previous
computation, that the probability of Algorithm 1 returning (u0 , v0 ) on input P
is exactly:
1
1
1
t0
=
=
·P
⊗2
−1
t0
d · q · $(P )#(f )−1 (P )P − f (u)u∈Fq #ftu

as required.

Lemma 5. With the same notation as in Lemma 4, write, for all P ∈ E(Fq ),εT (P ) = N (P )/d − 1 = q/#(f ⊗2 )−1 (P ) − 1. Then, for all P ∈ E(Fq ) except
possibly a fraction of ≤ q −1/2 of them, we have:
εT (P ) ≤2B 2 + 2= O(q −1/4 ).
q 1/4 − 2B 2(This is the same bound as (1) above).
p
Proof. Define δ = B 2 q 5/4 / #E(Fq ) (in particular, δ ∼ B 2 q 3/4 ), and let α bethe fraction of all points in E(Fq ) such that:#(f ⊗2 )−1 (P ) −q2> δ.
#E(Fq )

Now, according to Lemma 2, we have:∆22 (f ⊗2 )∗ UF2q =X
P ∈E(Fq )2
1
B4#(f ⊗2 )−1 (P )−≤.
q2
#E(Fq )q2

On the other hand, by definition of α:1∆22 (f ⊗2 )∗ UF2q = 4
qX#(f ⊗2 )−1 (P ) −P ∈E(Fq )2
q2
1≥ 4 · α#E(Fq ) · δ 2 .
#E(Fq )
qPutting both inequalities together, we get:α≤

B 4 q2= q −1/2 .
#E(Fq ) · δ 2Hence, for all P ∈ E(Fq ) except a fraction α ≤ q −1/2 , the number #(f ⊗2 )−1 (P )of preimages of P under f ⊗2 is within δ of q 2 /#E(Fq ). For all such P , we get:
εT (P ) =q
−1≤⊗2#(f )−1 (P )q
q2

#E(Fq ) − δ−1=(q + δ)#E(Fq ) − q 2.
q 2 − δ#E(Fq )√√The Hasse–Weil bound gives #E(Fq ) ≤ q + 2 q + 1 = ( q + 1)2 , and hence
δ#E(Fq ) = B 2 q 5/4 #E(Fq ) ≤ 2B 2 q 7/4 . As a result, again for all P except afraction ≤ q −1/2 :q 2 + 2q 3/2 + q + 2B 2 q 7/4 − q 2
q 2 − 2B 2 q 7/4
2B 2 + 2
2B 2 1 + B12 q −1/4 + 2B1 2 q −3/4≤
≤ 1/4 ·q
1 − 2B 2 q −1/4
q 1/4 − 2B 2εT (P ) ≤as required.

tuWith these lemmas, the proof of Theorem 1 is now complete. We also note that
we can deduce the following result of independent interest as an easy corollary.
This result is hinted to in [11], but not formally stated, let alone proven, although
it is quite important if the results of that paper are to be applied to hash function
constructions.
Corollary 1. Let f : Fq → E(Fq ) be a (d, B)-well-bounded encoding such thatboth f and f −1 are computable in polynomial time. Then f ⊗2 is 2q −1/2 -samplable
in the sense of [7, Definition 2], i.e. there exists a randomized algorithm I taking
points P ∈ E(Fq ) as inputs, running in polynomial time on all inputs, and suchthat I (P ) is an element of (f ⊗2 )−1 (P ) ∪ {⊥} whose distribution is 2q −1/2 statistically close to the uniform distribution on (f ⊗2 )−1 (P ). In particular, if h
is a random oracle with values in F2q , (f ⊗2 ) ◦ h is indifferentiable from a random
oracle with values in E(Fq ).
Proof. The only subtle point is that Algorithm 1 samples exactly uniform preimages under (f ⊗2 ), but may run in superpolynomial time, or even fail to terminate,
on a negligibly small fraction of possible inputs. We can convert it to an algorithm that terminates in polynomial time on all inputs but induces a samplingthat is only statistically close to uniform using early termination: for example,

modify Algorithm 1 to return ⊥ if more than log q/ log(d/(1 − d)) iterations of
the main loop are executed. Then, by Lemma 5, we obtain the algorithm returns
a uniform preimage with probability ≥ 1 − q −1/2 and ⊥ otherwise on all inputs
except possibly a fraction ≤ q −1/2 of them, which gives the stated samplability
result. The indifferentiability of the corresponding hash function constructionin then a consequence of [7, Theorem 1], since f is also regular and efficiently
computable.
tu
3.4

Bit-string representation

The Elligator Squared construction represents uniform elliptic curve points as
close to uniform elements (u, v) of F2q , but in practice, one wants to transmit bit
strings rather than field elements. Can we obtain close to uniform bit strings
instead?
Let us say for simplicity’s sake that q = p is a large prime (the prime
power setting can be treated similarly). Then, the simplest way to represent anelement in Fp is as the basic n-bit representation of the corresponding integerin {0, . . . , p − 1}, where n = dlog2 pe. Then, it is easy to see that the statisticaldistance between a uniform element of Fp in that representation and a uniform
bit string of the same length is given by 2 · (1 − p/2n ).
If p is very close to 2n , which is often the case for standardized curve parameters (including most NIST and SEC 2 curves [12,9], as well as Edwards curves
such as Curve25519 and Curve1174 [3,4]) as such special primes offer efficientmodular reduction, then we can simply transmit the basic n-bit representationsof u and v directly, since they are close to uniform bit strings.
In some cases, however (like Brainpool curves [19], most families of pairingfriendly curves, etc.), p is not close to 2n . Then, one possible approach to get close
to uniform bit strings is to use a redundant representation as a bit string of lengthn+t for some suitable t, i.e. represent u ∈ Fp as the basic (n+t)-bit representation
 n+t of a randomly chosen integer of the form u + kp with k ∈ 0, . . . , 2 p −u .
For a uniform u ∈ Fp , the statistical distance to uniform of the corresponding
distribution on (n + t)-bit strings is given by: 2n+t −u 
X
u∈Fp

p

2n+t

+1

−

1
p
≤ n+t ≤ 2−t .
p2Therefore, taking t ≈ n/2 is sufficient. In fact, we can represent the whole pair(u, v) ∈ F2p as a close to uniform bit string of length ≈ 2n + n/2 by first packing
u and v as an integer in {0, . . . , p2 − 1} and then using the same technique.

4

Application to specific curve families

One drawback of the Elligator Squared construction when applied to general
well-bounded encodings f is that the representation algorithm involves thecomputation of f −1 , which usually amounts to finding the roots of a possiblycomplicated polynomial over Fq .
For example, Icart’s encoding [16], defined for an elliptic curve E : y 2 =3
x + ax + b over a field Fq with q ≡ 2 (mod 2) and ab =6 0, is a (4, 14)-wellbounded encoding by [11, Theorem 8], so we can use it with Elligator Squared. In
particular, many curves of prime order are of that form and are thus supported byour construction. But computing the preimages of a point (x, y), or even counting
those preimages, involves solving quartic equation u4 − 6xu2 + 6yu − 3a = 0
over Fq , which would probably be done using a rather costly algorithm such as
Berlekamp or Cantor–Zassenhaus.
However, in many cases, we can choose a well-bounded encoding f such thatf −1 is much easier to compute (it might take a couple of base field exponentiations,say), and counting the number of preimages of a point is even faster. We present
several large classes of curves that admit such a convenient well-bounded encoding
below. The curves considered here will be defined over a field Fq with q ≡ 3(mod 4). In such a field Fq , we denote by χq (·) : Fq → {−1, 0, 1} the nontrivial√
quadratic character (which is the Legendre
symbol when q is prime), and by ·√the standard square root, defined by u = u(q+1)/4 when χq (u) 6= −1.
4.1

Ordinary curves with q ≡ 3 (mod 4)

Let E : y 2 = x3 + ax + b be an elliptic curve over Fq , q ≡ 3 (mod 4), with ab =6 0,
and let g be the polynomial X 3 + aX + b ∈ Fq [X]. Based on earlier constructions
by Shallue and van de Woestijne [22] and Ulas [23], Brier et al. [7] define thesimplified SWU encoding to E(Fq ) as follows (we follow the slightly modified
presentation from [14,11]).
Definition 7. Define rational functions X0 , X1 ∈ Fq (u) as:b
1
and X1 (u) = −u2 X0 (u).
X0 (u) = − 1 + 4au − u2The simplified SWU encoding to E(Fq ) is the following mapping, which is welldefined (where we denote by O the point at infinity on E).
f : Fq → E(Fq )

O


q


X
(u),
g X0 (u)
0
u 7→
q




 X (u), − g X (u)1

1

if u ∈ {−1, 0, 1};
if u ∈/ {−1, 0, 1} and g X0 (u) is a square;otherwise.

It is shown in [11, §5.3] that f is a (52 + O(q −1/2 ))-well-distributed encoding,and that for all u ∈ Fq \ {−1, 0, 1}:
1=0ω
x = X1 (u) ⇐⇒ u4 − ωu2 + ω = 0
x = X0 (u) ⇐⇒ u4 − u2 +where ω = ab x + 1. Since these are equations of degree 4 in u, it follows thatany point P = (x, y) ∈ E(Fq ) has at most 4 preimages under f (which mustcome from X0 if χq (y) ≥ 0 and from X1 otherwise). Therefore, f is a 4-wellbounded encoding. Moreover, the equations are biquadratic: therefore, f −1 canbe computed with at most two square root computations on any input. And
we can often compute the number of preimages under f with only quadratic
character evaluations.
Indeed, to compute the number of preimages of (x, y) under f where, without
loss of generality, χq (y) ≥ 0, we have to count the number N = #f −1 (x, y)of roots of the biquadratic equation u4 − u2 + 1/ω = 0, where ω = ab x + 1.
Let ∆ = 1 − 4/ω be the discriminant of the corresponding quadratic equationv 2 − v + 1/ω = 0. Clearly, if χq (∆) = −1, we have N = 0, and if ∆ = 0, theequation becomes u2 = v = 1/2, hence N = 0 or 2 depending on whether 1/2 isa square in Fq . Finally, suppose χq (∆) = 1. Then, the equation v 2 − v + 1/ω = 0
has two simple roots whose product is 1/ω. Therefore, if χq (1/ω) = −1, exactly
one of those roots is a square, and we get its two square roots as solutions foru, hence N√ = 2. If, however, χq (1/ω) = 1, we compute one of the roots, say
v0 = (1 + ∆)/2, and we get N = 0 or 4 depending on whether χq (v0 ) = ±1.
Thus, as we can see, we can compute N with at most one exponentiation,and no exponentiation at all (only quadratic character evaluations) most of thetime. This makes the Elligator Square construction quite efficient: the representation algorithm has an average total cost of 6.5 field exponentiations, while therecombination algorithm costs 2 field exponentiations (ignoring faster operations
like field arithmetic and quadratic character evaluations).
4.2

Elligator 1 curves

Consider now an Elligator 1 curve E over Fq in the sense of [4, §3]. It is associatedwith a map φ : Fq → E(Fq ) such that each point in E(Fq ) has either 0 or 2
preimages under φ (except one special point, which has a single preimage).
Bernstein et al. show that computing and inverting φ both cost about one
exponentiation in the base field, while counting the number of preimages of agiven point can be done with only a quadratic character evaluation and a few
multiplications.
Moreover, one can prove that φ is well-distributed. This is because φ canbe expressed in terms of a degree 2 covering h : H → E of E by a certain
elliptic curve H of genus 2, P
as described by Fouque et al. in [13]. As a result,character sums of the form u∈Fq χ(φ(u)) can be rewritten up to a constantP
as P ∈H(Fq ) χ(h(P )). Moreover, the covering h : H → E is of prime degree, sodoes not factor nontrivially, and it cannot be unramified since H is not elliptic.
Therefore, Lemma 3 ensures that:X√√χ h(P ) ≤ (2g − 2) q = 2 q
P ∈H(Fq )for all nontrivial characters χ of E(Fq ). Therefore, we get that φ is (2 + O(q −1/2 ))well-distributed, and hence also (2, 2 + O(q −1/2 ))-well-bounded.

This allows us to apply the Square Elligator construction to φ. It is even more
efficient that for the simplified SWU encoding: the representation algorithm has
an average total cost of 2×1+1 = 3 field exponentiations, while the recombination
algorithm costs 2 field exponentiations (ignoring faster operations again).
4.3

BN curves

In [15], Fouque and Tibouchi have analyzed the Shallue–van de Woestijne encoding [22] in the particular case of Barreto–Naehrig curves [2], and found that it
was a (62 + O(q −1/2 ))-well-distributed. Moreover, preimages under this encoding
are of three types, and the analysis in [15] makes it clear that each curve point
can have at most one preimage of type 1, one preimage of type 2 and 2 preimagesof type 3. As a result, the Shallue–van de Woestijne encoding f to any BN curve
is a 4-well-bounded encoding.
Moreover, since the equations satisfied by preimages are quadratic for type 1
and 2 and biquadratic for type 3, f −1 can be computed with at most 4 squareroot computations, and the number of preimages of a given point can again be
estimated with at most one square root computations and none at all most of thetime. Therefore, even for BN curves, the Elligator Square construction is quite
efficient.
4.4

Performance comparison with Elligator

Consider again a protocol such as the ECDH key exchange described in §3.2. The
ephemeral key generation involves a single elliptic curve scalar multiplication, as
well as one evaluation of the Elligator Squared representation algorithm, whichcosts an average of 6.5 base fields exponentiations with a general elliptic curve asin §4.1, or 3 base fields exponentiations with an Elligator 1 curve as in §4.2. In
contrast, the corresponding algorithm implemented using Elligator [4, §2.4] costs
an average of two scalar multiplications, plus one base field exponentiation forcomputing the representation. This is likely to make this phase of the protocol
significantly faster with Elligator Squared compared to Elligator (certainly so atleast when comparing implementations on the same curve). This is on top of theother advantages of Elligator Squared, including much more freedom in terms of
supported curve parameters (prime order curves, BN curves, etc.), support for
non-rerandomizable protocols and encoding of all curve points.
On the other hand, the transmitted data with Elligator Squared is twice aslarge, and the recombination algorithm about twice as slow (although for both
Elligator and Elligator Squared this recombination time is usually dwarfed by asubsequent scalar multiplication on the curve).

References
1. ANSSI. Publication d’un paramétrage de courbe elliptique visant des applications de passeport électronique et de l’administration électroniquefrançaise.
http://www.ssi.gouv.fr/fr/anssi/publications/publicationsscientifiques/autres-publications/publication-d-un-parametrage-decourbe-elliptique-visant-des-applications-de.html, Nov. 2011.
2. P. S. L. M. Barreto and M. Naehrig. Pairing-friendly elliptic curves of prime order.
In B. Preneel and S. E. Tavares, editors, Selected Areas in Cryptography, volume3897 of Lecture Notes in Computer Science, pages 319–331. Springer, 2005.
3. D. J. Bernstein. Curve25519: New Diffie-Hellman speed records. In M. Yung,
Y. Dodis, A. Kiayias, and T. Malkin, editors, Public Key Cryptography, volume3958 of Lecture Notes in Computer Science, pages 207–228. Springer, 2006.
4. D. J. Bernstein, M. Hamburg, A. Krasnova, and T. Lange. Elligator: Elliptic-curve
points indistinguishable from uniform random strings. In V. Gligor and M. Yung,
editors, ACM CCS, 2013.
5. D. Boneh and M. K. Franklin. Identity-based encryption from the Weil pairing. In
J. Kilian, editor, CRYPTO, volume 2139 of Lecture Notes in Computer Science,
pages 213–229. Springer, 2001.
6. D. Boneh, B. Lynn, and H. Shacham. Short signatures from the Weil pairing. J.
Cryptology, 17(4):297–319, 2004.
7. E. Brier, J.-S. Coron, T. Icart, D. Madore, H. Randriam, and M. Tibouchi. Efficientindifferentiable hashing into ordinary elliptic curves. Cryptology ePrint Archive,
Report 2009/340, 2009. http://eprint.iacr.org/. Full version of [8].
8. E. Brier, J.-S. Coron, T. Icart, D. Madore, H. Randriam, and M. Tibouchi. Efficientindifferentiable hashing into ordinary elliptic curves. In T. Rabin, editor, CRYPTO,
volume 6223 of Lecture Notes in Computer Science, pages 237–254. Springer, 2010.
9. Certicom Research. SEC 2: Recommended elliptic curve domain parameters, Version
2.0, Jan. 2010.
10. R. R. Farashahi. Hashing into Hessian curves. In A. Nitaj and D. Pointcheval,
editors, AFRICACRYPT, volume 6737 of Lecture Notes in Computer Science, pages
278–289. Springer, 2011.
11. R. R. Farashahi, P.-A. Fouque, I. Shparlinski, M. Tibouchi, and J. F. Voloch.
Indifferentiable deterministic hashing to elliptic and hyperelliptic curves. Math.
Comp., 82(281), 2013.
12. FIPS PUB 186-3. Digital Signature Standard (DSS). NIST, USA, 2009.
13. P.-A. Fouque, A. Joux, and M. Tibouchi. Injective encodings to elliptic curves.
In C. Boyd and L. Simpson, editors, ACISP, volume 7959 of Lecture Notes in
Computer Science, pages 203–218. Springer, 2013.
14. P.-A. Fouque and M. Tibouchi. Estimating the size of the image of deterministic
hash functions to elliptic curves. In M. Abdalla and P. S. L. M. Barreto, editors,
LATINCRYPT, volume 6212 of Lecture Notes in Computer Science, pages 81–91.
Springer, 2010.
15. P.-A. Fouque and M. Tibouchi. Indifferentiable hashing to barreto-naehrig curves.
In A. Hevia and G. Neven, editors, LATINCRYPT, volume 7533 of Lecture Notes
in Computer Science, pages 1–17. Springer, 2012.
16. T. Icart. How to hash into elliptic curves. In S. Halevi, editor, CRYPTO, volume
5677 of Lecture Notes in Computer Science, pages 303–316. Springer, 2009.
17. A. Joux. A one round protocol for tripartite Diffie-Hellman. In W. Bosma, editor,
ANTS, volume 1838 of Lecture Notes in Computer Science, pages 385–394. Springer,
2000.
18. N. Koblitz. Elliptic curve cryptosystems. Math. Comp., 48:203–209, 1987.
19. M. Lochter and J. Merkle. Elliptic curve cryptography (ECC) Brainpool standard
curves and curve generation. RFC 5639 (Informational), Mar. 2010.

20. V. S. Miller. Use of elliptic curves in cryptography. In H. C. Williams, editor,
CRYPTO, volume 218 of Lecture Notes in Computer Science, pages 417–426.
Springer, 1985.
21. B. Möller. A public-key encryption scheme with pseudo-random ciphertexts. In
P. Samarati, P. Y. A. Ryan, D. Gollmann, and R. Molva, editors, ESORICS, volume3193 of Lecture Notes in Computer Science, pages 335–351. Springer, 2004.
22. A. Shallue and C. van de Woestijne. Construction of rational points on elliptic
curves over finite fields. In F. Hess, S. Pauli, and M. E. Pohst, editors, ANTS,
volume 4076 of Lecture Notes in Computer Science, pages 510–524. Springer, 2006.
23. M. Ulas. Rational points on certain hyperelliptic curves over finite fields. Bull. Pol.
Acad. Sci. Math., 55(2):97–104, 2007.
24. Z. Weinberg, J. Wang, V. Yegneswaran, L. Briesemeister, S. Cheung, F. Wang, and
D. Boneh. StegoTorus: a camouflage proxy for the Tor anonymity system. In T. Yu,
G. Danezis, and V. D. Gligor, editors, ACM CCS, pages 109–120. ACM, 2012.
25. E. Wustrow, S. Wolchok, I. Goldberg, and J. A. Halderman. Telex: Anticensorship in
the network infrastructure. In USENIX Security Symposium. USENIX Association,
2011.
26. A. L. Young and M. Yung. Space-efficient kleptography without random oracles. In
T. Furon, F. Cayre, G. J. Doërr, and P. Bas, editors, Information Hiding, volume4567 of Lecture Notes in Computer Science, pages 112–129. Springer, 2007.
27. A. L. Young and M. Yung. Kleptography from standard assumptions and applications. In J. A. Garay and R. D. Prisco, editors, SCN, volume 6280 of Lecture Notes
in Computer Science, pages 271–290. Springer, 2010.