Paper 2014/043
Elligator Squared: Uniform Points on Elliptic Curves of Prime Order as Uniform Random Strings
Mehdi Tibouchi
Abstract
When represented as a bit string in a standard way, even using point compression, an elliptic curve point is easily distinguished from 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 with such 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 nontrivial $2$torsion, so that Elligator cannot be used with primeorder curves, ruling out standard ECC parameters and 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 be taken from a prime order subgroup, which, in conjunction with the nontrivial $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 an elliptic curve point P as the bit string \iota^{1}(P), where \iota is an injective encoding to the curve (which is only known to exist for some curve families, and reaches only half of all possible points), we propose to use a randomly sampled preimage of P under an admissible encoding of the form f^{\otimes 2}: (u,v)\mapsto 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^{\otimes 2} are essentially surjective, inducing a close to uniform 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, and can be computed quite efficiently when the function f is suitably chosen.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. Minor revision. FC 2014
 Keywords
 Elliptic curve cryptographyPoint encodingCircumvention technologyAnonymity and privacy
 Contact author(s)
 mehdi tibouchi @ normalesup org
 History
 20140130: revised
 20140117: received
 See all versions
 Short URL
 https://ia.cr/2014/043
 License

CC BY
BibTeX
@misc{cryptoeprint:2014/043, author = {Mehdi Tibouchi}, title = {Elligator Squared: Uniform Points on Elliptic Curves of Prime Order as Uniform Random Strings}, howpublished = {Cryptology ePrint Archive, Paper 2014/043}, year = {2014}, note = {\url{https://eprint.iacr.org/2014/043}}, url = {https://eprint.iacr.org/2014/043} }