International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Masaaki Shirase
Download:
URL: http://eprint.iacr.org/2010/134
Search ePrint
Search Google
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 $\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 $z\bmod{12}$ 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 $\Fp$ always becomes a BN curve for any $z$ with $z \equiv 2,11\!\!\!\pmod{12}$. Let $n_i(z)$ be irreducible. Then, to construct a pairing-friendly elliptic curve, it is enough to find an integer $z$ of appropriate size such that $p(z)$ and $n_i(z)$ are primes.
BibTeX
@misc{eprint-2010-23035,
  title={Barreto-Naehrig Curve With Fixed Coefficient - Efficiently Constructing Pairing-Friendly Curves -},
  booktitle={IACR Eprint archive},
  keywords={foundations / Pairing-friendly elliptic curve, Barreto-Naehrig curve, twist, Gauss' theorem, Euler's conjecture},
  url={http://eprint.iacr.org/2010/134},
  note={ shirase@fun.ac.jp 14778 received 11 Mar 2010, last revised 18 Jun 2010},
  author={Masaaki Shirase},
  year=2010
}