How rare are elliptic curves with a low embedding degree?
To implement pairing-based cryptography, we want elliptic curve groups with a low embedding degree. These are actually fairly rare. The following result by Balasubramanian and Koblitz gives us a rough idea or exactly how rare they are:
Let q be a randomly chosen prime with M/2 ≤ q ≤ M and E/GF(q) a randomly chosen elliptic curve. If #E(GF(q)) = p for some prime p, then the probability that p | (qk – 1) for some k ≤ (log q)2 is less than c (log M)9 (log log M)2 / M for some constant c.
We can summarize what the BK theorem tells us as saying that the chances of an embedding degree being low (k ≤ (log q)2) are extremely small ((log M)9 (log log M)2 / M).
This doesn’t cover the exact case that we're interested in because we don't always have #E being a prime. That actually doesn't happen very often. But let's suppose that the same estimate is still valid for cases where #E isn't a prime and see how rare we can expect low embedding degrees to be.
Let's suppose that we want to find a curve that's suitable for use at the 128-bits-of-security level. At that level, q has at least 256 bits, so that the value M in the BK theorem also has at least 256 bits. At that point, the probability of a random curve having a low embedding degree is actually so low that you can expect it to essentially never happen: ignoring the constant c, we get the estimate that this probability is no more than 2-178.
That's only if you're picking a random curve, of course. If you're picking a curve by other means, you can still find ones with a low enough embedding degree to be useful. It's easy to find BN curves (embedding degree k = 12) at the 128-bit level, for example, but doing that isn't the same thing as picking a random curve.
And the bound of (log q)2 can actually be impractically big for useful sizes of q. If q has 256 bits then (log q)2 is roughly 2562 = 65,536, and implementing anything over such a GF(q65,536) isn't practical. An element of GF(q65,536) is a vector of 65,536 components, each of which has 256 bits, for a total of 16,777,216, or 224, bits. Those aren't practical to do public-key operations with.
The bottom line is that most elliptic curves aren't useful for pairing-based cryptography. So if you need a curve to use in this way, don't try to pick random curves until you find one that works. That's a very bad idea. Instead, just get one from the IEEE P1363.3 standard. Or if you don't want to do that, get a copy of "A Taxonomy of Pairing-friendly Elliptic Curves" by David Freeman, Michael Scott and Edlyn Teske. That should give you all that you need to find your own curve.