Skip to Main content Skip to Navigation

A short-list of pairing-friendly curves resistant to Special TNFS at the 128-bit security level

Aurore Guillevic 1
1 CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : There have been notable improvements in discrete logarithm computations in finite fields since 2015 and the introduction of the Tower Number Field Sieve (TNFS) algorithm for extension fields. The Special TNFS is very efficient in finite fields that are target groups of pairings on elliptic curves, where the characteristic is special (e.g. sparse). The key sizes for pairings should be increased, and alternative pairing-friendly curves can be considered. We revisit the Special variant of TNFS for pairing-friendly curves. In this case the characteristic is given by a polynomial of moderate degree (between 4 and 38) and tiny coefficients, evaluated at an integer (a seed). We present a polynomial selection with a new practical trade-off between degree and coefficient size. As a consequence, the security of curves computed by Barbulescu, El Mrabet and Ghammam should be revised: we obtain a smaller estimated cost of STNFS for all curves except BLS12 and BN. To obtain TNFS-secure curves, we reconsider the Brezing-Weng generic construction of families of pairing-friendly curves and estimate the cost of our new Special TNFS algorithm for these curves. This improves on the work of Fotiadis and Konstantinou, Fotiadis and Martindale, and Barbulescu, El Mrabet and Ghammam. We obtain a shortlist of interesting families of curves that are resistant to the Special TNFS algorithm, of embedding degrees 10 to 16 for the 128-bit security level. We conclude that at the 128-bit security level, a BLS-12 curve over a 440 to 448-bit prime seems to be the best choice for pairing efficiency. We also give a brief overview of the 192-bit security level.
Complete list of metadatas

Cited literature [39 references]  Display  Hide  Download

https://hal.inria.fr/hal-02396352
Contributor : Aurore Guillevic <>
Submitted on : Thursday, December 5, 2019 - 11:17:11 PM
Last modification on : Friday, February 7, 2020 - 1:43:36 AM
Document(s) archivé(s) le : Friday, March 6, 2020 - 7:37:56 PM

File

Curves_128_STNFS_05122019.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02396352, version 1

Citation

Aurore Guillevic. A short-list of pairing-friendly curves resistant to Special TNFS at the 128-bit security level. 2019. ⟨hal-02396352v1⟩

Share

Metrics

Record views

47

Files downloads

106