NTRU-Like Secure and Effective Congruential Public-Key Cryptosystem Using Big Numbers

Abstract

We propose RCPKC, a random congruential public key cryptosystem working on integers modulo q, such that the norm of a two-dimensional vector formed by its private key, (f; g), is greater than q. RCPKC works similar to NTRU, the fastest and secure PKC. NTRU, uses high order, N, polynomials and is susceptible to the lattice basis reduction attack (LBRA) taking time exponential in N. RCPKC is a secure version of insecure CPKC proposed by NTRU authors and easily attackable by LBRA since CPKC uses small numbers for the sake of the correct decryption. RCPKC specifies a range from which the random numbers shall be selected, it provides correct decryption for valid users and incorrect decryption for an attacker using Gaussian Lattice Reduction (GLR). Because of its resistance to LBRA, RCPKC is more secure, and, due to the use of big numbers instead of high order polynomials, about 24 (7) times faster in encryption (decryption) than NTRU. Also, RCPKC is more than 3 times faster than the most effective known NTRU variant, BQTRU.