Solving a 676-Bit Discrete Logarithm Problem in $GF(3^{6n})$

Abstract

Pairings on elliptic curves over finite fields are crucial for constructing various cryptographic schemes. The ηT pairing on supersingular curves over $GF(3^n)$ is particularly popular since it is efficiently implementable. Taking into account the Menezes-Okamoto-Vanstone attack, the discrete logarithm problem (DLP) in $GF(3^{6n})$ becomes a concern for the security of cryptosystems using ηT pairings in this case. In 2006, Joux and Lercier proposed a new variant of the function field sieve in the medium prime case, named JL06-FFS. We have, however, not yet found any practical implementations on JL06-FFS over $GF(3^{6n})$. Therefore, we first fulfill such an implementation and we successfully set a new record for solving the DLP in $GF(3^{6n})$, the DLP in GF(3^{6·71}) of 676-bit size. In addition, we also compare JL06-FFS and an earlier version, named JL02-FFS, with practical experiments. Our results confirm that the former is several times faster than the latter under certain conditions.