Paper 2014/486
Binary Elligator Squared
Diego F. Aranha, PierreAlain Fouque, Chen Qian, Mehdi Tibouchi, and JeanChristophe Zapalowicz
Abstract
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 curvebased 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 Shalluevan de Woestijne characteristic 2 encoding, which we show can be computed using only multiplications, trace and halftrace 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 overheadmuch 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 3540% faster with Elligator for protocols using a fixed base point (such as static ECDH), but 3035% 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.
Metadata
 Available format(s)
 Category
 Implementation
 Publication info
 Preprint. MINOR revision.
 Keywords
 ElligatorBinary Elliptic CurvesEfficient ImplementationPCLMULQDQAnonymity & Privacy
 Contact author(s)
 mehdi tibouchi @ normalesup org
 History
 20140623: received
 Short URL
 https://ia.cr/2014/486
 License

CC BY
BibTeX
@misc{cryptoeprint:2014/486, author = {Diego F. Aranha and PierreAlain Fouque and Chen Qian and Mehdi Tibouchi and JeanChristophe Zapalowicz}, title = {Binary Elligator Squared}, howpublished = {Cryptology ePrint Archive, Paper 2014/486}, year = {2014}, note = {\url{https://eprint.iacr.org/2014/486}}, url = {https://eprint.iacr.org/2014/486} }