Knapsack Cryptosystems are cryptosystems which security is based on the hardness of solving the knapsack problem. They remain quite unpopular because these algorithms have been broken for several decades. However that type of cryptosystem is a good candidate for post-quantum cryptography.
The most famous knapsack cryptosystem is the Merkle-Hellman Public Key Cryptosystem, one of the first public key cryptosystems, published the same year as the RSA cryptosystem. However this system has been broken by several attacks : one from Shamir, one by Adleman, and the low density attack.
However, there exist modern knapsack cryptosystems that are considered secure so far: among them is Nasako-Murakami 2006.
What is interesting with those systems is that the Knapsack problem, in the settings where no attack were found, is believed to be difficult to solve even by a quantum computer. This is not the case for systems as RSA relying on the problem of factoring large integers, a problem that is solved in polynomial time by Shor's algorithm.
- Leonard Adleman (1982), "On breaking the titrated Merkle-Hellman public-key cryptosystem", Crypto'82, Springer: 303–308, doi:10.1007/978-1-4757-0602-4_29, ISBN 978-1-4757-0604-8
- Adi Shamir (1982), "A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystems", Focs'82: 145–152, doi:10.1109/SFCS.1982.5
- T. Nasako; Y. Murakami (2006), "A high-density knapsack cryptosystem using combined trapdoor", Japan Society for Industrial and Applied Mathematics, 16 (4): 519–605
|This cryptography-related article is a stub. You can help Wikipedia by expanding it.|