Pairing-friendly curves

In August 2020 at the virtual CRYPTO conference, during Friday session Cryptanalysis 2, there was a live discussion on the security of pairing-friendly curves, and which ones are the best at the 128-bit security level (asked by F. Vercauteren). This page is an answer summary.

This question is also discussed in an IETF draft mentioned by Hoeteck Wee on the IACR chat.

First online: September 10, 2020,
Last updated: February 22, 2021.

Pairing-friendly curves at the 128-bit security level

Broadly speaking, there are two sets of keysizes at the 128-bit security level: non-conservative choices and conservative choices. They depend on the choices when estimating the cost of computing a discrete logarithm in Fpk with the new variants of the Number Field Sieve (NFS) algorithm.

For efficient non-conservative pairings, choose BLS12-381 (or any other BLS12 curve or Fotiadis–Martindale curve of roughly 384 bits), for conservative but still efficient, choose a BLS12 or a Fotiadis–Martindale curve of 440 to 448 bits.

the security between BLS12-446 and BLS12-461 is not worth paying an extra machine word, and is close to the error margin of the security estimate.

Curve k D u ref p (bits) r (bits) pk/d (G2, bits) pk (bits)
Curve for fastest pairing
Barreto–Lynn–Scott BLS12, cyclotomic r(x) 12 3 -(273+272+250+224) eprint 2017/334 440 295 p2, 880 5280
Barreto–Lynn–Scott BLS12, cyclotomic r(x) 12 3 -(212-248-271+274) eprint 2017/334 442 296 p2, 884 5296
Barreto–Lynn–Scott BLS12, cyclotomic r(x) 12 3 -(274+273+263+257+250+217+1) eprint 2019/885 446 299 p2, 892 5352
Fotiadis–Martindale FM17, Aurifeuillean r(x) 12 3 -272-271-236 eprint 2019/555 447 296 p2, 894 5356
Kachisa–Schaefer–Scott KSS16 16 1 -234+227-223+220-211+1 eprint 2017/334 330 257 p4, 1320 5280
Kachisa–Schaefer–Scott KSS16 16 1 234-230+226+223+214-25+1 eprint 2019/1371 330 256 p4, 1320 5268
Kachisa–Schaefer–Scott KSS16 16 1 235-232-218+28+1 eprint 2017/334 339 263 p4, 1356 5411
Curve with small embedding degree k
Cocks–Pinch modified 6 3 2128-2124-269, ht=-1, hy=280-270-266–0x3fe0=0xffbbffffffffffffc020 eprint 2019/431 672 256 p, 672 4028
Cocks–Pinch modified 8 1 264-254+237+232-4, ht=1, hy=0xdc04 eprint 2019/431 544 256 p2, 1088 4349
Curve with smallest G1
Freeman–Scott–Teske 6.6 BW13-P310, cyclotomic r(x) 13 3 0x8b0 eprint 2020/760 310 267 p13, 4030 4027
Freeman–Scott–Teske 6.6 BW19-P286, cyclotomic r(x) 19 3 -0x91 eprint 2020/760 286 259 p19, 5434 5427
Barreto–Lynn–Scott BLS24, cyclotomic r(x) 24 3 -232+228-223+221+218+212-1 eprint 2019/885 318 256 p4, 1272 7621
Barreto–Lynn–Scott BLS24, cyclotomic r(x) 24 3 -232+228+212 eprint 2019/485 318 256 p4, 1272 7632
Barreto–Lynn–Scott BLS48, cyclotomic r(x) 48 3 0xf5ef MIRACL 286 256 p8, 2288 13698
Scott–Guillevic KSS54, Aurifeuillean r(x) 54 3 -0x2886 Mike Scott, personal communication 283 255 p9, 2547 15264
Other popular curve
Barreto–Naehrig BN, Aurifeuillean r(x) 12 3 2110+236+1 eprint 2010/429 446 446 p2, 892 5343

Some of the parameters can be found in the Python file testvector_sparseseed.py

Some of the parameters of Cocks-Pinch curves can be found in the Python file example_cocks_pinch_nfs.py

More info

BLS12-381

Challenges with Assessing the Impact of NFS Advances on the Security of Pairing-based Cryptography by Menezes, Sarkar and Singh, published at Mycrypt 2016 conference, LNCS 10311, pp. 83–108, (DOI 10.1007/978-3-319-61273-7_5, eprint 2016/1102) is the first paper to analyze thoroughly the consequences of TNFS, STNFS and their variants to target groups of pairing-friendly curves. The conclusion recommends BLS12 or BN curves over 384-bit prime fields instead of BN curves over 256-bit fields. Based on this work, the curve BLS12-381 was chosen by ZCash. This curve is now widely deployed.

BLS12-461, BN-462

In 2017 (published in 2019), Barbulescu and Duquesne wrote Updating key size estimations for pairings, Journal of Cryptology, vol. 32, pp. 1298–1336, DOI 10.1007/s00145-018-9280-5, eprint 2017/334. They advised the following curves:

  • a BLS-12 curve over a 461-bit field;
  • a BN curve over a 462-bit field;
  • a KSS16 curve over a 330-bit field and another over a 339-bit field;
  • a KSS18 curve over a 348-bit field.

Their contribution is a refined model of cost compared to the previous work of Menezes, Sarkar and Singh.

BLS12-446, Fotiadis–Martindale, Cocks–Pinch, Brezing–Weng

I wrote the paper A short list of pairing-friendly curves at the 128-bit security level presented at PKC2020 and eprint 2019/1371. A SageMath version (for easy copy-paste) is available on gitlab, this is project tnfs-alpha/alpha Then under sage, the file example_curves_short_list.sage contains this short list.

For each embedding degree from 9 to 17, the best option is selected. The final result is Table 6 page 20 reproduced below.

Curve k D u ref p (bits) r (bits) pk/d (G2, bits) pk (bits)
Cocks–Pinch modified 6 3 2128-2124-269, ht=xx, hy=0xXX eprint 2019/431 672 256 p, 672 4028
Cocks–Pinch modified 8 1 264-254+237+232-4, ht=1, hy=0xdc04 eprint 2019/431 544 256 p2, 1088 4349
Brezing–Weng, cyclotomic r(x) (FM15) 10 15 232-226-217+210-1 eprint 2019/1371 446 256 p5, 2230 4458
Brezing–Weng, cyclotomic r(x) 11 3 -0x1d2a eprint 2019/1371 333 258 p11, 3663 3663
Brezing–Weng, cyclotomic r(x) 11 11 -226+221+219-211-29-1 eprint 2019/1371 412 256 p11, 4532 4528
Barreto–Naehrig BN, Aurifeuillean r(x) 12 3 2110+236+1 eprint 2010/429 446 446 p2, 892 5343
Barreto–Lynn–Scott BLS12, cyclotomic r(x) 12 3 -(274+273+263+257+250+217+1) eprint 2019/885 446 299 p2, 892 5352
Fotiadis–Martindale FM17, Aurifeuillean r(x) 12 3 -272-271-236 eprint 2019/555 447 296 p2, 894 5356
Freeman–Scott–Teske 6.6 BW13-P310, cyclotomic r(x) 13 3 0x8b0 eprint 2020/760 310 267 p13, 4030 4027
Freeman–Scott–Teske 6.6, cyclotomic r(x) 14 3 0x2803c0 eprint 2019/1371 340 256 p7, 2380 4755
Kachisa–Schaefer–Scott KSS16 16 1 -234+227-223+220-211+1 eprint 2017/334 330 257 p4, 1320 5280
Kachisa–Schaefer–Scott KSS16 16 1 234-230+226+223+214-25+1 eprint 2019/1371 330 256 p4, 1320 5268

Implementing pairings on curves of embedding degrees 9 to 27 (in particular, prime degrees)

  • Enge, A., Milan, J.: Implementing cryptographic pairings at standard security levels. In: Chakraborty, R.S., Matyas, V., Schaumont, P. (eds.) Security, Privacy, and Applied Cryptography Engineering — 4th International Conference, SPACE 2014, Pune, India, October 18-22, 2014. Proceedings. LNCS, vol. 8804, pp. 28–46. Springer (2014). DOI 10.1007/978-3-319-12060-7_3, arxiv 1407.5953, HAL hal-01034213.

This paper implements and compares pairings with embedding degrees between 9 and 27, in particular it presents a Miller loop compatible with 2-NAF form and a prime embedding degree (such as 11, 17, 19). The paper made parameters choices in 2014, before the TNFS algorithm was published, the sizes would need to be increased. It compares the pairing efficiency on curves of embedding degrees 9 to 27, in particular it offers a valuable comparison between prime and composite embedding degrees.

Cocks–Pinch modified

with Simon Masson and Emmanuel Thomé we investigated variants of Cocks–Pinch in this paper: Cocks–Pinch curves of embedding degrees five to eight and optimal ate pairing computation, Designs, Codes and Cryptography, vol. 88 pp. 1047–1081 DOI 10.1007/s10623-020-00727-w, eprint 2019/431.

Fotiadis–Martindale

There is also a family of curves introduced by Fotiadis and Martindale: eprint 2019/555. These curves have similar properties as BLS12 curves and have the same security. See also TNFS Resistant Families of Pairing-Friendly Elliptic Curves, Georgios Fotiadis and Elisavet Konstantinou, Journal of Theoretical Computer Science, vol. 800, pp. 73–89, 2019, DOI 10.1016/j.tcs.2019.10.017, eprint 2018/1017.

Clarisse–Duquesne–Sanders

Rémi Clarisse et al. investigated smallest possible G1 in – Curves with Fast Computations in the First Pairing Group, Rémi Clarisse, Sylvain Duquesne, and Olivier Sanders, CANS 2020, LNCS 12579, pages 280–298, DOI 10.1007/978-3-030-65411-5_14, eprint 2020/760.

They obtained the curve BW19-P286, a Brezing–Weng curve of embedding degree 19 defined over a 286-bit prime field. This is the record in terms of smallest possible G1 and is well-suited for 32-bit architecture.

BLS24-318

On a Github discussion page here, BLS-24 curves are discussed, because they provide very small G1 (in other words, a very small p provides a fast arithmetic in G1).

In this paper with Singh we estimated the security of another BLS24-318 curve to be 162 bits in Fpk. The security on the curve is 128 bits with r of 256 bits. – On the alpha value of polynomials in the tower number field sieve algorithm, Aurore Guillevic and Shashank Singh, Mathematical Cryptology, vol 1 no 1, eprint 2019/885

In testvector_sparseseed.py there are other seeds so that r has 250 to 257 bits, and r-1 and p-1 have a high 2-valuation, of 18 to 20.

BLS48-286, KSS54-283

Mike Scott investigated shortest G1 with high embedding degree k, and degree 6 twist. The curve BLS48-286 is implemented in MIRACL. He also suggested to compare the performances to a KSS54 curve with p of 283 bits and r of 255 bits obtained with u=-0x2886.

BLS12-381, BLS12-461, or BLS12-446?

In Barbulescu–Duquesne paper Updating key size estimations for pairings, Journal of Cryptology, vol. 32, pp. 1298–1336, DOI 10.1007/s00145-018-9280-5, eprint 2017/334, there is a remark (2 page 18) saying that a BLS12-442 only has 127 bits of security. I guess this is because of this remark that cryptographers are not promoting BLS12 with 7 machine-words (448 bits) but prefer 461 bits as in the IETF draft mentioned by Hoeteck Wee on the IACR chat.

Barbulescu–Duquesne remark is below:

Remark 2.
Zhaohui Cheng communicated to us two choices of BLS12 curses which have 127 bits of security:

  • equation y2=x3+9 and parameter u=-(273+272+250+224);
  • equation y2=x3+7 and parameter u=-(212-248-271+274).

The field pk is 5280 bits long instead of the 5530 bits required by the general estimations in Table 7. Hence, our approach of first finding general recommendations for each family (assuming the attacker can apply all improvements), then checking specific values of u, only loses 5% in length.

For efficient modular arithmetic, finite fields elements (integers modulo p, also denoted Z/pZ) are represented in Montgomery form, and all the bits of the machine-words are filled. It means elements of Fp where p is 385 to 448-bit long are stored in the full 448 bits. And elements of Fp where p is 449 to 512-bit long are stored in 512 bits. From 7 machine words (BLS12-446) to 8 machine words (BLS12-461), the length in Montgomery form is increased by 14% (8/7*100), not 5%. Because the timings of modular multiplications are quadratic in the machine-word size of the modular integers, the slowdown in time could be up to 30%. 2019/431 reports a slowdown of 25% for modular multiplication from 7 machine-words to 8 machine-words when benchmarking RELIC.

With the improved estimation implemented with Shashank Singh, we obtained that such BLS12 curves of 440 to 448 bits have roughly a security of 132 bits, these results are given in Section 7.2, in Table 7, and Appendix C of the paper On the alpha value of polynomials in the tower number field sieve algorithm (eprint 2019/885). The security of BLS12-461 is estimated to be between 134 and 135 bits.

In short, the security between BLS12-446 and BLS12-461 is not worth paying an extra machine word, and is close to the error margin of the security estimate.

About eprint 2019/485

The preprint 2019/485 by Barbulescu, El Mrabet and Ghammam was posted on eprint on May 13, 2019. It lists curves mostly from Freeman, Scott and Teske paper A taxonomy of pairing-friendly elliptic curves, Journal of Cryptology vol. 23, pp. 224–280, 2010, DOI 10.1007/s00145-009-9048-z, eprint 2006/372. I contacted the authors of eprint 2019/485 on August 20, 2019 because our respective results did not match on many curves. The preprint was updated on September 13, 2020. Comments are on a separate page.

In July 3-6, 2020 at ITC-CSCC 2020, Nagoya (Online Conference), these curves were implemented and compared. It turned out that they are slower (than BLS12 for example), because fewer optimisations are available (in particular, a quadratic twist only for k=10 and k=14, a cubic twist for k=15, instead of a sextic twist for BN, BLS12, Fotiadis–Martindale k=12 curves results in a slower pairing).

Curve k D u ref p (bits) r (bits) pk (bits)
Brezing–Weng, cyclotomic r(x) 10 2 236+230+212+26+1 1 503 289 5024
Brezing–Weng, cyclotomic r(x) 14 2 221+213+211+210+29+1 2 377 253 5267
BLS15 Barreto–Lynn–Scott, cyclotomic r(x) 15 3 -232-222+217+26, -232-220-214-23 3, 4 383 257 5737
  • a k=10, D=1 Brezing–Weng curve in R. Matsumura, Y. Takahashi, Y. Nanjo, T. Kusaka and Y. Nogami, Implementation and Evaluation of Ate Pairings on Elliptic Curves with Embedding Degree 10 Applied Type-II All-One Polynomial Extension Field of Degree 5, ITC-CSCC, Nagoya, Japan, July 3-6, 2020, pp. 336–341, online paper 1. The parameters are p(x) = (x14 – 2 x12 + x10 + x4 + 2 x2 + 1)/4, r(x) = x8 – x6 + x4 – x2 + 1, t(x) = x2 + 1, c(x) = (x4 – 1)(x2 – 1)/4, y(x) = (x-1)(x+1)x5, and seed u=236 + 230 + 212 + 26 + 1 gives a 503-bit prime p and a 289-bit prime r.
  • a k=14, D=1 Brezing–Weng curve in An Implementation and Evaluation of a Pairing on Elliptic Curves with Embedding Degree 14, Song, Matsumura, Takahashi, Nanjo, Kusaka, Nogami, Matsumoto, ITC-CSCC 2020, Nagoya, Japan, July 3-6, 2020, pp. 293–298, online paper 2. The parameters are p(x)=(x18 – 2 x16 + x14 + x4 + 2 x2 + 1)/4, r(x)=x12 – x10 + x8 – x6 + x4 – x2 + 1, t(x)=x2 + 1, curve cofactor is c(x)=(x4 – 1)(x2 – 1)/4, y(x)=(x – 1)(x + 1)x7, and seed u=221 + 213 + 211 + 210 + 29 + 1 gives a 377-bit prime p and a 253-bit prime r.
  • a k=15, D=3 BLS curve in Y. Nanjo, M. Shirase, T. Kusaka and Y. Nogami, An Explicit Formula of Cyclotomic Cubing Available for Pairings on Elliptic Curves with Embedding Degrees of Multiple of Three, ITC-CSCC, Nagoya, Japan, July 3-6, 2020, pp. 288–292, online paper 3. Y. Nanjo, M. Shirase, T. Kusaka and Y. Nogami, A Technique for Fast Miller’s Algorithm of Ate Pairings on Elliptic Curves with Embedding Degrees of Multiple of Three, ITC-CSCC, Nagoya, Japan, July 3-6, 2020, pp. 283–287, online paper 4. The parameters are p(x) = (x – 1)2/3(x2 + x + 1)r(x) + x, r(x) = x8 – x7 + x5 – x4 + x3 – x + 1, t(x) = x + 1, c(x) = (x – 1)(x3 – 1)/3, y(x) = (x – 1)(2 x5 + 1)/3, and seeds u= – 232 – 222 + 217 + 26 and u= – 232 – 220 – 214 – 23 give 383-bit prime p and 257-bit prime r.

Pairing-friendly curves for zk-SNARKs

In the zero-knowledge community, there are other needs (cycles of MNT curves, chains of curves, parameters p-1 and r-1 with a high 2-valuation…) A cycle of curves (available only with MNT curves for now) is a pair of pairing-friendly elliptic curves E1, E2 such that E1 is defined over a finite prime field Fp and has prime order r, and E2 is defined over the finite field Fr (where r is E1 order) and has order p.

BLS12 and BLS24 curves

Curve k D u ref p (bits) r (bits) pk/d (G2, bits) pk (bits)
Popular BLS12-381 curve
Barreto–Lynn–Scott BLS12, cyclotomic r(x) 12 3 -0xd201000000010000=-263-262-260-257-248-216 ZCash 381 255 p2, 762 4569
Curves with 2n|p-1, 2m|r-1
Barreto–Lynn–Scott BLS12, cyclotomic r(x) 12 3 0x8508c00000000001=263+258+256+251+247+246+1 Zexe, eprint 2018/962, Table 16 377 253 p2, 754 4521
Barreto–Lynn–Scott BLS12, cyclotomic r(x) 12 3 0x9b04000000000001=263+261-258-256+250+1 testvector_sparseseed.py 379 254 p2, 758 4537
Barreto–Lynn–Scott BLS12, cyclotomic r(x) 12 3 0x105a8000000000001=264+259-257-255+253+251+1 testvector_sparseseed.py 383 257 p2, 766 4592
Barreto–Lynn–Scott BLS24, cyclotomic r(x) 24 3 -0xbfcfffff=-232+230+222-220+1 testvector_sparseseed.py 315 253 p4, 1260 7543

MNT curves

Two cycles of elliptic curves are widely deployed: 298-bit parameters and 753-bit parameters (see DOI 10.1007/978-3-662-44381-1_16, eprint 2014/595). I generated other parameters (with the algorithms from Karabina–Teske, eprint 2007/425, DOI 10.1007/978-3-540-79456-1_6) to have an idea of the security for larger parameters, there are at tnfs/param/TestVectorMNT_k_cycle_D_1e9.py. But the curves are not optimized for zk-SNARKs, the valuation at 2 of p-1 and r-1 is low.

Curve k D ref p (bits) r (bits) pk (bits) estimated security
MNT4-298 4 614144978799019 eprint 2014/595 298 298 1192 277
MNT6-298 6 614144978799019 eprint 2014/595 298 298 1788 287
MNT4-753 4 241873351932854907 eprint 2014/595, CODA 753 753 3012 2113
MNT6-753 6 241873351932854907 eprint 2014/595, CODA 753 753 4517 2137
MNT4-992 4 95718723 gitlab file 992 992 3966 2126
MNT6-992 6 95718723 gitlab file 992 992 5948 2156

The seeds are the following.

Curve seed
MNT4-298 u = 0x1eef5546609756bec2a33f0dc9a1b671660000
MNT6-298 u = -0xf77aaa3304bab5f61519f86e4d0db38b30000
MNT4-753 u = -0x15474b1d641a3fd86dcbcee5dcda7fe51852c8cbe26e600733b714aa43c31a66b0344c4e2c428b07a7713041ba18000
MNT6-753 u = 0xaa3a58eb20d1fec36e5e772ee6d3ff28c296465f137300399db8a5521e18d33581a262716214583d3b89820dd0c000
MNT4-992 u = 0xc85f1924b404f160077c049739e871907e407900a6d59abd8e25f63eaec03b9f974bfa92dd5cc38cb09ffdcdd3d19ab23bad8e228130bedd0e0859c32774
MNT6-992 u = -0x642f8c925a0278b003be024b9cf438c83f203c80536acd5ec712fb1f57601dcfcba5fd496eae61c6584ffee6e9e8cd591dd6c71140985f6e87042ce193ba

For a 128-bit security level, an example of cycle for comparison (in terms of length) is the following. Roughly 1024-bit parameters provide a 128-bit security level. For the curve MNT4-992 the estimated cost of NFS-Conjugation is 2126 in Fp4 and for MNT6-992 the estimated cost of STNFS is 2156 in Fp6.

# MNT4_992
k = 4
u = 0xc85f1924b404f160077c049739e871907e407900a6d59abd8e25f63eaec03b9f974bfa92dd5cc38cb09ffdcdd3d19ab23bad8e228130bedd0e0859c32774
D = 95718723
c = 1
a = -3
b = 0x1c517e4f1632c3879c949ad49791cd8d9a6fc4bba403a3e69053e909ecbd42dbafb80100e0e46c53e85a07d869637e75ca6c3371de1bb090517613b30782f01489562fe913cd858d6671ab2a9d7ceb5c3ce8ea426c577ebb16b3c87a501e4bef0df989d7ec1037f32e852df87dce54696805764e1a072268d650a1ea
pnbits = 992
rnbits = 992
p = u**2 + u + 1
r = u**2 + 1
t = u + 1
y = 0x914c26752f9ff10b6a9060342744c1971bd11ee0a5a9f3dbff85fd462a6807cdbe69fef2c1fc2731306a180a5490999b3e810db101c100f78eee893a3
assert t**2-4*p == -D*y**2
assert p+1-t == r*c
(p-1) % (2**2 * 3 * 5**5 * 13) == 0
(r-1) % (2**4 * 3**2 * 5**10) == 0
Fp = GF(p)
E4 = EllipticCurve([Fp(a),Fp(b)])

# MNT6_992
k = 6
u = -0x642f8c925a0278b003be024b9cf438c83f203c80536acd5ec712fb1f57601dcfcba5fd496eae61c6584ffee6e9e8cd591dd6c71140985f6e87042ce193ba
D = 95718723
c = 1
a = -3
b = 0xa0c214d66abeed117834b3812f966d30b7ce0cef1dc8aec978c8da94cbcf67a2d99c2c1428f9ffb86b280c13144154fb1be8a9e1f4fd886271c3816e25f623c01e344d24440dd2873f6b207862dab186fde6c075b5a0dccdcd86c7656865d75ca94f63a091cf6fc5d538342b81b871bda4b63fac1a9ed8b36ccd906
pnbits = 992
rnbits = 992
p = 4*u**2 + 1
r = 4*u**2 - 2*u + 1
t = 2*u + 1
y = 0x914c26752f9ff10b6a9060342744c1971bd11ee0a5a9f3dbff85fd462a6807cdbe69fef2c1fc2731306a180a5490999b3e810db101c100f78eee893a3
assert t**2-4*p == -D*y**2
assert p+1-t == r*c
(p-1) % (2^4 * 3^2 * 5^10) == 0
(r-1) % (2^2 * 3 * 5^5 * 13) == 0
Fp = GF(p)
E6 = EllipticCurve([Fp(a),Fp(b)])