Function Field Sieve: Recent advances in the index-calculus attack on the discrete logarithm problem

Abstract

In this paper we look into the discrete log problem over finite fields. The relative hardness of this problem defines the integrity of many cryptographic systems. Therefore the ease of solvalbility of this problem has been important to cryptographer for a long time. We study the index calculus method. In prticular we focus on the function field sieve. This algorithm works well to find discrete log in the multiplicative group of finite fields Fqn with a medium or small sized subfield Fq. It has sub-exponential time complexity. We investigate various recent improvements done to this algorithm by Antoine Joux.