Cryptology ePrint Archive: Report 2013/325
Elligator: Elliptic-curve points indistinguishable from uniform random strings
Daniel J. Bernstein and Mike Hamburg and Anna Krasnova and Tanja Lange
Abstract: 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.
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.
Category / Keywords: Censorship circumvention; elliptic curves; injective maps; indistinguishable public keys
Original Publication (in the same form): ACM-CCS 2013
Date: received 27 May 2013, last revised 29 Aug 2013
Contact author: tanja at hyperelliptic org
Available format(s): PDF | BibTeX Citation
Note: Are paying for open access, so uploading this version is fine.
Version: 20130829:075905 (All versions of this report)
Short URL: ia.cr/2013/325
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]