(A) study on a secure multi-user knapsack public key cryptosystem

Abstract

Recently, a dense knapsack public key cryptosystem based on arithmetic in finite fields was developed by Chor-Rivest. Its encryption and decryption procedures are simple and fast. But it takes too long time to generate a knapsack vector because of using discrete logarithms, and the calculation of discrete logarithms can be used for only one person. To shorten the construction time of the cryptosystem, we propose a knapsack public key cryptosystem in which the knapsack vector can be shared by many people once it is generated. our system will be based on a generalized version of Bose-Chowla theorem which provides uniqueness of subset sum in finite fields. Our system is secure against the case that one of the private keys is known. Also it is secure against any attack because we use no superincreasing sequences and our knapsack vector is dense enough to foil Lagarias-Odlyzko low density attack.