Joux, Antoine
Discrete Logarithms in Small Characteristic Finite Fields: a Survey of Recent Advances (Invited Talk)
Abstract
The discrete logarithm problem is one of the few hard problems on which publickey cryptography can be based. It was introduced in the field by the famous DiffieHellman 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.
BibTeX  Entry
@InProceedings{joux:LIPIcs:2017:7031,
author = {Antoine Joux},
title = {{Discrete Logarithms in Small Characteristic Finite Fields: a Survey of Recent Advances (Invited Talk)}},
booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
pages = {3:13:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770286},
ISSN = {18688969},
year = {2017},
volume = {66},
editor = {Heribert Vollmer and Brigitte Vallée},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7031},
URN = {urn:nbn:de:0030drops70313},
doi = {10.4230/LIPIcs.STACS.2017.3},
annote = {Keywords: Cryptography, Discrete logarithms, Finite fields}
}
2017
Keywords: 

Cryptography, Discrete logarithms, Finite fields 
Seminar: 

34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Issue date: 

2017 
Date of publication: 

2017 