Public key cryptanalysis using lattice reduction algorithms

Abstract

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.