Antoine Joux: A Simplified Setting for Discrete Logarithms in Small Characteristics Finite Fields

Speaker: Antoine Joux

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

Public: Yes

Location: G449 Patil/Kiva

Event Type:

Room Description:

Host: Costis Daskalakis, Ankur Moitra, Dana Moshkovitz and Vinod Vaikuntanathan

Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: cis-seminars@csail.mit.edu, theory-seminars@csail.mit.edu, seminars@csail.mit.edu

Reminder Subject: TALK: Antoine Joux: A Simplified Setting for Discrete Logarithms in Small Characteristics Fin

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.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation (TOC) Seminar Series 2015.

Created by Deborah Goodwin at Tuesday, March 10, 2015 at 3:27 PM.