Paper 2010/134

Barreto-Naehrig Curve With Fixed Coefficient - Efficiently Constructing Pairing-Friendly Curves -

Masaaki Shirase

Abstract

This paper describes a method for constructing Barreto-Naehrig (BN) curves and twists of BN curves that are pairing-friendly and have the embedding degree $12$ by using just primality tests without a complex multiplication (CM) method. Specifically, this paper explains that the number of points of elliptic curves $y^2=x^3\pm 16$ and $y^2=x^3\pm 2$ over $\text{Fp}$ is given by 6 polynomials in $z$, $n_0(z),\cdots ,n_5(z)$, two of which are irreducible, classified by the value of $zmod12$ for a prime $p(z)=36z^4+36z^3+24z^2+6z+1$ with $z$ an integer. For example, elliptic curve $y^2=x^3+2$ over $\text{Fp}$ always becomes a BN curve for any $z$ with $z\equiv 2,11(\mathrm{mod}12)$. Let $$ be irreducible. Then, to construct a pairing-friendly elliptic curve, it is enough to find an integer $$ of appropriate size such that $$ and $$ are primes.