特征 p 椭圆曲线上 p-群的离散对数问题

Abstract

设E是定义在有限域\Fq上的一条椭圆曲线. 当曲线的Frobenius迹为1时, 即#E(\Fq)=q, 我们称其为异常曲线. 为了设计安全的椭圆曲线密码方案, 我们通常要求曲线的群阶含有一个大素因子. 而素域上的异常曲线恰好满足这个要求, 其群阶为素数, 等于有限域的大小. 然而研究学者发现这样看似安全的椭圆曲线其实并不安全. Satoh-Araki, Semaev和Smart分别提出了求解异常曲线上离散对数问题的有效算法. 其中Satoh-Araki和Smart提出的算法本质相同, 均为提升法. 该方法通过把素域\Fp上的椭圆曲线提升到p-adic域\Qp上, 然后利用易于计算的形式对数映射求出离散对数. 然而Satoh-Araki和Smart只给出了素域上椭圆曲线的提升法, 并没有提及当基域是非素域时的情形. 本文将推广该方法, 使其可以求解特征p有限域上椭圆曲线p-群的离散对数问题. 该方法和Semaev的方法具有相同的复杂度, 并且具有简洁和直观的优势. 进一步, 我们将讨论\Qp及其代数扩域上椭圆曲线离散对数问题, 并给出它们与有限域上椭圆曲线离散对数问题的关系.

Alternate abstract:

Let E be an elliptic curve defined over finite field \Fq. E(\Fq) is said to be anomalous if its trace of Frobenius is 1, i.e. #E(\Fq)=q. To design a secure elliptic curve cryptosystem, we usually require #E(\Fq) to have a large prime divisor. The anomalous elliptic curve over a prime field meets this requirement. Its group order is a prime, which is equal to the size of the finite field. However, researchers find that these curves are not secure. Satoh-Araki, Semaev and Smart independently proposed efficient algorithms for discrete logarithm problem on anomalous elliptic curves. The methods proposed by Satoh-Araki and Smart are essentially the same. By lifting the elliptic curve over a prime field \Fp to an elliptic curve over a p-adic field \Qp, one can solve the discrete logarithm problem by using the computable formal logarithm. However, Satoh-Araki and Smart only gave the lifting method for elliptic curves over prime fields and did not mention the case when the underlying field is nonprime. In this work, we generalize this method to solve the discrete logarithm problem in any p-group on elliptic curves over finite fields in characteristic p. The method enjoys the same complexity as Semaev's method and is more concise and intuitional. Moreover, we also discuss the elliptic curve discrete logarithm problem over \Qp and its algebraic extension fields and give its relationship with the elliptic curve discrete logarithm problem over finite fields.