Efficient Inversion Algorithms and Its Applications to ECDLP

Abstract

이 논문에서 타원 곡선에서 태그 트레이싱 기법을 적용시켰다. 처음에 천정희 등이 제안한 태크 트레이싱은 폴라드로 알고리즘을 더욱 빠르게 돌도록 해준다. 이 방법을 이용하면 유한체에서 이산 대수 문제를 10배 더 빠르게 풀 수 있다. 그러나, 타원 곡선에서는 덧셈 연산 때문에 이정도의 효 과를 보지 못한다. 덧셈을 하기 위해서는 역원 연산과 제곱 두 번을 포함한 곱셈 연산을 세 번을 해야한다. 역원 연산은 시간이 가장 많이 걸리는 연산 이기 때문에 좀 더 빠르게 할 수 있도록 개선을 할 필요가 있다. 그래서 우 리는 확장체에서 유용하게 사용되는 역원 알고리즘에 대해서 살펴보았다. 가장 널리 쓰이는 두 개의 알고리즘이 있는데, 하나는 확장된 유클리디안 알고리즘이고, 다른 하나는 이토-쯔지 알고리즘이다. 이 외에도, 역행렬을 이용하여 역원을 구할 수 있다. 우리는 이 알고리즘들의 계산 복잡도를 비교해보았고, 우리에 환경에 맞췄을 때 가장 빠른 역원 알고리즘을 비교 대상으로 삼았다. 그리고 복잡도를 계산해본 결과, 확장체의 차수가 낮은 경우에 역행렬을 이용하여 역원을 구하는 방법이 더 빠르다는 것을 알 수 있었다. 또한, 역행렬을 이용할 경우 역원의 전체를 다 구하지 않고 역원의 계수 하나를 빠르게 구할 수 있었다. 이 방법을 이용하여 우리는 확장체의 차수가 낮은 경우에 타원 곡선 이산 대수 문제를 이 전에 알려진 방법보다 더 빠르게 풀 수 있었다.

In this paper, we apply tag tracing technique to elliptic curves. Tag tracing is the technique which can apply to the Pollard rho algorithm, first suggested by Cheon et al. They can solve DLP 10 times faster than before in the multiplicative groups of finite field. However, for elliptic curves, tag tracing does not effect so much because of an addition in elliptic curves. To add two pointsin elliptic curves, we actually need one inversion and three multiplications including two squaring. An inversion operation is the most time-consuming arithmetic, so an inversion algorithm needs to be improved. We investigate some useful inversion algorithms which can be used for a finite extension field. Until now, there are two widely used algorithms to get an inverse element over the finite extension field. One is extended Euclidean algorithm, and the other is Itoh-Tsujii inversion algorithm. Beside these algorithms, we can compute an inverse element by computing an inverse matrix. Generally, this method is slower than the other algorithms, but when the degree of the extension field is small, this is slightly faster. We compare the complexity of these algorithms and use the most efficient method suitably for our setting when applying tag tracing to elliptic curves, Also, to accelerate the Pollard rho algorithm, we calculate the pre-computation table. Using these skills, we expect to reduce the time complexity to solve ECDLP than before.