Barreto-Lynn-Scott curves

A class of pairing-friendly curves with embedding degree $k \in \{12, 24\}$.

BLS12

Given an integer $z \in \mathbb{N}$ the BLS curve with embedding degree $12$ can be constructed over a prime field $\mathbb{F}_p$ with the number of points $r$ and a trace of Frobenius $t$.

BLS24

Given an integer $z \in \mathbb{N}$ the BLS curve with embedding degree $24$ can be constructed over a prime field $\mathbb{F}_p$ with the number of points $r$ and a trace of Frobenius $t$.

The class of curves has the Short-Weierstrass form:

where given $z$ such that $p(z)$ is prime, a curve with a prime order subgroup of $r(z)$ points can be found either via complex multiplication or by exhaustively trying small coefficients $b$ until a curve is found. Some generate curves can be found in the BLS category.

The following SageMath code generates BLS curves with embedding degree $12$ and $24$.

class BLS(object):
    @classmethod
    def generate_prime_order(cls, zbits):
        while True:
            z = randint(2^(zbits - 1), 2^zbits)
            pz = int(cls.p(z))
            if not is_prime(pz):
                continue
            rz = int(cls.r(z))
            if not is_prime(rz):
                continue
            break
        K = GF(pz)
        b = 1
        while True:
            curve = EllipticCurve(K, [0, b])
            card = curve.cardinality()
            if card % rz == 0:
                break
            b += 1
        return curve


class BLS12(BLS):
    @staticmethod
    def p(z):
        return (z - 1)^2 * (z^4 - z^2 + 1)/3 + z
    @staticmethod
    def r(z):
        return z^4 - z^2 + 1
    @staticmethod
    def t(z):
        return z + 1


class BLS24(BLS):
    @staticmethod
    def p(z):
        return (z - 1)^2 * (z^8 - z^4 + 1)/3 + z
    @staticmethod
    def r(z):
        return z^8 - z^4 + 1
    @staticmethod
    def t(z):
        return z + 1

References

• Paulo S. L. M. Barreto, Ben Lynn, Michael Scott: Constructing Elliptic Curves with Prescribed Embedding Degrees
• Diego F. Aranha, Laura Fuentes-Castaneda, Edward Knapp, Alfred Menezes, Francisco Rodríguez-Henríquez: Implementing Pairings at the 192-bit Security Level