4
$\begingroup$

I am new to ECC. I am confused about what the embedding degree in an elliptic curve group represents and what is the impact of its values on the curve and security (small values or large values?)

What does the following mean:

The elliptic curve group used has a 160-bit group order, the base field size is 512-bit, the embedding degree is 2

$\endgroup$
5
$\begingroup$

Informally, you can think of the embedding degree as the smallest integer $k$ that lets you transform or embed an instance of the elliptic curve discrete logarithm problem (ECDLP) over an elliptic $E(\mathbb{F}_p)$ into an instance of the discrete log problem (DLP) over the field $\mathbb{F}_{p^k}$.

Answering the specific question: we have an elliptic curve over a finite field $E(\mathbb{F}_p)$, where $\log(p) = 512$. There is a subgroup with order $\log(q) = 160$ bits. Finally, there is a transformation from the elliptic curve to $\mathbb{F}_{p^2}$, where $p^2$ has $\log p^2 = 1024$ bits. (The exponent "$2$" here is the embedding degree.)

Recall that the fastest algorithms known for solving the ECDLP are of order $O(\sqrt{p})$ steps for the ECDLP over $E(\mathbb{F}_p)$, whereas the DLP can be solved in subexponential time using, say, the index calculus. This transformation opens up the solution of the ECDLP to techniques from DLP, depending on the curve you choose.

Generally speaking, you want $k$ to be large to resist faster solution via transformation to the DLP.


I'm leaving out heavier details because the OP was new to ECC, but to be more precise, if you have a curve $E(\mathbb{F}_p)$, and one point in $E(\mathbb{F}_p)$ has order $q$ where $q \neq p$ is a prime, then the embedding degree with respect to $q$ is the smallest value $k$ such that $q | p^k - 1$, or $p^k \equiv 1 \bmod q$, assuming $p \not\equiv 1 \bmod q$.

I also left out that the Weil pairing does the embedding, and is used in the MOV algorithm. A similar attack is the Frey-Rück attack carried out using Tate pairings.

$\endgroup$
  • $\begingroup$ here p is prime right? $\endgroup$ – David 天宇 Wong May 22 '18 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.