7
$\begingroup$

I am dealing with MOV algorithm to transform ECDLP to DLP in $GF(p^k)$, but at the first step I have to determine embedding degree k. I have read the definitions of embedding degree, but still I am not sure, how to compute it and what exactly it states for. As far as I understand embedding degree is not equal to the degree of the curve.

I would be grateful, if somebody could clarify, what the embedding degree stands for, and how to calculate.

$\endgroup$
4
  • 2
    $\begingroup$ I don't really know this stuff, but isn't it simply the smallest value of $k$ in which you can move the ECDLP to the DLP? $\endgroup$
    – user14972
    Commented Jun 7, 2014 at 17:35
  • $\begingroup$ Well, I think this is true, but still I am not sure how to calculate it, and from which paramters of elliptic curve it is derived... $\endgroup$
    – abs
    Commented Jun 7, 2014 at 17:47
  • $\begingroup$ It shouldn't depend on the parameters, just on the exponent of the group of points. As I understand it, you're simply asking "what is the smallest $k$ such that $GF(p^k)^*$ has a subgroup of the right size?" $\endgroup$
    – user14972
    Commented Jun 7, 2014 at 17:48
  • $\begingroup$ Yes, this is my question. $\endgroup$
    – abs
    Commented Jun 7, 2014 at 17:49

2 Answers 2

15
$\begingroup$

My answer will probably not be perfect, but I will try to convey my own understanding.

When you try to implement the MOV attack (or try to guard from it) what you need to do is transfer the discrete logarithm problem from an EC over $\mathbb{F}_p$ to a finite field $\mathbb{F}_{p^k}$.

For this it is important to note that you are not actually embedding the whole EC group but rather just the cyclic subgroup $\langle P\rangle$ generated by the point $P$ which is the base of your logarithm problem (i.e. $P^d=Q$ or in additive terms for an EC $[d]P=Q$).

We assume that the order $|\langle P\rangle |=l$ is prime (this will be true for pretty much all standard ECC applications). And our goal will be to embed $\langle P \rangle$ into the group of roots of 1 over some appropriate $\mathbb{F}_{p^k}$. For this to be possible there must be enough roots of 1 in the appropriate field and this happens when $l|(p^k-1)$. Since we are trying to be efficient we will want the lowest such $k$ which we call the embedding degree (note this should be the embedding degree of $P$ but since there normally is only one reasonable subgroup of an EC for ECC purposes it seems to be often called the embedding degree of the curve).

To find the embedding degree we first note that $l|(p^k-1)$ is the same as saying that $p^k\equiv 1 \mod l$. Wanting the minimal such $k$ is then equivalent to asking for the multiplicative order of $p$ in $\mathbb{F}_l$. Note that since both $p$ and $l$ are prime $p$ must be a unit in $\mathbb{F}_l$. Moreover we get $p^{l-1}\equiv 1 \mod l$ by Fermat's little theorem.

This gives us an upper bound on $k$. Further we can see that the order of $p$ must divide $l-1$ and so factoring $l-1$ gives us all candidates for $k$, which we can then test.

$\endgroup$
2
  • $\begingroup$ Could you explain how you get from solving the congruense to finding the multiplicative order? Why are the two problems equivalent? $\endgroup$
    – Alice
    Commented Oct 2, 2016 at 11:49
  • $\begingroup$ "And our goal will be to embed $⟨P⟩$ into the group of roots of 1 over some appropriate $F_{p^k}$" - I don't understand the "roots of 1" part here - why should it be roots of unity? Could you please explain? $\endgroup$
    – user93353
    Commented Oct 24, 2022 at 7:49
1
$\begingroup$

In a $\textbf{MOV/Frey-Rück}$ context;

Let $E$ be an elliptic curve defined over a finite field $\mathbb{F}_q$, let $n$ be a prime dividing $\#E(\mathbb{F}_q)$. The $\textbf{embedding degree}$ of $E$ with respect to $n$ is the smallest integer $k$ such that $n$ divides $q^k - 1$.

Example

Let $E: y^2 = x^3 + 1$ be an elliptic curve defined over $\mathbb{F}_{101}$.

By Hasse/Waterhouse Theorem'; observe that $\#E(\mathbb{F}_q)$ = 101 + 1 = 2*3*17.

Let $n = 17$.

Since $17|101^2-1$ we call $k = 2$ the embedding degree of $E$ with respect to $n$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .