Note on families of pairing-friendly elliptic curves with small embedding degree
This work addresses a foundational challenge in pairing-based cryptography by clarifying limitations in generating efficient elliptic curves, which is incremental as it builds on known results like the Barreto-Naehrig curve.
The paper tackled the problem of identifying ideal families of pairing-friendly elliptic curves with small embedding degrees, proving that no ideal families exist for embedding degrees 3, 4, or 6, and that many complete families for degrees 8 or 12 are nonideal, even with noncyclotomic choices.
Pairing-based cryptographic schemes require so-called pairing-friendly elliptic curves, which have special properties. The set of pairing-friendly elliptic curves that are generated by given polynomials form a complete family. Although a complete family with a $ρ$-value of 1 is the ideal case, there is only one such example that is known, this was given by Barreto and Naehrig. We prove that there are no ideal families with embedding degree 3, 4, or 6 and that many complete families with embedding degree 8 or 12 are nonideal, even if we chose noncyclotomic families.