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.