NTRU is a public key encryption scheme whose security is based on a polynomial factorisation problem in the ring $\mathcal{R} = \mathbb{Z}_{q} [X]/(X^{N} - 1)$. It is an interesting system to study for a number of reasons. Firstly, it does not depend on the traditional hard problems, such as factoring or discrete logarithms, on which other practical public key schemes are based. Indeed the best known heuristic attack is that of finding a short vector in a lattice, which appears to be a very hard problem. Furthermore, schemes based on factoring or discrete logarithms can be broken in the quantum setting using Shor’s algorithm. Currently, there is no quantum algorithm which significantly improves the classical approach to breaking NTRU. Secondly, the basic arithmetic operations in NTRU are particularly simple making it suitable for use in constrained environments where traditional public key schemes have difficulty.
Lattice-based attack is one of the basic attack on NTRU. The results of the lattice-reduction algorithm have a deep relation with the properties of lattice. When we attack NTRU using lattice, the lattice is not general lattice, but convolution modular lattice. Using this property, there are many tries to make more efficient lattice-reduction algorithm. When a lattice is given, using well the properties of the lattice or changing the lattice to more efficient one is also a important problem.
In this paper, we study a hybrid lattice-reduction and meet-in-the-middle attack on NTRU proposed by Nick Howgrave-Graham, 2007. Especially, we apply splitting system to meet-in-the-middle attack. We make the algorithm and, moreover, realize it.
NTRU는 공개키 기반 암호 체계로서 환에서의 다항식의 분해의 어려움을 기반으로 한다. 이는 NP-complete 문제인 격자에서 SVP, CVP를 찾는 문제와도 연관되는 어려운 문제이며, 이 암호체계는 암호화, 복호화 과정이 효율적이며 공개키의 크기도 작고, 생성도 쉽다는 특성을 가지고 있다. 이 암호는 많이 연구되는 암호체계 중 하나이며, 언젠가는 개발되리라 생각되는 양자 컴퓨터에 의해서도 공격되지 않을 가능성이 있다.
NTRU에 대한 격자를 이용한 공격은 가장 기본적인 공격 중 하나이다. 격자 reduction 알고리듬의 결과는 격자의 특성에 상당히 깊은 관련이 있다. NTRU를 만드는 격자는 일반적인 격자가 아닌 convolution modular 격자이다. 이런 특성을 이용해서 좀더 효율적인 격자 reduction 알고리듬을 만드는 시도도 계속되고 있다. 그리고 주어진 격자의 특성을 잘 이용하는, 혹은 주어진 격자를 효과적인 reduction이 가능한 격자로 변형하는 문제 역시 중요하다.
본 논문에서는 2007년에 Nick Howgrave-Graham에 의해 제안된 격자 축소와 meet-in-the-middle 공격을 혼합한 공격에 대해 연구해보았다. 특히, meet-in-the-middle 공격 내에 splitting system을 도입하여 공격 알고리듬을 만들고, 이를 구현해보았다.
