Public key cryptanalysis using lattice reduction algorithms = 격자 축소 알고리즘을 이용한 공개키 암호 분석

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

학위논문(박사) - 한국과학기술원 : 수리과학과, 2009.2, [ vi, 36 p. ]

Keywords

Lattice reduction; Lattice gap; Lattice challenge; GGH; 격자 축소; 격자 틈; 격자 도전; GGH; Lattice reduction; Lattice gap; Lattice challenge; GGH; 격자 축소; 격자 틈; 격자 도전; GGH

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

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0