Abstract: Traditional public key cryptosystems suffer from a drawback that the encryption／decryption speed is relatively low, which hampers their applications in resource-constrained environments. A fast public-key cryptosystem is proposed to remedy this drawback. The new algorithm uses the Chinese remainder theorem to hide the trapdoor information. The encryption of the system only carries out several modular multiplication operations, and the decryption only needs a modular multiplication and a low-dimensional matrix-vector multiplication, which makes the speed of the encryption and the decryption of the scheme very high. The security of the system is based on two number-theoretic hard problems. The attacker has to solve the integer factorization problem and the simultaneous Diophantine approximation problem simultaneously to recover the secret key from the public key. The proposed cryptosystem is also shown to be secure against the lattice attack. Analysis shows that the encryption algorithm is a secure, fast and efficient public key cryptosystem.

Key words: public-key cryptography, fast public-key cipher, Chinese remainder theorem, integer factorization, simultaneous Diophantine approximation