1
$\begingroup$

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?

$\endgroup$
  • 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$ – yyyyyyy May 24 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$ – satya May 24 at 14:44
1
$\begingroup$

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.

$\endgroup$
  • $\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$ – satya May 26 at 1:02
  • $\begingroup$ I mean that $p$ is an $n$-bit value, and $a$ and $b$ are sampled from $[0, p-1]$. $\endgroup$ – Samuel Neves May 26 at 1:31

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.