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에서 발표된 흥미있는 격자들에 대해서 몇 가지 관찰을 함으로써 짧은 벡터를 찾을 수 있는 방법들을 제시하였다. 이 격자들은 짧은 벡터들이 상당히 많이 숨어 있어서 흥미로운 연구의 대상이 된다. 이 격자들에 위의 방법을 적용한다면 짧은 벡터들을 좀 더 쉽게 찾을 수 있으리라 기대된다.
