bn-curves

This crate implements elliptic curve arithmetic and bilinear pairings for Barreto-Naehrig (BN) curves. It was 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 F_p.

The additional constraint p ≡ 3 (mod 4) is typical, since it enables specifying the quadratic extension F_p² = F_p[i]/<i² + 1> and the tower-friendly extension fields F_p⁴ ≃ F_p²[σ]/<σ² - ξ>, F_p⁶ ≃ F_p²[τ]/<τ³ - ξ>, and F_p¹² ≃ F_p²[z]/<z⁶ - ξ>, where ξ = 1 + i.

The BN curve equation is E/F_p : Y²Z = X³ + bZ³, whose number of points is n ≔ #E(F_p) = 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. Incidentally, the curve order satisfies n ≡ 5 (mod 8).

The default quadratic twist of the curve is E'/F_p² : Y'²Z' = X'³ + b'Z'³ with b' ≔ b/ξ, whose number of points is n' ≔ #E'(F_p²) = 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/F_p is the point G ≔ [-1 : 1 : 1], and a suitable generator of n-torsion on E'/F_p² is the point G' ≔ [h']G₀' where G₀' ≔ [-i : 1 : 1]. The maximum supported size is LIMBS = 12.

All feasible care has been taken to make sure the arithmetic algorithms adopted in this crate are isochronous ("constant-time") and efficient. Yet, the no-warranty clause of the MIT license is in full force for this whole crate.

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