Many cryptosystems can be attacked by a method of an algebraic attack, which derives systems of algebraic equations and solve them. Bard-Courtois-Jefferson suggested to convert a system of quadratic equations to a conjunctive normal form (CNF) and solve a satisfiability problem for the form logically, instead of solving the system algebraically. In this paper we extend their work to construct a CNF for quadratic polynomials efficiently. First we identify each symmetric polynomial with a set and split those sets into smaller sets, then compute CNFs for the smallers. CNFs for original polynomials are built from them easily. Our method generates much smaller CNF than Bard et al.`s, and so our CNFs are solved much faster than theirs. We apply our work to a system from an algebraic attack against the NTRU cryptosystem, whose algebraic equations consist of a sum of quadratic symmetric polynomials. As a result our method reduces the size of the CNF from $O(N^{3})$ to $O(N^{2})$, where $\N$ is a security parameter of the NTRU system. Also the satisfiability problem is solved faster. In case of $\N$ = 28 our CNF can be solved about 30 times faster in average than theirs.
많은 암호 시스템은 대수적 공격방법을 사용하여 공격할 수 있다. 이 공격에서 공격자는 암호 시스템으로부터 다항식의 계를 얻어내어 이 계를 대수적 방법으로 풀어내게 된다. Bard-Courtois-Jefferson은 이차식으로 이루어진 다항식의 계로부터 논리곱 표준형 (Conjunctive Normal Form, CNF) 을 얻어내어, 원래의 계를 대수적으로 푸는 대신에 이 표준형을 논리적으로 푸는 방법을 제안하였다. 본 논문에서는 Bard 등의 방법을 확장하여 이차식을 더 효율적으로 CNF로 변환하는 방법을 제시하였다. 우선 각각의 이차식에서 대칭꼴인 일차식과 이차식을 분리한 후 이 대칭식을 변수의 집합으로 표시한 뒤, 이 집합을 작은 집합들로 분리해 나간다. 이 작은 집합에 대응하는 대칭식의 CNF를 계산한 뒤, 이를 다시 합쳐 원래 집합의 CNF를 계산하게 된다. 우리가 제시한 방법은 Bard 등의 방법보다 훨씬 짧은 CNF를 만들게 되고, 따라서 이 CNF를 논리적으로 풀 때도 훨씬 짧은 시간이 걸리게 된다. 대수적 공격을 이용하면 NTRU 암호 시스템으로부터 긴 대칭식의 합으로 나타나는 이차식이 유도됨이 알려져있기에, 실제 응용 결과를 보기 위해 우리 방법을 적용해보았다. 그 결과 N을 NTRU의 안전계수라할 때, Bard 등의 방법으로는 $O(N^{3})$의 길이를 가지는 CNF가 얻어지지만 우리 방법을 이용하면 그 길이가 $O(N^{2})$로 줄어듬을 확인할 수 있었다. 아울러 우리의 CNF는 Bard 등의 것보다 훨씬 빨리 풀렸는데, $\N$=28의 경우 평균 30배 이상 빠름을 확인할 수 있었다.
