Elligator: Elliptic-curve points indistinguishable from uniform random strings

[Nytro]

Elligator: Elliptic-curve points

indistinguishable from uniform random strings

Daniel J. Bernstein1;3

1Department of Computer

Science

University of Illinois at Chicago

Chicago, IL 60607–7045

USA

djb@cr.yp.to

Anna Krasnova2

2Privacy & Identity lab

Institute for Computing and

Information Sciences

Radboud University Nijmegen

Heyendaalseweg 135

6525 AJ Nijmegen

The Netherlands

anna@mechanicalmind.

org

Tanja Lange3

3Department of Mathematics

and Computer Science

Technische Universiteit

Eindhoven

P.O. Box 513

5600 MB Eindhoven

The Netherlands

tanja@hyperelliptic.org

ABSTRACT

Censorship-circumvention tools are in an arms race against

censors. The censors study all trac passing into and out

of their controlled sphere, and try to disable censorshipcircumvention

tools without completely shutting down the

Internet. Tools aim to shape their trac patterns to match

unblocked programs, so that simple trac proling cannot

identify the tools within a reasonable number of traces; the

censors respond by deploying rewalls 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 ellipticcurve

systems in which elliptic-curve points are encoded so

as to be indistinguishable from uniform random strings.

Slides: http://cr.yp.to/talks/2013.05.31/slides-dan+tanja-20130531-4x3.pdf

Paper:

http://cr.yp.to/elligator/elligator-20130527.pdf