Pairings on elliptic curves are involved in signatures, NIZK, and

recently in blockchains (ZK-SNARKS).

These pairings take as input two points on an elliptic curve E over a

finite field, and output a value in an extension of that finite field.

Usually for efficiency reasons, this extension degree is a power of 2

and 3 (such as 12,18,24), and moreover the characteristic of the finite

field has a special form. The security relies on the hardness of

computing discrete logarithms in the group of points of the curve and in

the finite field extension.

In 2013-2016, new variants of the function field sieve and the number

field sieve algorithms turned out to be faster in certain finite fields

related to pairing-based cryptography. Now small characteristic settings

(with GF(2^(4*n)), GF(3^(6*m))) are discarded, and the situation of

GF(p^k) where p is prime and k is small (in practice from 2 to 54) is

unclear.

The asymptotic complexity of the Number Field Sieve algorithm in finite

fields GF(p^k) (where p is prime) and its Special and Tower variants is

given by an asymptotic formula of the form A^(c+o(1)) where A depends on

the finite field size (log p^k), o(1) is unknown, and c is a constant

between 1.526 and 2.201 that depends on p, k, and the choice of

parameters in the algorithm.

In this work we improve the approaches of Menezes-Sarkar-Singh and

Barbulescu-Duquesne to estimate the cost of a hypothetical

implementation of the Special-Tower-NFS in GF(p^k) for small k (k <=

24), and update some parameter sizes for pairing-based cryptography.

This is a joint work with Shashank Singh, IISER Bhopal, India.