I'm learning about Elliptic curve cryptography. If I understand right, ECDSA and other algorithms used in ECC are dependent on the curve chosen. So, before you want to use ECDSA, you first have to choose a suitable curve.

Pairing-friendly curves are a special kind of elliptic curves that have properties that allow for different algorithms not available on every elliptic curves such as BLS or Identity-Based Encryption.

In this publication there is written on page 8:

Following the discovery of these attacks in the early 1990s, the consensus was that elliptic curves with low embedding degrees should not be used in discrete log protocols. In fact many standards for elliptic curve cryptography such as ANSI X9.62 [3] explicitly forbid the use of such curves. However, low-embedding degree elliptic curves are now very much back in vogue since they are crucial for the efficient realization of the pairing-based protocols that were presented in §3.

Let's say I wanted to use ECDSA (which is based on the discrete log problem I believe) over a pairing-friendly curve (like alt_bn128). According to this, the pairing-friendly curve is supposed to have a low-embedding degree and shouldn't be used with ECDSA.

Am I understanding this correctly? Does that mean the cryptographic primitives one can use on pairing-friendly curves should be specifically designed for pairing-friendly curves (like BLS)?


You can. Low-embedding degree may be bad due to the MOV attack, but pairing-friendly curves are particularly chosen so that the embedding degree is low but still enough to not decrease security. So any elliptic curve algorithm should be safe on the curve, not only pairing-based ones.

Some observations:

  • ECDSA if often used with NIST curves with cofactor 1. However, some pairing-friendly curves have larger cofactors, so you need to take that into account. For example, the BLS12-381 curve has a 381-bit prime but the main subgroup has 255 bits, therefore is has around $255/2 \approx 128$ bits of security (and not $381/2$)
  • It's still a bit riskier than using high-embedding degree curves. If there are advances in attacks against discrete logs in finite fields then the curve security can decrease. In fact, this has already happened once: for example, the BN256 curve security was reduced from 128 bits to 110 bits.

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.