caa a22 4500 47582721X CHVBK 20180406123831.0 cr unu---uuuuu 170329e20000301xx s 000 0 eng 10.1007/s001459910010 doi (NATIONALLICENCE)springer-10.1007/s001459910010 A New Public-Key Cryptosystem over a Quadratic Order with Quadratic Decryption Time [Elektronische Daten] [Sachar Paulus, Tsuyoshi Takagi] 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. International Association for Cryptologic Research, 2000 Key words. Public-key cryptosystem, Fast decryption, Quadratic order, Factoring algorithm, Chosen ciphertext attack nationallicence Paulus Sachar Technische Universität Darmstadt, Alexanderstrasse 10, D-64283, Darmstadt, Germany aut Takagi Tsuyoshi NTT Software Laboratories 3-9-11, Midori-cho, 180, Musashino-shi, Tokyo, Japan aut Journal of Cryptology Springer Berlin Heidelberg 13/2(2000-03-01), 263-272 0933-2790 13:2<263 2000 13 145 https://doi.org/10.1007/s001459910010 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s001459910010 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Paulus Sachar Technische Universität Darmstadt, Alexanderstrasse 10, D-64283, Darmstadt, Germany aut NATIONALLICENCE 700 1- Takagi Tsuyoshi NTT Software Laboratories 3-9-11, Midori-cho, 180, Musashino-shi, Tokyo, Japan aut NATIONALLICENCE 773 0- Journal of Cryptology Springer Berlin Heidelberg 13/2(2000-03-01), 263-272 0933-2790 13:2<263 2000 13 145 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer