Date de l'exposé : 01 mars 2019
Discrete logarithm computation in finite fields GF(p^k) with NFSvariants and consequences in pairing-based cryptography
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.
