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

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Pairing-friendly elliptic curveBarreto-Naehrig curvetwistGauss' theoremEuler's conjecture
Contact author(s)
shirase @ fun ac jp
History
2010-06-18: last of 2 revisions
2010-03-12: received
See all versions
Short URL
https://ia.cr/2010/134
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/134,
      author = {Masaaki Shirase},
      title = {Barreto-Naehrig Curve With Fixed Coefficient - Efficiently Constructing Pairing-Friendly Curves -},
      howpublished = {Cryptology {ePrint} Archive, Paper 2010/134},
      year = {2010},
      url = {https://eprint.iacr.org/2010/134}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.