A study on the probabilistic algorithm to solve the elliptic curve discrete logarithm problem

摘要

In this paper a probabilistic algorithm to solve the ECDLP is presented. This scheme uses the symmetry of the elliptic curve, and can be applied to a wide class of elliptic curves. In the proposed scheme a large number of random integers H_i ∈ {0,1, • • •, g-1} (I = 1,2, • • •) are generated to calculate the points Q + [Hi]P (I = 1,2, • • •), where Q = [K_(secret)]P and g is the order of the point P. Then, the scheme tries to find a pair of points Q + [Hi]P and Q + [H_j]P whose X-coordinates are the same value but H_i 4= Hj, i.e., one in the pair is the inverse of the other. If such a pair is found, the secret K_(secret) can be calculated by 2K_(secret) + H_i + H_j =0 (mod g). We investigate the probability to find such a pair among m random points on an elliptic curve. The probability of finding one or more pairs would be 1/2 when m is of the order of g~(1/2). Furthermore, we discuss the techniques to reduce the size of disk storage and to parallelize the operation with multiple computers. It is also shown that the proposed algorithm can be extended to solve the usual discrete logarithm problem (DLP).%一般的な楕円曲線上の離散対数問題に対する確率的な解法を提案する．この方式は，多数の乱数H_i∈｛0，1，…，g-1｝（i=1，2，…，m）に対してQ＋［H_i］Pを計算し，それらの点をズ座標の値でソートすることで．X座標が等しく凡手巧となるQ＋［H_i］PとQ＋［H_j］Pのペアを探し，2K_（secret）＋H_i＋H_j≡0（mod g）からK（secret）を求める．ただし，Q=［K_（secret）］Pとし，gを点Pの位数とする．本論文では．確率1/2以上で解を求めることができる乱数の数mが、√g以下であることを示す・さらに，この解法を拡張して，計算量を少し増やすことでrn記憶領域のサイズを小さくする方式や，複数の計算機で効率的に並列処理を行う方式を示す．