Paper 2013/325

Elligator: Elliptic-curve points indistinguishable from uniform random strings

Daniel J. Bernstein, Mike Hamburg, Anna Krasnova, and Tanja Lange


Censorship-circumvention tools are in an arms race against censors. The censors study all traffic passing into and out of their controlled sphere, and try to disable censorship-circumvention tools without completely shutting down the Internet. Tools aim to shape their traffic patterns to match unblocked programs, so that simple traffic profiling cannot identify the tools within a reasonable number of traces; the censors respond by deploying firewalls with increasingly sophisticated deep-packet inspection. Cryptography hides patterns in user data but does not evade censorship if the censor can recognize patterns in the cryptography itself. In particular, elliptic-curve cryptography often transmits points on known elliptic curves, and those points are easily distinguishable from uniform random strings of bits. This paper introduces high-security high-speed elliptic-curve systems in which elliptic-curve points are encoded so as to be indistinguishable from uniform random strings. At a lower level, this paper introduces a new bijection between strings and about half of all curve points; this bijection is applicable to every odd-characteristic elliptic curve with a point of order 2, except for curves of j-invariant 1728. This paper also presents guidelines to construct, and two examples of, secure curves suitable for these encodings.

Note: Are paying for open access, so uploading this version is fine.

Available format(s)
Publication info
Published elsewhere. ACM-CCS 2013
Censorship circumventionelliptic curvesinjective mapsindistinguishable public keys
Contact author(s)
tanja @ hyperelliptic org
2013-08-29: revised
2013-06-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Daniel J.  Bernstein and Mike Hamburg and Anna Krasnova and Tanja Lange},
      title = {Elligator: Elliptic-curve points indistinguishable from uniform random strings},
      howpublished = {Cryptology ePrint Archive, Paper 2013/325},
      year = {2013},
      doi = {10.1145/2508859.2516734},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.