Knapsack cryptosystems

Knapsack Cryptosystems are cryptosystems which security is based on the hardness of solving the knapsack problem. They remain quite unpopular because simple versions of these algorithms have been broken for several decades.[1] 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,[2] one by Adleman,[3] and the low density attack.

However, there exist modern knapsack cryptosystems that are considered secure so far: among them is Nasako-Murakami 2006.[4]

Knapsack cryptosystems, when not subject to classical cryptoanalysis, are believed to be difficult even for quantum computers. That is not the case for systems that rely on factoring large integers, like RSA, or computing discrete logarithms, like ECDSA, problems solved in polynomial time with Shor's algorithm.[5]

References

Schneier, Bruce (2004). Secrets and Lies. Wiley Publishing, Inc. p. 95. ISBN 978-0-471-25311-2.
Shamir 1982.
Adleman 1982.
Nasako & Murikami 2006.
Shor, Peter (1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Computing. 26 (5): 1484–1509. arXiv:quant-ph/9508027. doi:10.1137/s0097539795293172. S2CID 2337707.

Bibliography

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, doi:10.11540/jsiamt.16.4_591

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Schneier, Bruce (2004). Secrets and Lies. Wiley Publishing, Inc. p. 95. ISBN 978-0-471-25311-2.

[FOOTNOTEShamir1982-2] Shamir 1982.

[FOOTNOTEAdleman1982-3] Adleman 1982.

[FOOTNOTENasakoMurikami2006-4] Nasako & Murikami 2006.

[5] Shor, Peter (1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Computing. 26 (5): 1484–1509. arXiv:quant-ph/9508027. doi:10.1137/s0097539795293172. S2CID 2337707.