Antoine Joux: A Simplified Setting for Discrete Logarithms in Small Characteristics Finite Fields
Date: Tuesday, April 07, 2015
Time: 4:15 PM to 5:15 PM Note: all times are in the Eastern Time Zone
Refreshments: 4:00 PM
Location: G449 Patil/Kiva
Host: Costis Daskalakis, Ankur Moitra, Dana Moshkovitz and Vinod Vaikuntanathan
Contact: Deborah Lehto, 617.324.7303, firstname.lastname@example.org
Speaker URL: None
email@example.com, firstname.lastname@example.org, email@example.com
TALK: Antoine Joux: A Simplified Setting for Discrete Logarithms in Small Characteristics Fin
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.
Created by Deborah Goodwin at Tuesday, March 10, 2015 at 3:27 PM.