New public-key cryptosystems with fast decryption

In this doctoral thesis, we propose three public-key cryptosystems with fast decryption function: the NICE cryptosystem, the PkQ cryptosystem and the Nk cryptosystem. The NICE cryptosystem is constructed over non-maximal quadratic orders. The PkQ cryptosystem is constructed over Z/pkqZ, where p,q are primes and k is a positive integer. The Nk cryptosystem is constructed over Z/nkZ, where n is the RSA-modulus and k is a positive integer. These three public-key cryptosystems are not only of theoretical interest but also practical one. The NICE cryptosystem and the PkQ cryptosystem are suitable for implementation on smartcards. The NICE cryptosystem is constructed over quadratic orders. The NICE cryptosystem has two interesting properties. The first property is that the trapdoor mechanism is different from previously reported public-key cryptosystems such as RSA cryptosystem and elliptic curve cryptosystems. The second property is that the decryption process of the NICE cryptosystem is very fast. It is of quadratic bit complexity in the length of the public key, i.e., polynomial time with a polynomial of degree = 2. The NICE cryptosystem is the only known public-key cryptosystem whose decryption has quadratic polynomial time. Our implementation shows that with regards to the decryption time, it is comparably as fast as the encryption time of the RSA cryptosystem with small encryption exponent e=216+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 cryptanalysis such as the number field sieve, the elliptic curve method, or the Hafner-McCurley algorithm are not applicable. The PkQ cryptosystem is constructed over Z/pkqZ, where p,q are primes and k is a positive integer. The prominent property of the PkQ cryptosystem is its decryption time. It is about three times faster than implementations of the RSA cryptosystem that use the Chinese remainder theorem. Indeed, timings for implementations using LiDIA show that the PkQ cryptosystem is about 2.4 times faster than the RSA cryptosystem with the Chinese remainder theorem. The security of the PkQ cryptosystem is closely related to the RSA cryptosystem. We prove that standard attacks against the RSA cryptosystem, for example, the cycling attack and the low decryption exponent attack are not applicable to the PkQ cryptosystem. Moreover, to implement the PkQ cryptosystem we do not have to prepare extra cryptographic libraries; instead, we can use the standard one for the RSA cryptosystem. We can easily implement the PkQ cryptosystem in an environment designed for the RSA cryptosystem. The Nk cryptosystem is constructed over Z/nkZ, where n is the RSA modulus and k is a positive integer. The features of the Nk cryptosystem are as follows: We can encrypt a message which is several time larger than the RSA modulus. We can prove that breaking the second block of the Nk cryptosystems is as hard as breaking the original RSA cryptosystem. The decryption time of the first block is dominant, because after the first block we only calculate several basic operations to decrypt blocks after the first one. Even if a message is several times longer than a public-key n, we can encrypt the message fast without additionally using a symmetry-key cryptsystem.