Next SSL Seminar will take place on Thursday, February 28th at 1.30 pm in room A008.

Aurore Guillevic (Caramba) will give a presentation entitled “Discrete logarithm computation in finite fields GF(p^k) with NFS variants and consequences in pairing-based cryptography.”

Abstract:
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.

More information about SSL Seminars