Solving a 676-bit Discrete Logarithm Problem in GF(36n)
Solving a 676-bit Discrete Logarithm Problem in GF(36n)
复制标题
求解 GF(36n) 中的 676 位离散对数问题
DOI：
10.1007/978-3-642-13013-7_21
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Tsuyoshi Takagi
中科院分区：
文献类型：
--
作者：
Takuya Hayashi;Naoyuki Shinohara;Lihua Wang;Shin'ichiro Matsuo;Masaaki Shirase;Tsuyoshi Takagi
有限域上的椭圆曲线对是构造各种密码体制的关键。GF（3 n）上超奇异曲线上的η T配对由于其可有效实现而特别受欢迎。考虑到Menezes-Okamoto-Vanstone攻击，GF（36 n）上的离散对数问题（DLP）成为使用η T对的密码系统安全性的关注点。在2006年，Joux和Lercier提出了一个新的函数域筛在中素情况下的变体，命名为JL 06-FFS。然而，我们还没有找到任何实际的实现JL 06-FFS GF（36 n）。因此，我们首先实现了这样的实现，并且我们成功地创造了解决GF（36 n）中DLP的新记录，即GF（36·71）中676位大小的DLP。此外，我们还比较了JL 06-FFS和早期版本，命名为JL 02-FFS，与实际实验。我们的结果证实，前者是几倍的速度比后者在一定条件下。
Pairings on elliptic curves over finite fields are crucial for constructing various cryptographic schemes. The ηTpairing 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 ηTpairings 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.