bls24-curves

This crate implements elliptic curve arithmetic and bilinear pairings for Barreto-Lynn-Scott curves containing a (large) prime-order torsion of embedding degree 24 (hence, BLS24 curves).

A BLS24 curve is specified by an integer parameter u ∈ ℤ with u ≡ 1 (mod 3) such that the values r ≔ u⁸ - u⁴ + 1 and p ≔ ((u - 1)²/3)r + u are prime, defining finite fields F_r and F_p. The curve equation is E/F_p : Y²Z = X³ + bZ³, whose number of F_p-rational points is #E(F_p) = cr with c ≔ (u - 1)²/3 being the so-called cofactor of the r-torsion. The quadratic twist of the curve is E'/F_p⁴ : Y'²Z' = X'³ + b'Z'³, whose number of F_p⁴ -rational points is #E'(F_p⁴) = h'r, where h' is called the cofactor of the r-torsion on the curve twist. Parameter u is also the order of the optimal pairing for BLS24 curves.

This implementation focuses on curves with u ≡ 16 (mod 72), which constitute one of the four Costello-Lauter-Naehrig families of particularly attractive BLS24 curves. This enables specifying the tower-friendly extension fields F_p² ≃ F_p[i]/<i² + 1>, F_p⁴ ≃ F_p² [v]/<v² + ξ> with ξ ≔ 1 + i, and F_p²⁴ ≃ F_p⁴ [z]/<z⁶ + v> (notice the signs of ξ and v).

This family also tends to be KZG-friendly, in the sense that the curve order r has high 2-adicity (that is, 2ᵐ | r - 1 for some fairly large m>) by just requiring u itself to be a multiple of a suitably high power of 2. The equations of the curve and its twist take simple, uniform shapes, with b = 4 and b' = 4v. For simplicity and efficiency, only positive, sparse (trinomial, tetranomial, and pentanomial) u parameters are currently supported.

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, Ben Lynn, Michael Scott: "Constructing Elliptic Curves with Prescribed Embedding Degrees." In: Cimato, S., Persiano, G., Galdi, C. (eds). Security in Communication Networks -- SCN 2002. Lecture Notes in Computer Science, vol. 2576, pp. 257--267. Springer, Berlin, Heidelberg. 2003. https://doi.org/10.1007/3-540-36413-7_19

• Craig Costello, Kristin Lauter, Michael Naehrig: "Attractive Subfamilies of BLS Curves for Implementing High-Security Pairings." In: Bernstein, D.J., Chatterjee, S. (eds) Progress in Cryptology -- INDOCRYPT 2011. Lecture Notes in Computer Science, vol 7107, pp. 320--342. Springer, Berlin, Heidelberg, 2011. https://doi.org/10.1007/978-3-642-25578-6_23