A Novel Combinatorial Public Key Cryptosystem

Article type: Research Article

Authors: Wang, Baocang^; | Hu, Yupu

Affiliations: Key Laboratory of Computer Networks and Information Security, Xidian University, Xi'an 710071, China | State Key Laboratory of Information Security, Institute of Software, Chinese Academy of Sciences, Beijing 100049, China, e-mail: [email protected], [email protected]

Abstract: Combinatorial problems serve as an important resource for developing practical public key cryptosystems and several combinatorial cryptosystems have been proposed in the cryptographic community. In this paper, a combinatorial public key cryptosystem is proposed. The security of the proposed cryptosystem is dependent on a combinatorial problem involving matrices. The system features fast encryption and decryption. However, the system also suffers from some drawbacks. The ciphertext expansion is relatively large and the key sizes are somewhat larger than that of RSA. The security of the system is carefully examined by illustrating the computational infeasibilities of some attacks on the system.

Keywords: public key cryptography, combinatorial cryptosystem, integer factorization, lattice reduction, security

Journal: Informatica, vol. 21, no. 4, pp. 611-626, 2010