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

Takuya Hayashi; Naoyuki Shinohara; Lihua Wang; Shin'ichiro Matsuo; Masaaki Shirase; Tsuyoshi Takagi

Paper 2010/090 Original: eprint.iacr.org/2010/090 ↗

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

Takuya Hayashi

Naoyuki Shinohara

Lihua Wang

Shin'ichiro Matsuo

Masaaki Shirase

Tsuyoshi Takagi

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
History: 2010-02-22: last updated; 2010-02-22: published
Short URL: https://ia.cr/2010/090
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2010/090,
      author = {Takuya Hayashi and Naoyuki Shinohara and Lihua Wang and Shin'ichiro Matsuo and Masaaki Shirase and Tsuyoshi Takagi},
      title = {Solving a 676-bit Discrete Logarithm Problem in GF(3^{6n})},
      howpublished = {Cryptology {ePrint} Archive, Paper 2010/090},
      year = {2010},
      url = {https://eprint.iacr.org/2010/090}
}