A new public-key cryptosystem over a quadratic order with quadratic decryption time

We present a new cryptosystem based on ideal arithmetic in quadratic orders . The method of our trapdoor is different from the Diffie-Hellman key distr ibution scheme or the RSA cryptosystem. The plaintext m is encrypted by mp( r), where p is a fixed element and r is a random integer, so our proposed c ryptosystem is a probabilistic encryption scheme and has the homomorphy pro perty. The most prominent property of our cryptosystem is the cost of the d ecryption, which is of quadratic bit complexity in the length of the public key. Our implementation shows that it is comparably as fast as the encrypt ion time of the RSA cryptosystem with e = 2(16) + 1. The security of our cr yptosystem is closely related to factoring the discriminant of a quadratic order. When we choose appropriate sizes of the parameters, the currently kn own fast algorithms, for example, the elliptic curve method, the number fie ld sieve, the Hafner-McCurley algorithm, are not applicable. We also discus s that the chosen ciphertext attack is not applicable to our cryptosystem.