The Cryptographic Security of Compact Knapsacks (Preliminary Report)
Author(s)
Shamir, Adi![Thumbnail](/bitstream/handle/1721.1/148991/MIT-LCS-TM-164.pdf.jpg?sequence=3&isAllowed=y)
DownloadMIT-LCS-TM-164.pdf (3.019Mb)
Metadata
Show full item recordAbstract
In 1978, Merkle and Hellman introduced a knapsack-based public-key cryptosystem, which received widespread attention. The two major open problems concerning this cryptosystem are: (i) Security: How difficult are the Merkle-Hellman knapsacks? (ii) Efficiency: Can the huge key size be reduced? In this paper we analyze the cryptographic security of knapsack problems with small keys, develop a new (non-enumerative) type of algorithm for solving them, and use the algorithm to show that under certain assumptions it is as difficult to find the hidden trapdoors in Merkle-Hellman knapsacks as it is to solve general knapsack problems.
Date issued
1980-04Series/Report no.
MIT-LCS-TM-164