①Key Lab of Computer Networks & Information Security, Ministry of Education, Xidian University, Xi’an 710071, China; ②State Key Lab of Information Security, Institute of Software, Chinese Academy of Sciences, Beijing 100049, China; ③School of Information and Communication, Guilin University of Electronic Technology, Guilin 541004, China
Abstract：A knapsack-type public key cryptosystem is proposed. The proposed knapsack cryptosystem has the following advantages. The encryption and decryption only need addition and modular minus operations, so the encryption and decryption speed is high; The cryptosystem is constructed based on random knapsacks but not easy-to-solve knapsack problems; It is proven that if the secret key is not possessed by the attacker, the proposed cryptosystem can withstand the attacks launched by directly solving the underlying knapsack problem, including low-density attack and simultaneous Diophantine approximation attack; It is proven that the attacker can recover the secret keys if and only if he can factor a large integer. Analysis shows that the proposal is an efficient and secure public key encryption algorithm.
2010, Vol. 32 
