International Association
for Cryptologic Research

Applications of elliptic curve cryptography to anonymity, privacy and

censorship circumvention call for methods to represent uniformly random

points on elliptic curves as uniformly random bit strings, so that, for

example, ECC network traffic can masquerade as random traffic.

At ACM CCS 2013, Bernstein et al. proposed an efficient approach,

called ``Elligator,\'\' to solving this problem for arbitrary elliptic

curve-based cryptographic protocols, based on the use of efficiently

invertible maps to elliptic curves. Unfortunately, such invertible maps

are only known to exist for certain classes of curves, excluding in

particular curves of prime order and curves over binary fields. A variant

of this approach, ``Elligator Squared,\'\' was later proposed by Tibouchi

(FC 2014) supporting not necessarily injective encodings to elliptic

curves (and hence a much larger class of curves), but, although some

rough efficiency estimates were provided, it was not clear how an actual

implementation of that approach would perform in practice.

In this paper, we show that Elligator Squared can indeed be implemented

very efficiently with a suitable choice of curve encodings. More

precisely, we consider the binary curve setting (which was not discussed

in Tibouchi\'s paper), and implement the Elligator Squared bit string

representation algorithm based on a suitably optimized version of the

Shallue--van de Woestijne characteristic 2 encoding, which we show can

be computed using only multiplications, trace and half-trace

computations, and a few inversions.

On the fast binary curve of Oliveira et al. (CHES 2013), our

implementation runs in an average of only 22850 Haswell cycles, making

uniform bit string representations possible for a very reasonable

overhead---much smaller even than Elligator on Edwards curves.

As a side contribution, we also compare implementations of Elligator and

Elligator Squared on a curve supported by Elligator, namely

Curve25519. We find that generating a random point and its uniform

bitstring representation is around 35-40% faster with Elligator for

protocols using a fixed base point (such as static ECDH), but 30-35%

faster with Elligator Squared in the case of a variable base point

(such as ElGamal encryption). Both are significantly slower

than our binary curve implementation.