SafeCurves:
choosing safe curves for elliptic-curve cryptography

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".