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

Sachar Paulus, Tsuyoshi Takagi

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)


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 mpr, 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 = 2IS +. 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.

Original languageEnglish
Pages (from-to)263-272
Number of pages10
JournalJournal of Cryptology
Issue number2
Publication statusPublished - 2000
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'A new public-key cryptosystem over a quadratic order with quadratic decryption time'. Together they form a unique fingerprint.

Cite this