Discrete Logarithms in Small Characteristic Finite Fields: a Survey of Recent Advances (Invited Talk)

Author Antoine Joux



PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.3.pdf
  • Filesize: 233 kB
  • 1 pages

Document Identifiers

Author Details

Antoine Joux

Cite AsGet BibTex

Antoine Joux. Discrete Logarithms in Small Characteristic Finite Fields: a Survey of Recent Advances (Invited Talk). In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.STACS.2017.3

Abstract

The discrete logarithm problem is one of the few hard problems on which public-key cryptography can be based. It was introduced in the field by the famous Diffie-Hellman key exchange protocol. Initially, the cryptographic use of the problem was considered in prime fields, but was readily generalized to arbitrary finite fields and, later, to elliptic or higher genus curves. In this talk, we survey the key technical ideas that can be used to compute discrete logarithms, especially in the case of small characteristic finite fields. These ideas stem from about 40 years of research on the topic. They appeared along the long road that leads from the initial belief that this problem was hard enough for cryptographic purpose to the current state of the art where it can no longer be considered for cryptographic use. Indeed, after the recent developments started in 2012, we now have some very efficient practical algorithms to solve this problem. Unfortunately, these algorithms remain heuristic and one important direction for future research is to lift the remaining heuristic assumptions.
Keywords
  • Cryptography
  • Discrete logarithms
  • Finite fields

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail