Status Report on Knapsack-Based Public Key Cryptosystems

摘要

In the period since 1976, when Diffie and Hellman published the first discussion of two-key cryptography to appear in the open literature, only a handful of two-key cryptoalgorithms have been proposed - two of which are based on the knapsack problem. Consequently there was enormous interest when Shamir announced in early 1982 a cryptanalytic technique that could break many Merkle-Hellman knapsacks. In a rapid sequence of developments, Simmons and Brickell, Adleman, and Lagarias all announced other attacks on knapsack-based cryptosystems that were either computationally much more efficient or else directed at other knapsack schemes such as the Graham-Shamir or iterated systems. This paper analyzes the common features of knapsack-based cryptosystems and presents all of the cryptanalytic attacks made in 1982 from a unified viewpoint. (ERA citation 08:032926)