The knapsack problem is hard (it's NP-Complete, which is what most people mean when they say "it's hard") but the candidate encryption scheme based off of the k

The knapsack problem is hard (it's NP-Complete, which is what most people mean when they say "it's hard") but the candidate encryption scheme based off of the knapsack problem turned out to be easily breakable (by using lattice reduction techniques, if I remember correctly)[1]. They had to put in structure to the knapsack encoding (to be able to, for example, encrypt and decrypt messages)[2] but put "too much" [3] in so that things like lattice reduction could find solutions without too much trouble (read polynomial time). [1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.11.7624&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.11.... [2] https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsac... [3] https://en.wikipedia.org/wiki/Superincreasing_sequence https://en.wikipedia.org/wiki/Superincreasing_sequence