New designing of cryptosystems based on quadratic fields

This paper proposes a method to construct new kind of non-maximal imaginary quadratic order (NIQO*) by combining the technique of Diophantine equation and the characters of non-maximal imaginary quadratic order. It is proved that in the class group of this new kind of NIQO*, it is very easy to design provable secure cryptosystems based on quadratic field (QF). With the purpose to prove that this new kind of QF-based cryptosystems are easy to implement, two concrete schemes are presented, i.e., a Schnorr-like signature and an ElGamel-like encryption, by using the proposed NIQO*. In the random oracle model, it is proved that: (1) under the assumption that the discrete logarithm problem over class groups (CL-DLP) of this new kind of NIQO*is intractable, the proposed signature scheme is secure against adaptive chosen-message attacks, i.e., achieving UF-CMA security; (2) under the assumption that the decisional Diffie-Hellman problem over class groups (CL-DDH) of this new kind of NIQO* is intractable, the enhanced encryption in this paper is secure against adaptive chosen-ciphertext attacks, i.e., reaching IND-CCA2 security.