3 octobre 2016, Aurore Guillevic: Key-size updates for pairing-friendly elliptic curves

The building-bloc function in bilinear pairing-based cryptography is a Weil or Tate pairing over an elliptic (or hyperelliptic) curve, defined over a finite field, and of small embedding degree. The security relies on the hardness of a discrete logarithm computation in an elliptic curve and in a finite field: the target group of a cryptographic bilinear pairing is a finite field GF(p^n) where usually the embedding degree n is small: 1 ≤= n ≤= 24 and most of the time, n=12. (Small characteristic finite fields are now avoided: there exists a quasi-polynomial-time algorithm to compute DL). Until 2014 is was assumed that computing a discrete logarithm in a large characteristic field GF(p^n) was at least as hard as in a prime field GF(q) where log q = log p^n (i.e. of same total size). This is not true anymore: the Number Field Sieve algorithm now has better variants for such finite fields. To obtain the same security, finite fields should be enlarged. The asymptotic complexity of the NFS algorithm is not tight enough to obtain tight intervals for key-sizes according to a given security level. We propose to study the ingredient in NFS that determines the complexity: the size of the elements involved in the relation collection. Graphs of these sizes will be presented for 2 ≤ n ≤ 12, with quite interesting results in some cases. The norms were computed experimentally.

Comments are closed.