Why is the NTRUEncrypt Public Key Cryptosystem more secure than earlier lattice based systems, such as knapsack systems, that have been broken?
The original collection of cryptosystems broken by lattice reduction were those based upon variations of the knapsack problem. As each new variation appeared, hopeful authors did everything in their power to avoid potential transformations of their “hard problem” into one that could be attacked by lattice reduction. As the survey article by Odlyzko describes, no matter how obscured the original problem was, it still always proved in the end to be possible to transform it into one vulnerable to LLL lattice reduction methods. The last one to bite the dust was the Chor-Rivest system, broken by Schnorr’s recent improvements to the LLL algorithm. One of the fundamental problems these authors faced was the fact that the key size of their system grew with the square of the dimension of the lattice used for an attack. Because of this, it was impossible to make the dimension of an attack lattice greater than a couple of hundred without simultaneously making the cryptosystem impractical. Develop
