A new public-key cryptosystem and its applications
We propose in this paper a new public-key crypto-system, called the non-linear knapsack cryptosystem. The security of this system is based on the NP-completeness of the non-linear knapsack problem. We extend the system into secret sharing and access control. That is, an encrypted message can be decrypted only when all members of a group agree to do so with their secret sub-keys. The secret sharing here is equivalent to access control, which establishes multiple identities. That is, when the verifier challenges the prover with encrypted messages with public sub-keys, the prover can prove multiple identities using the secret sub-keys. Some experimental results are given, which demonstrate the efficiency of our system.