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

Transfers

A "transfer" converts ECDLP into a "linear algebraic group" DLP. There are several types of transfers for an elliptic-curve group of prime order ℓ over a prime field F_p:

  • Additive transfer: applicable when ℓ equals p. The target group is the additive group F_p, where DLP is very easy to solve.
  • Degree-1 multiplicative transfer: applicable when ℓ divides p-1. The target group is the multiplicative group F_p^*, where DLP is solved in subexponential time by index calculus. The standard estimates are that current index-calculus methods break DLP in F_p^* at cost below 2^128 for p up to roughly 2^3000.
  • Degree-2 multiplicative transfer: applicable when ℓ divides p^2-1. The target group is the multiplicative group F_{p^2}^*, where DLP is solved in subexponential time by index calculus. The standard estimates are that current index-calculus methods break DLP in F_{p^2}^* at cost below 2^128 for p up to roughly 2^1500.
  • Degree-3 multiplicative transfer: applicable when ℓ divides p^3-1. The target group is the multiplicative group F_{p^3}^*, where DLP is solved in subexponential time by index calculus. The standard estimates are that current index-calculus methods break DLP in F_{p^3}^* at cost below 2^128 for p up to roughly 2^1000.
  • Et cetera.

The minimum possible multiplicative-transfer degree for a particular elliptic-curve group is called the embedding degree of that group. Standards vary in the requirements they place upon the embedding degree:

  • SEC1 requires the embedding degree to be at least 20.
  • X9.62 requires the embedding degree to be at least 20.
  • P1363 puts variable requirements upon the embedding degree, depending on the size of p, but never requires it to be more than 30.
  • Brainpool requires the embedding degree to be much larger, at least (ℓ-1)/100.

The SEC/X9.62/P1363 approach is risky: there is a long history of improvements to index calculus, and the point of ECC has always been to avoid index calculus. The Brainpool approach is clearly overkill, but is also non-controversial, since it rules out only a small fraction of curves.

SafeCurves takes the overkill approach. Pairing-based cryptography requires the risky approach, but pairing-based cryptography is outside the scope of SafeCurves.

The following table shows the transfer possibilities for various curves:

Curve

Safe against additive transfer?

Safe against multiplicative transfer?

Embedding degree

Anomalous

False

Unverified

Unverified

M-221

True

True

210624583337114373395836055367341083963447540990198152472167526445
= (l-1)/2

E-222

True

True

1684996666696914987166688442938726735569737456760058294185521417406
= (l-1)/1

NIST P-224

True

True

8986648889050213264889005029006541980152602571474797240560907456020
= (l-1)/3

Curve1174

True

True

904625697166532776746648320380374280092339035279495474023489261773642975600
= (l-1)/1

Curve25519

True

True

1206167596222043702328864427173832373476186059896651267666991823047575708498
= (l-1)/6

BN(2,254)

True

False

12
= (l-1)/1399842394251319357078400345185977825813298300283729395752364905347130851329

brainpoolP256t1

True

True

38442478198522672110404873314500824546368765892207264769377759531531768179539
= (l-1)/2

ANSSI FRP256v1

True

True

18242428555282879769611787505122521357667424468567068775512033867954346593872
= (l-1)/6

NIST P-256

True

True

38597363070118749587565815649802524509998985074711920114140753020356170681456
= (l-1)/3

secp256k1

True

True

19298681539552699237261830834781317975472927379845817397100860523586360249056
= (l-1)/6

E-382

True

True

307828173409331868845930000782371982852185463050511302093217254319707881820581146407832415835405575543260510130915
= (l-1)/8

M-383

True

True

2462625387274654950767440006258975862817483704404090416746934574041288984234680883008327183083615266784870011007446
= (l-1)/1

Curve383187

True

True

164175025818310330051162667083931724187832246960272694449808294574171658707062956691328325176707128453292808794080
= (l-1)/15

brainpoolP384t1

True

True

5414817692529829043267309210583151244949029096754412150018911318705402875339628884490673779342225813057400429680985
= (l-1)/4

NIST P-384

True

True

2814429014028177086591360007153115271791409947890389047710493234259118528508090254957068307725163922396745260995903
= (l-1)/14

Curve41417

True

True

5288447750321988791615322464262168318627237463714249754277190328831105466135348245791335989419337099796002495788978276839288
= (l-1)/1

Ed448-Goldilocks

True

True

90854840536950861318665475986000566794205170085914757535186274897573001980769792858097877645846187981655146854545831152386877929824889
= (l-1)/2

M-511

True

True

279329331873804106241125520795955127655820121262341528702574196744203417293202470268292259794351836254047019752832482978329017502925208720820310245980766
= (l-1)/3

E-521

True

True

1716199415032652428745475199770348304317358825035826352348615864796385795849413675475876651663657849636693659065234142604319282948702542317993421293670108522
= (l-1)/1

How stable is the security story for transfers?

All of these transfers have been known since the 1990s. Multiplicative transfers were introduced in 1993 Menezes–Okamoto–Vanstone, 1994 Frey–Rück, 1996 Semaev; they are often called the "MOV attack". Additive transfers were introduced in 1998 Semaev, 1998 Satoh–Araki, and 1999 Smart; they are often called the "Smart-ASS attack".


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