Barreto-Naehrig curves

A class of pairing-friendly curves with embedding degree $k = 12$. Given an integer $z \in \mathbb{N}$ the BN 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$.

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 generated curves can be found in the BN category.

The following SageMath code generates BN curves with embedding degree $12$.

class BN(object):
    @staticmethod
    def generate_prime_order(zbits):
        while True:
            z = randint(2^(zbits - 1), 2^zbits)
            pz = int(BN.p(z))
            if not is_prime(pz):
                continue
            rz = int(BN.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

    @staticmethod
    def p(z):
        return 36 * z^4 + 36 * z^3 + 24 * z^2 + 6 * z + 1
    @staticmethod
    def r(z):
        return 36 * z^4 + 36 * z^3 + 18 * z^2 + 6 * z + 1
    @staticmethod
    def t(z):
        return 6 * z^2 + 1

References

• Paulo S. L. M. Barreto, Michael Naehrig: Pairing-Friendly Elliptic Curves of Prime Order
• Geovandro C. C. F. Pereira, Marcos A. Simplício Jr., Michael Naehrig, Paulo S. L. M. Barreto: A Family of Implementation-Friendly BN Elliptic Curves
• Diego F. Aranha, Laura Fuentes-Castaneda, Edward Knapp, Alfred Menezes, Francisco Rodríguez-Henríquez: Implementing Pairings at the 192-bit Security Level