A New Public-Key Cryptosystem over a Quadratic Order with Quadratic Decryption Time |
| |
Authors: | Sachar Paulus Tsuyoshi Takagi |
| |
Affiliation: | Technische Universit?t Darmstadt, Alexanderstrasse 10, D-64283, Darmstadt, Germany NTT Software Laboratories 3-9-11, Midori-cho, 180, Musashino-shi, Tokyo, Japan
|
| |
Abstract: | We present a new cryptosystem based on ideal arithmetic in quadratic orders. The method of our trapdoor is different from
the Diffie—Hellman key distribution 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 cryptosystem is a probabilistic encryption scheme and has the homomorphy property.
The most prominent property of our cryptosystem is the cost of the decryption, which is of quadratic bit complexity in the
length of the public key. Our implementation shows that it is comparably as fast as the encryption time of the RSA cryptosystem
with e=2
16
+1 . The security of our cryptosystem is closely related to factoring the discriminant of a quadratic order. When we choose
appropriate sizes of the parameters, the currently known fast algorithms, for example, the elliptic curve method, the number
field sieve, the Hafner—McCurley algorithm, are not applicable. We also discuss that the chosen ciphertext attack is not applicable
to our cryptosystem.
Received 29 June 1998 and revised 15 November 1998 |
| |
Keywords: | , Public-key cryptosystem, Fast decryption, Quadratic order, Factoring algorithm, Chosen ciphertext attack, |
本文献已被 SpringerLink 等数据库收录! |
|