SafeCurves:
choosing safe curves for elliptic-curve cryptography

Indistinguishability from uniform random strings

Standard representations of elliptic-curve points are easily distinguishable from uniform random strings. This poses a problem for many cryptographic protocols using elliptic curves: censorship-circumvention protocols, for example, and password-authenticated key-exchange 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 error-prone. For example, a password-authenticated key-exchange 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 constant-time bijective map between a large set of b-bit strings (large enough to be indistinguishable from all b-bit 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 b-bit 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/(c-1)^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^2-4B). 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=1-x^2y^2. More generally, it includes all curves with points of order 2, except for j-invariant 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.
M-221	True✔	Elligator 2: Yes.
E-222	True✔	Elligator 2: Yes.
NIST P-224	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 P-256	False	Elligator 2: No.
secp256k1	False	Elligator 2: No.
E-382	True✔	Elligator 2: Yes.
M-383	True✔	Elligator 2: Yes.
Curve383187	True✔	Elligator 2: Yes.
brainpoolP384t1	False	Elligator 2: No.
NIST P-384	False	Elligator 2: No.
Curve41417	True✔	Elligator 2: Yes.
Ed448-Goldilocks	True✔	Elligator 2: Yes.
M-511	True✔	Elligator 2: Yes.
E-521	True✔	Elligator 2: Yes.