Elligator : elliptic-curve points indistinguishable from uniform random strings

D.J. Bernstein, M. Hamburg, A. Krasnova, T. Lange

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

57 Citations (Scopus)

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. 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.
Original languageEnglish
Title of host publication2013 ACM SIGSAC Conference on Computer and Communications Security (CCS'13, Berlin, Germany, November 4-8, 2013)
EditorsA.-R. Sadeghi, V.D. Gligor, M. Yung
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
Pages967-979
ISBN (Print)978-1-4503-2477-9
DOIs
Publication statusPublished - 2013
Eventconference; 20th ACM SIGSAC Conference on Computer and Communications Security; 2013-11-04; 2013-11-08 -
Duration: 4 Nov 20138 Nov 2013

Conference

Conferenceconference; 20th ACM SIGSAC Conference on Computer and Communications Security; 2013-11-04; 2013-11-08
Period4/11/138/11/13
Other20th ACM SIGSAC Conference on Computer and Communications Security

Fingerprint Dive into the research topics of 'Elligator : elliptic-curve points indistinguishable from uniform random strings'. Together they form a unique fingerprint.

Cite this