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.
Advisors
Hahn, Sang-Geunresearcher한상근researcher
Publisher
한국과학기술원
Issue Date
2010
Identifier
455381/325007  / 020025123
Language
eng
Description

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

Keywords

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

URI
http://hdl.handle.net/10203/41942
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=455381&flag=t
Appears in Collection
MA-Theses_Ph.D.(박사논문)
Files in This Item
There are no files associated with this item.
  • Hit : 126
  • Download : 0
  • Cited 0 times in thomson ci

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0