Towards practical non-interactive public-key cryptosystems using non-maximal imaginary qua\-dratic orders (Q1412255)

The notion of identity based cryptosystem was proposed by \textit{A. Shamir} [Lect. Notes Comput. Sci. 196, 47--53 (1985; Zbl 1359.94626)]. The authors present a new non-interactive public-key distribution system based on the discrete logarithm (DL) problem using the class group of a non-maximal imaginary quadratic order. The main idea behind the method is encapsulated in the following result (Theorem 1): Let \(G,H\) be finite abelian groups and \(\Phi:G\to H\) a homomorphism. Then the DL problem in \(G\) can be reduced to one DL computation in \(\text{Ker}(\Phi)\) and two DL computations in \(H\) via two applications of \(\Phi\), \(O(\log| H| )\) group operations in \(G\) and \(O((\log| G| )^2)\) bit-operations. In the application \(G= \text{Cl}(\Delta_f)\), the class group of a non-maximal imaginary quadratic order with conductor \(f\), \(H=\text{Cl} (\Delta_1)\), the class group of the maximal order. If \(G\) is cyclic and \(| H| \) known, then one can avoid one DL computation in \(H\). Thus DL computations in \(\text{Cl} (\Delta_f)\) can be reduced to DL computations in \(\text{Cl}(\Delta_1)\) and the DL computation in \(\text{Ker}(\Phi^{-1}_{\text{Cl}})\). Moreover, the authors show that the latter computation reduces to the DL computations in a small number of finite fields. The reader is kindly referred to the paper for more details.