An efficient construction of a CNF for a system of quadratic equations and its application to an algebraic attack against the NTRU cryptosystem = 이차식으로 이루어진 계를 위한 CNF의 효율적인 생성 및 이를 이용한 NTRU 암호 시스템에 대한 공격

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.
Hahn, Sang-Geunresearcher한상근researcher
Issue Date
455381/325007  / 020025123

학위논문(박사) - 한국과학기술원 : 수리과학과, 2010.08, [ ⅵ, 39 p. ]


대수적 공격; 논리곱 표현형; 암호; NTRU; symmetric quadadratic polynomial; conjunctive normal form; algebraic attack; cryptosystem; NTRU; 대칭꼴 이차식

Appears in Collection
Files in This Item
There are no files associated with this item.
  • Hit : 126
  • Download : 0
  • Cited 0 times in thomson ci


  • mendeley


rss_1.0 rss_2.0 atom_1.0