Discrete Logarithm with Low Hamming Weight Exponents
성긴 지수 이산대수 문제

Cited 0 time in Web of Science Cited 0 time in Scopus
자연과학대학 수리과학부
Issue Date
서울대학교 대학원
Discrete Logarithm ProblemLow Hamming Weight Discrete Logarithm ProblemLow Hamming Weight Product Discrete Logarithm ProblemParameterized Splitting Systems
학위논문 (박사)-- 서울대학교 대학원 : 수리과학부, 2012. 8. 천정희.
이산대수 문제는 현대 공개키 암호에 있어 가장 중요한 수학적 기반 문제의 하나이다. 수많은 암호 시스템과 프로토콜들이 이산대수가 어렵다는 가정하게 설계 및 제안되고 있으며 이러한 연구는 활발하게 진행되고 있다.

이산대수 기반 암호 시스템의 효율성은 지수승 연산 속도에 직결된다. Hoffstein과 Silverman은 이산대수 문제가 정의된 군에서 빠른 지수승과 안전성을 보장하기 위해 해밍 웨이트가 작은 지수들의 곱(성긴 지수 곱)을 사용할 것을 제안하였다. 특히 GF(2^n)에서의 제곱연산 그리고 Koblitz 타운 곡선에서의 두 배 연산은 각각의 군 연산보다 훨씬 빠르기 때문에 성긴 지수 곱을 사용하면 연산을 매우 가속화시킬 수 있다.

본 학위 논문에서는 성긴 지수 곱 이산대수 문제의 안전성을 분석한다. 현재의 성긴 지수 곱 이산대수 문제의 안전성 분석은 성긴 지수 이산대수 문제의 분석 기법에 의존하고 있는데 이로부터는 본래 문제의 정확한 안전성을 측정할 수 없다.

본 논문에서는 성긴 지수 곱 이산대수 문제의 안전성을 분석하기 위해 매개화된 분할 시스템을 이용하여성긴 지수 곱 이산대수 문제를 공격하는 효율적인 알고리즘을 제안한다. 제안 알고리즘은 현재까지 알려진 알고리즘 중 가장 빠른 시간 안에 성긴 지수 곱 이산대수 문제의 해를 찾는다. 실증적인 예로써 Coron, Lefranc 그리고 Poupard가 CHES 2005에서 제안한 GPS 인증 스킴의 비밀키와 Hoffstein과 Silverman이 제안한 (2,2,11)-지수에 대해 제안 알고리즘을 적용하여 각각에 대해 2^{61.82} 그리고 2^{53.02} 번의 군 연산을 사용하여 비밀키를 복구할 수 있음을 보인다.
The discrete logarithm problem is one of the most important underlying mathematical problems in contemporary public key cryptography. Under the assumption that the problem is infeasible, a great number of cryptosystems have been constructed and researches in this area are still underway actively.

The efficiency of cryptosystems based on the discrete logarithm problem primarily relies on the speed at which exponentiation can be performed. On this line of research to address the issue Hoffstein and Silverman suggested the use of low Hamming weight product exponents to accelerate group exponentiation while maintaining the security level. Taking low Hamming weight product exponents, computation costs on GF(2^n) or Koblitz elliptic curves can be reduced significantly, where the cost of squaring and elliptic curve doubling is much lower than that of multiplication and elliptic curve addition, respectively.

In the thesis we focus our concern on the security analysis of the discrete logarithm problem of low Hamming weight product exponents. The current estimate on the security of the problem mainly depends on the approaches for the case of low Hamming weight exponents, which does not fit into the product form well.

We come up with parameterized splitting systems to resolve this problem. We show that it yields an efficient algorithm for the discrete logarithm problem of low Hamming weight exponents with lower complexity than that of any previously known algorithms.

To demonstrate its application, we attack the GPS identification scheme modified by Coron, Lefranc, and Poupard in CHES 2005 and Hoffstein and Silverman's (2,2,11)-exponents. The time complexity of our key recovery attack against the GPS scheme is 2^{61.82}, which was expected to be 2^{78}. Hoffstein and Silverman's (2,2,11)-exponent can be recovered with a time complexity of 2^{53.02}, which is the lowest among the known attacks.
Files in This Item:
Appears in Collections:
College of Natural Sciences (자연과학대학)Dept. of Mathematical Sciences (수리과학부)Theses (Ph.D. / Sc.D._수리과학부)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.