This crate implements elliptic curve arithmetic and bilinear pairings for Barreto-Naehrig (BN) curves. It has been created to commemorate the 20th anniversary of the discovery of those curves in 2005.
A BN curve is specified by an integer parameter u ∈ ℤ such that the value p ≔ 36u⁴ + 36u³ + 24u² + 6u + 1 is prime, defining a finite field Fp.
The additional constraint p ≡ 3 (mod 4) is typical, since it enables specifying the quadratic extension Fp² = Fp [i]/<i² + 1> and the tower-friendly extension fields Fp⁴ = Fp² [τ]/<τ² + ξ> and Fp¹² = Fp² [z]/<z⁶ + ξ>, where ξ = 1 + i.
The BN curve equation is E/Fp : Y² Z = X³ + b Z³, whose number of points is n ≔ #E(Fp) = 36u⁴ + 36u³ + 18u² + 6u + 1, which is usually required (with a careful choice of the curve parameter u) to be prime. The underlying finite field and the number of points are thus related as n = p + 1 - t where t ≔ 6u² + 1 is the trace of the Frobenius endomorphism on the curve.
The default quadratic twist of the curve is E'/Fp² : Y'² Z' = X'³ + b' Z'³ with b' ≔ b/ξ, whose number of points is n' ≔ #E'(Fp²) = h' n where h' ≔ p - 1 + t is called the cofactor of the curve twist.
All supported curves were selected so that the BN curve parameter is a negative number (so that field inversion can be replaced by conjugation at the final exponentiation of a pairing) with absolute value of small Hamming weight (typically 5 or less), ceil(lg(p)) = 64×LIMBS - 2 for 64-bit limbs, and the curve equation coefficients are always b = 2 and b' = 1 - i.
With this choice, a suitable generator of n-torsion on E/Fp is the point G ≔ [-1 : 1 : 1], and a suitable generator of n-torsion on E'/Fp² is the point G' ≔ [h']G₀' where G₀' ≔ [-i : 1 : 1]. The maximum supported size is LIMBS = 12.
References:
-
Paulo S. L. M. Barreto, Michael Naehrig: "Pairing-Friendly Elliptic Curves of Prime Order." In: Preneel, B., Tavares, S. (eds). Selected Areas in Cryptography -- SAC 2005. Lecture Notes in Computer Science, vol. 3897, pp. 319--331. Springer, Berlin, Heidelberg. 2005. https://doi.org/10.1007/11693383_22
-
Geovandro C. C. F. Pereira, Marcos A. Simplicio Jr., Michael Naehrig, Paulo S. L. M. Barreto: "A Family of Implementation-Friendly BN Elliptic Curves." Journal of Systems and Software, vol. 84, no. 8, pp. 1319--1326. Elsevier, 2011. https://doi.org/10.1016/j.jss.2011.03.083