International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Takuya Hayashi
Naoyuki Shinohara
Lihua Wang
Shin'ichiro Matsuo
Masaaki Shirase
Tsuyoshi Takagi
Download:
URL: http://eprint.iacr.org/2010/090
Search ePrint
Search Google
Abstract: Pairings on elliptic curves over finite fields are crucial for constructing various cryptographic schemes. The \eta_T pairing on supersingular curves over GF(3^n) is particularly popular since it is efficiently implementable. Taking into account the Menezes-Okamoto-Vanstone (MOV) attack, the discrete logarithm problem (DLP) in GF(3^{6n}) becomes a concern for the security of cryptosystems using \eta_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 fulfilled such an implementation and we successfully set a new record for solving the DLP in GF(3^{6n}), the DLP in GF(3^{6 \cdot 71}) of 676-bit size. In addition, we also compared 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.
BibTeX
@misc{eprint-2010-22991,
  title={Solving a 676-bit Discrete Logarithm Problem in $GF(3^{6n})$},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / function field sieve, discrete logarithm problem, pairing-based cryptosystems},
  url={http://eprint.iacr.org/2010/090},
  note={This is a full version of PKC 2010 paper. takagi@fun.ac.jp 14659 received 19 Feb 2010, last revised 19 Feb 2010},
  author={Takuya Hayashi and Naoyuki Shinohara and Lihua Wang and Shin'ichiro Matsuo and Masaaki Shirase and Tsuyoshi Takagi},
  year=2010
}