No subexponential time algorithm is known yet for the Elliptic Curve Discrete Logarithm Problem(ECDLP) except the cases of singular curves, supersingular curves and anomalous curves. In this paper, we introduce the lifting problem and show that it implies the ECDLP and integer factorization problem(IFP) and we note that finding a point in $E_1(Q)$, the kernel of the reduction map, also implies the ECDLP and the IFP since it solves the lifting problem. Moreover, we analyze the difficulty of the lifting problem by estimating the minimum of the canonical heights on the kernel of the reduction map.
유한체에서 정의된 이산로그의 경우, 정수로의 올림을 이용한 Index Calculus 알고리즘이 알려져 있으나, 타원곡선 이산로그의 경우에는 몇몇 특수한 경우에 한하여 그 해법이 알려졌을 뿐, 일반적인 타원곡선에 대하여 이를 해결하는 준 지수시간 알고리즘(subexponential time algorithm)은 아직 알려지지 않고 있다.
본 논문에서는 타원곡선의 올림을 정의하고, 이를 이용한 타원곡선 이산로그 공격방법을 제안한다. 이를 위하여, descent 방법으로 유리체 위에서 정의된 타원곡선의 유리점의 일차 의존 관계식(dependence equation)의 계수를 다항식 시간안에 계산할 수 있음을 보인다. 또한, 이 방법을 유한체 $F_p^n$위에서 정의된 타원곡선에서 적용할 수 있도록 일반화 한다. 또한, 환 Z/nZ 위에서 정의된 타원곡선에 대한 올림을 구할 수 있는 경우, 타원곡선위의 한 점에 대한 위수를 계산할 수 있고, 이를 이용하여, 자연수 n을 소인수 분해할 수 있음을 보였다.
마지막으로, 현재 알려져 있는 올림방법의 문제점을 살펴 보고, 특히, 기존의 올림 타원곡선에서 $E_1(Q)$의 최소 canonical height와 타원곡선 이산로그의 어려움를 연관지어 수식으로 표현하였다.
