# Is there a concept of embedding degree for non-pairing based elliptic curves?

From this post, I learned the concept of embedding degree. Intuitively, if embedding degree of an elliptic curve $$E(F_p)$$ is $$k$$, it means there is a way to transform points in $$E(F_p)$$ to $$F_{p^k}$$. Is the concept of embedding degree only valid for pairing-based elliptic curves, or does the same hold even for non-pairing based elliptic curves?

• Every elliptic curve admits a pairing, and hence the embedding degree makes sense. "Pairing-friendly" means that the embedding degree is particularly small and therefore the pairing can be computed efficiently, but the Weil pairing itself exists for all curves. – yyyyyyy May 24 at 14:08
• @yyyyyyy I heard that there are 3 types of pairings: weil, tate and ate pairings. So, do all 3 pairings exist on every elliptic curve? – satya May 24 at 14:44

As pointed out by @yyyyyyy, every curve does have an embedding degree, i.e., there is some $$k$$ for which $$p^k - 1$$ is a multiple of $$r$$, the order one of the subgroups of a curve defined over $$\mathbb{F}_p$$.
There is a relevant result from Koblitz and Balasubramanian that establishes that the probability that the embedding degree of a random $$n$$-bit curve of prime order is "small" is vanishingly low: $$\mathbf{Pr}[l \mid p^k - 1 \text{ and } k \le (\log p)^2] \le c_3 \frac{(\log 2^n)^9(\log \log 2^n)^2}{2^n} \,.$$ As such, only "special" curves that are explicitly designed to have small embedding degree $$k$$, i.e., pairing-friendly curves, are effectively computable; but the pairing does exist for all of them.
• What does it mean to say n-bit curve? If the elliptic curve is of the form $y^2 = x^3 + ax + b$, do you mean $a, b$ are randomly sampled $n$-bit values? – satya May 26 at 1:02
• I mean that $p$ is an $n$-bit value, and $a$ and $b$ are sampled from $[0, p-1]$. – Samuel Neves May 26 at 1:31