SafeCurves:
choosing safe curves for elliptic-curve cryptography


Introduction
Curve parameters:
Fields
Equations
Base points
Prime proofs
ECDLP security:
Rho
Transfers
Discriminants
Rigidity
ECC security:
Ladders
Twists
Completeness
Indistinguishability
More information:
References
Verification

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.


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