# What is embedding degree?

What is the embedding degree of an elliptic curve group and what does it mean? And why is this important to understand when you’re implementing pairing-based cryptographic algorithms?

Suppose that we have a pairing *e: G*_{1 }x *G*_{2} → *G _{T }*where

*p*and

*q*are primes,

*G*

_{1},

*G*

_{2}and

*G*all have order

_{T}*p,*and

*G*is a subgroup of GF(

_{T }*q*)*. In most of the useful cases,

^{k}*G*

_{1 }is a subgroup of

*E*[

*p*] for some elliptic curve

*E*/GF(

*q*), while

*G*

_{2}is either a subgroup of either

*E*[

*p*] or

*E*’[

*p*] for some other elliptic curve

*E*’ (usually a twist of

*E*).

Note that when *q* is a power of a prime the usual definition of embedding degree actually doesn’t quite have the properties that we’d like it to have. See this discussion, for example. Let’s just consider the case where *q* is a prime here so that we don’t have to worry about that. That includes all of the cases that are useful for implementing pairing-based cryptography, so that’s not a huge restriction.

Note that *G*_{1}, *G*_{2}, and *G _{T}* are all isomorphic. To see why this is true, pick

*P*

_{0 }∈

*G*

_{1}and

*Q*

_{0 }∈

*G*

_{2}, and we have that

*e*(

*P*,

*Q*

_{0}) is an isomorphism from

*G*

_{1}to

*G*and

_{T}*e*(

*P*

_{0},

*Q*) is an isomorphism from

*G*

_{2}to

*G*.

_{T}This means that the points in *G*_{1} or *G*_{2} that are of order *p* get mapped to points in *G _{T}* that are also of order

*p*by the isomorphism. In particular, because

*pP*=

*O*for

*P*∈

*G*

_{1}we have

*g*= 1 for

^{p}*g*∈

*G*, or that the elements of

_{T}*G*

_{T}_{ }are really the

*p*th roots of 1 in GF(

*q*)*.

^{k}Now GF(*q ^{k}*)* is cyclic and of order

*q*– 1 and the order of the subgroup

^{k}*G*needs to divide

_{T }*q*– 1. Euler's theorem tells us that

^{k}*q*

^{p}^{-1}≡ 1 (mod

*p*) or that

*p*|

*q*

^{p}^{-1}- 1, but there might be value of

*k*<

*p*– 1 for which we also have

*p*|

*q*- 1. The smallest

^{k}*k*for which this is true is called the

*embedding degree*of the group

*G*

_{1}.

People sometimes talk about the embedding degree of an elliptic curve, but to be careful, you really need to talk about the embedding degree of a subgroup of an elliptic curve group (or possibly of the order of the subgroup). In any case, it’s the degree of the extension of GF(*q*) which lets us have a subgroup of GF(*q ^{k}*)* that’s isomorphic to

*G*

_{1}.

This table shows the embedding degrees that we get for a few small values where we have *E*/GF(*q*): *y*^{2} = *x*^{3} + *ax* + *b* and *G*_{1} is a subgroup of order *p *of *E*(GF(*q*)). Note that for *q *= 23 the embedding degree is different for the subgroups of order 3 and 5, even for the same elliptic curve, so that just talking about the embedding degree of an elliptic curve can cause confusion.

q |
a |
b |
#E |
p |
k |

11 | 2 | 7 | 7 | 7 | 3 |

13 | 6 | 9 | 17 | 17 | 4 |

17 | 8 | 3 | 11 | 11 | 10 |

19 | 3 | 17 | 16 | 2 | 1 |

23 | 7 | 13 | 30 | 3 | 2 |

23 | 7 | 13 | 30 | 5 | 4 |

29 | 21 | 26 | 26 | 13 | 3 |

31 | 20 | 12 | 17 | 17 | 16 |

31 | 3 | 1 | 29 | 29 | 28 |

Because it’s cyclic, we can write GF(*q ^{k}*)* = {α, α

^{2}, α

^{3}, … ,α

^{qk-1}}. Writing

*r*= (

*q*– 1) /

^{k }*p*and β = α

*we can write the*

^{r}*p*th roots of 1 in GF(

*q*)* as β, β

^{k}^{2},

**…,**β

*which makes it easier to see the correspondence between the points of*

^{p}*G*and the points of

_{T}*G*

_{1}= {

*P*, 2

*P*, …,

*pP*} .

When you’re implementing pairing-based cryptography, it’s useful to have elliptic curve groups that have a low embedding degree. For the Tate pairing, for example, the arithmetic used to calculate the value of the pairing is performed in GF(*q ^{k}*)*, so if

*k*is too big, it can be impractical to do this calculation. In the example above with

*q*= 31 and

*p*= 29, the arithmetic would need to be done in GF(31

^{28})*, where elements have 28 coordinates instead of just one, so that arithmetic would be much more expensive than it would be in GF(31).

But a low embedding degree also means that you need parameters that are bigger than those that you might expect for cryptographic algorithms that use elliptic curves. To get 128 bits of strength, for example, you can use an elliptic curve group whose order is a 256-bit prime. But if we have a pairing we can calculate discrete logs in *G*_{1} by calculating discrete logs in *G _{T}*. To find the discrete log of

*nP*in

*G*

_{1}we can calculate the discrete log of

*e*(

*nP*,

*P*) =

*e*(

*P*,

*P*)

*in*

^{n}*G*.

_{T}Suppose *G*_{1} is a subgroup of *E*(GF(*q*))[*p*], where *p* and* q* are primes that have 256 bits and *G*_{1} has embedding degree 2. This means that we can find *n* by calculating the discrete log of *nP* in *G*_{1}, which takes about 128 bits of work, or we could find *n* by calculating the discrete log of *e*(*P*,*P*)^{n}^{ }in *G _{T}*, which takes much less work.

According to the guidelines in the Implementation Guidance to FIPS 140-2 (PDF), (Section 7.5, Strength of Key Establishment Methods) that actually takes about 64 bits of work, the amount of work needed to calculate discrete logs in GF(*q*^{2}), where *q*^{2 }has 256 bits x 2 = 512 bits.

But it’s easy to keep 128 bits of strength by using a group with a higher embedding degree. If we use a group whose order has 256 bits and has embedding degree 12 then calculating discrete logs in *G _{T} *also takes 128 bits of work (256 bits x 12 = 3,072 bits, the size of GF(

*n*)* that’s required to have 128 bits of strength).

It turns out that most elliptic curve groups have fairly big embedding degrees. So if you pick a random elliptic curve, it’s very unlikely to be useful for pairing-based cryptography. More on that tomorrow. (If I can recover from the trauma of getting that table converted to HTML by then, that is.)