Linearly shift knapsack public-key cryptosystem

Abstract

Two algorithms are proposed to improve the Merkle-Hellman knapsack public-key cryptosystem. an approach to transform a superincreasing sequence to a high-density knapsack sequence is proposed. The algorithm is easy to implement and eliminates the redundancy of many knapsack cryptosystems. A linear shift method is used to improve the security of the knapsack public-key cryptosystem. It is shown that several knapsacks (e.g., the so-called useless knapsack), which cannot be generated by using the Merkle-Hellman scheme, can be generated by the linear shift method. Thus A. Shamir's (1982, 1984) attack to the original knapsack, as well as the low-density attack to the iterated knapsack, cannot be applied to this system successfully. It is interesting to note that the concept of the requirement of being one-to-one in practical enciphering keys is not necessary for this system.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>