Search

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$.

\begin{aligned} p(z) &= 36 z^4 + 36 z^3 + 24 z^2 + 6 z + 1\\ r(z) &= 36 z^4 + 36 z^3 + 18 z^2 + 6 z + 1\\ t(z) &= 6 z^2 + 1 \end{aligned}

The class of curves has the Short-Weierstrass form:

$y^2 \equiv x^3 + b$

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

© 2020 Jan Jancar | Built with Dox theme for Gatsby