Security and design of knapsack public key cryptosystems

This paper discusses the bit security of knapsack-based public key cryptosystems and establishes the equivalence between the security of some particular bits in the plaintext and the plaintext itself. Furthermore, a new public key cryptosystem based on the knapsack problem is presented. The system differs from the Merkle-Hellman's scheme in that it does not involve any superincreasing sequence of knapsack components. In addition, the system has a high density when choosing the system parameters properly, so it is secure against both Shamir's polynomial cryptoanalysis algorithm and Brickell's algorithm of solving low density knapsacks.