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?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ 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. $\endgroup$– yyyyyyyMay 24, 2019 at 14:08
-
$\begingroup$ @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? $\endgroup$– satyaMay 24, 2019 at 14:44
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ 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? $\endgroup$– satyaMay 26, 2019 at 1:02
-
$\begingroup$ I mean that $p$ is an $n$-bit value, and $a$ and $b$ are sampled from $[0, p-1]$. $\endgroup$ May 26, 2019 at 1:31