Attacks of Knapsack Cryptosystem using LLL

Abstract

Historically, a lattice and the LLL algorithm have played important roles in mathematics and cryptography as a problem-solving tool. In this paper, among applications of LLL algorithm, we describe several algorithms to attack knapsack cryptosystem using LLL. A key part of these attacks is to convert knapsack problems into lattice problems. So we show how to do these works. We expect that these work give us insights into converting hard problems to lattice problems in a variety of situations.