Design And Analysis Of Several Classes Of Fast Public Key Cryptosystems

The traditional public-key ciphers suffer from a drawback that their speed is relatively low, which hampers the further applications of public key cryptography and also motivates the cryptographic community to design fast public-key cryptosystems. In the area of fast public-key cryptography, the author obtains the following main results.(1) A new kind of easy knapsack-type problems is found. A knapsack-type public-key encryption scheme is constructed based on the problem. This is the first probabilistic knapsack-type encryption scheme. It is shown that the cryptosystem is secure against low-density attacks and the simultaneous Diophantine approximation attacks. Furthermore, the computational complexities of the encryption and the decryption algorithms of the cryptosystem are quadratic.(2) A weak key of the RSA cryptosystem is found. It turns out that the modulus of the RSA cryptosystem is easy to factor if the the ratio of the two prime factors of the modulus can be well approximated by a small fraction.(3) A fast public-key encryption scheme is developed by using the Chinese remainder theorem. It is pointed out that the attacker must solve two number-theoretic intractable problems, namely the integer factorization and simultaneous Diophantine approximation problems, to recover the trapdoor information.(4) The RSA problem is generalized by introducing the generalized-RSA problem. The relations between the RSA problem and the G-RSA related problems are given. A public-key cryptosystem GRSA is proposed, which is based on the G-RSA problem and features double trapdoor decryption mechanism. It is proven that the GRSA is one-way if and only if the computational G-RSA problem is intractable, and the semantic security of the GRSA cryptosystem under the chosen-plaintext attack model is correct if and only the decisional G-RSA problem is infeasible.(5) A public-key cryptosystem based on two cryptographic intractable assumptions is proposed. The security of the proposed cryptosystem is based on the integer factorization and the simultaneous Diophantine approximation problems. It only takes quadratic bit complexity for the cryptosystem to perform an encryption/decryption operation.(6) A public-key cryptosystem is proposed by using a special combinatorial problem defined over the matrix ring. The security of the scheme is related to but not directly dependent upon the integer factorization problem.(7) This dissertation considers the root extraction problem defined over braid groups, and constructs a digital signature scheme. It is shown that the attacker can forge a signature if and if he can solve the root extraction problem defined over braid groups. Furthermore, the signature scheme is modified as an identity-based signature scheme.(8) The Naccache-Stern cryptosystem is cryptanalyzed. It is pointed out that the decryption of the cryptosystem can be viewed as a group factorization problem. The success probability of the attack relies on with what probability it can successfully transform a random integer into a smooth number.(9) The security of the cryptosystem proposed at ACISP 2000 is analyzed. The relation of the security of the cryptosystem with the simultaneous Diophantine approximation problem and the shortest vector problem over lattices is clarified.