서지주요정보
Elliptic curve discrete logarithm and lifting problem = 타원곡선 이산로그와 올림 문제
서명 / 저자 Elliptic curve discrete logarithm and lifting problem = 타원곡선 이산로그와 올림 문제 / Hwan-Joon Kim.
발행사항 [대전 : 한국과학기술원, 2000].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8010805

소장위치/청구기호

학술문화관(문화관) 보존서고

DMA 00005

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

리뷰정보

초록정보

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와 타원곡선 이산로그의 어려움를 연관지어 수식으로 표현하였다.

서지기타정보

서지기타정보
청구기호 {DMA 00005
형태사항 [ii], [33] p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 김환준
지도교수의 영문표기 : Sang-Geun Hahn
지도교수의 한글표기 : 한상근
수록잡지명 : "Elliptic curve lifting problem and its applications". Proceedings of the japan academy
학위논문 학위논문(박사) - 한국과학기술원 : 수학전공,
서지주기 Reference : p. 32-33
주제 Elliptic curve
Discrete logarithm
Factorization
타원곡선
이산로그
소인수 분해
QR CODE qr code