CANCELLED - A simplified setting for discrete logarithms in small characteristic finite fields
Friday, November 21, 2014 - 10:30am to 12:00pm
Refreshments:
Light Refreshments
Location:
G449 (Patil/Kiva)
Speaker:
Antoine Joux, Cryptology Chair - Fondation Partenariale de l'UPMC
Abstract:
The hardness of computing discrete logarithms in finite field has
served as a foundation for many public key cryptosystems. In the last
two years, tremendous progress have been made in the case of small
characteristic finite fields.
In this talk, we present a simplified description of the algorithmic
framework that has been developed to solve this problem faster. This
framework is an index calculus approach that relies on two main
ingredients, the definition of the extension field and the generation
of multiplicative relations in this field. Given a base field GF(q),
we construct its extension field GF(q^k) in the following way: we
find two polynomials of low degree h0 and h1 with coefficients
in GF(q) such that x^q h1(x)-h0(x) has an irreducible factor of
degree k over GF(q).
To generate relations, we start from the well-known identity:
X^q-X=Prod_(c in GF(q)) X-c.
Combining substitution of X by a fraction in the identity with the field
definition, we easily obtain many multiplicative relations. This is enough
to obtain the logarithms of a factor base of small degree elements in
polynomial time.
Once this is done, we use a descent procedure to recursively express
any element of the finite field GF(q) into elements represented
by polynomials of lower degree. This procedure is quite complex but
ultimately leads to a quasi-polynomial time algorithm for the discrete
logarithm problem in small characteristic finite fields.