서지주요정보
Public key cryptanalysis using lattice reduction algorithms = 격자 축소 알고리즘을 이용한 공개키 암호 분석
서명 / 저자 Public key cryptanalysis using lattice reduction algorithms = 격자 축소 알고리즘을 이용한 공개키 암호 분석 / Moon-Sung Lee.
저자명 Lee, Moon-Sung ; 이문성
발행사항 [대전 : 한국과학기술원, 2009].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8020300

소장위치/청구기호

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

DMA 09003

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

초록정보

The security of lattice based cryptosystems is related to the closest vector problem, which is usually attacked by lattice reduction algorithms in practice. Since the performance of these lattice reduction algorithms is better when a lattice gap is large, enlarging this gap is important. We study methods of enlarging this lattice gap, which results in an easier reduction. More precisely, we show by experiment that multiplying integers to the random vectors of a basis increases a lattice gap. This is done at a cost of increased number of closest vector problems to solve, however, they can be solved in parallel. Using these methods, we cryptanalyze the GGH cryptosystem and Micciancio`s cryptosystem. And the GGH challenge 400 is solved combining with Nguyen`s previous attack. Also, a strategy to find short vectors in a family of lattices proposed in PQCrypto 2008 is suggested.

격자에서 가장 짧은 벡터를 찾는 것이 어렵다는 사실과 격자에서의 어려운 문제의 최악의 경우도 고려한 복잡도와 평균적인 복잡도 사이에 관계가 있다는 사실이 알려지면서, 격자에 기반한 암호들이 많이 개발되었다. 격자에 기반한 많은 암호들이 안전성에 문제가 있거나 효율성에 문제가 있어서 잘 사용되지 않지만 어려운 문제의 복잡도에 대한 보장이 있기 때문에 여전히 많은 관심을 끌고 있으며 연구되고 있다. 이들은 보통 격자에서의 가장 가까운 벡터를 찾는 문제와 관련이 있으며, 이 문제에 대한 가장 효율적인 알고리즘은 격자 축소 알고리즘이다. 격자 축소 알고리즘은 격자에 기반한 암호체계들의 안전성과 깊이 관련되어 있으며, 격자 갭이 클수록 격자 축소 알고리즘이 더 효율적으로 동작한다는 사실이 알려져 있다. 우리는 격자 갭을 크게 할 수 있는 방법들에 대해 연구하였으며, 격자의 기저에 랜덤하게 정수를 곱해줌으로써 격자 갭을 크게 할 수 있음을 실험적으로 보였다. 비록 이 방법을 사용하면 이렇게 얻게 된 격자 갭이 커져서 보다 쉬워진 문제들을 여러 개 풀어야 하지만, 이는 병렬화가 가능하므로 충분한 자원을 가진다면 전혀 문제가 되지 않는다고 할 수 있으며, 자원이 부족하더라도 부분적인 병렬화는 항상 가능하므로 가진 자원을 최대한 활용할 수 있는 방법이 된다. 우리는 이 방법을 사용하여 GGH 암호와 Micciancio의 암호의 해독을 연구하였으며, GGH 암호의 경우 미해결 문제였던 차수 400의 문제를 풀 수 있었고, Micciancio의 암호의 경우에는 그 안전성을 다시 평가할 수 있었다. 또한, 최근에 PQ Crypto 2008에서 발표된 흥미있는 격자들에 대해서 몇 가지 관찰을 함으로써 짧은 벡터를 찾을 수 있는 방법들을 제시하였다. 이 격자들은 짧은 벡터들이 상당히 많이 숨어 있어서 흥미로운 연구의 대상이 된다. 이 격자들에 위의 방법을 적용한다면 짧은 벡터들을 좀 더 쉽게 찾을 수 있으리라 기대된다.

서지기타정보

서지기타정보
청구기호 {DMA 09003
형태사항 vi, 36 p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 이문성
지도교수의 영문표기 : Sang-Geun Hahn
지도교수의 한글표기 : 한상근
학위논문 학위논문(박사) - 한국과학기술원 : 수리과학과,
서지주기 References : p. 35-36
주제 Lattice reduction;Lattice gap;Lattice challenge;GGH;
격자 축소;격자 틈;격자 도전;GGH;
QR CODE qr code