
Indistinguishability from uniform random strings
Standard representations of ellipticcurve points
are easily distinguishable from uniform random strings.
This poses a problem for many cryptographic protocols using elliptic curves:
censorshipcircumvention protocols, for example,
and passwordauthenticated keyexchange protocols.
The typical workaround is for the protocol
to bounce randomly between a curve and its twist
(assuming
twist security),
but this is complicated and errorprone.
For example,
a passwordauthenticated keyexchange protocol from 2001 Boyd–Montague–Nguyen
was discovered more than ten years later to be breakable by a twist attack.
2013 Bernstein–Hamburg–Krasnova–Lange
introduced the following solution to the underlying problem.
Construct an efficient constanttime bijective map
between a large set of bbit strings
(large enough to be indistinguishable from all bbit strings;
i.e., very close to 2^b possibilities)
and a large set of rational points on an elliptic curve
(e.g., about half of all points).
Use uniform random points in this set,
and represent them by the corresponding strings under this bijective map.
These strings are indistinguishable from uniform random bbit strings.
Known constructions of these bijective maps
place various requirements on the elliptic curve.
Specifically:
 "Elligator 1" requires a prime congruent to 3 mod 4
and a complete Edwards curve x^2+y^2=1+dx^2y^2
where d has the form (c+1)^2/(c1)^2 with c=2/s^2.
The idea of Elligator 1 can be extended to more curves
but is inherently limited to primes congruent to 3 mod 4
and to curves whose group order is a multiple of 4.
 "Elligator 2" works for any odd prime
and any curve of the form y^2=x^3+Ax^2+Bx with nonzero AB(A^24B).
This includes all Montgomery curves y^2=x^3+Ax^2+x except for one curve y^2=x^3+x.
It also includes, after conversion,
all Edwards curves x^2+y^2=1+dx^2y^2 except for one curve x^2+y^2=1x^2y^2.
More generally, it includes all curves with points of order 2,
except for jinvariant 1728.
 There is another construction for Hessian curves.
The order of a Hessian curve is always a multiple of 3.
The following table reports the availability of these maps
for various existing curves:
Curve 
Supports indistinguishability? 
Notes 
Anomalous

False

Elligator 2: No.

M221

True✔

Elligator 2: Yes.

E222

True✔

Elligator 2: Yes.

NIST P224

False

Elligator 2: No.

Curve1174

True✔

Elligator 2: Yes.

Curve25519

True✔

Elligator 2: Yes.

BN(2,254)

False

Elligator 2: No.

brainpoolP256t1

False

Elligator 2: No.

ANSSI FRP256v1

False

Elligator 2: No.

NIST P256

False

Elligator 2: No.

secp256k1

False

Elligator 2: No.

E382

True✔

Elligator 2: Yes.

M383

True✔

Elligator 2: Yes.

Curve383187

True✔

Elligator 2: Yes.

brainpoolP384t1

False

Elligator 2: No.

NIST P384

False

Elligator 2: No.

Curve41417

True✔

Elligator 2: Yes.

Ed448Goldilocks

True✔

Elligator 2: Yes.

M511

True✔

Elligator 2: Yes.

E521

True✔

Elligator 2: Yes.

Version:
This is version 2013.10.13 of the ind.html web page.
