You are looking at a specific version 20191206:143422 of this paper. See the latest version.

Paper 2019/1371

A short-list of STNFS-secure pairing-friendly curves at the 128-bit security level

Aurore Guillevic

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 short-list 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.

Note: Update Dec 6, 2019: added info about GLV scalar multiplication. Corrected typos.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
discrete logarithmfinite fieldnumber field sievepairing-friendly curve
Contact author(s)
aurore guillevic @ inria fr
History
2020-02-05: last of 2 revisions
2019-12-01: received
See all versions
Short URL
https://ia.cr/2019/1371
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.