Solving a 676-Bit Discrete Logarithm Problem in GF(36n)
-
- HAYASHI Takuya
- Graduate School of Mathematics, Kyushu University
-
- SHINOHARA Naoyuki
- Network Security Research Institute, National Institute of Information and Communications Technology
-
- WANG Lihua
- Network Security Research Institute, National Institute of Information and Communications Technology
-
- MATSUO Shin'ichiro
- Network Security Research Institute, National Institute of Information and Communications Technology
-
- SHIRASE Masaaki
- School of Systems Information Science, Future University-Hakodate
-
- TAKAGI Tsuyoshi
- Institute of Mathematics for Industry, Kyushu University
Search this article
Abstract
Pairings on elliptic curves over finite fields are crucial for constructing various cryptographic schemes. The ηT pairing on supersingular curves over GF(3n) is particularly popular since it is efficiently implementable. Taking into account the Menezes-Okamoto-Vanstone attack, the discrete logarithm problem (DLP) in GF(36n) 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(36n). Therefore, we first fulfill such an implementation and we successfully set a new record for solving the DLP in GF(36n), the DLP in GF(36·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.
Journal
-
- IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
-
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E95-A (1), 204-212, 2012
The Institute of Electronics, Information and Communication Engineers
- Tweet
Details 詳細情報について
-
- CRID
- 1390001206310854144
-
- NII Article ID
- 10030534822
-
- NII Book ID
- AA10826239
-
- ISSN
- 17451337
- 09168508
-
- Text Lang
- en
-
- Data Source
-
- JaLC
- Crossref
- CiNii Articles
- KAKEN
-
- Abstract License Flag
- Disallowed