To search, Click below search items.


All Published Papers Search Service


Cryptanalysis of a Knapsack Cryptosystem based on Multiple Knapsack


Jinsu kim


Vol. 19  No. 8  pp. 14-17


We propose a cryptanalysis of a knapsack cryptosystem which is based on three knapsacks. That was introduced by Kobayashi et al [1]. On their encryption scheme, a cipher text is formed by multiplying two non-super-increasing knapsacks together and then adding it to the super-increasing knapsack. They insist that this construction is secure against known attacks including the low density attack and Shamir attack. However due to modular mapping structure, we can apply the method, orthogonal lattice attack, provided by Nguyen and Stern in Crypto'97[6]. More specifically, we show how to find private keys from the corresponding public keys in the cryptosystem. Therefore, we argue that the cryptosystem is insecure one.


Knapsack, Cryptosystem, orthogonal lattice attack, multiple knapsack