Reducing Logarithms in Totally Non-maximal Imaginary Quadratic Orders to Logarithms in Finite Fields

We discuss the discrete logarithm problem over the class group Cl(Δ) of an imaginary quadratic order ${\cal O}_\Delta$, which was proposed as a public-key cryptosystem by Buchmann and Williams [8]. While in the meantime there has been found a subexponential algorithm for the computation of discrete logarithms in Cl(Δ) [16], this algorithm only has running time $L_{\Delta}[\frac{1}{2},c]$ and is far less efficient than the number field sieve with $L_p[\frac{1}{3},c]$ to compute logarithms in $\mathbb{F}_p^*$. Thus one can choose smaller parameters to obtain the same level of security. It is an open question whether there is an $L_{\Delta}[\frac{1}{3},c]$ algorithm to compute discrete logarithms in arbitrary Cl(Δ).In this work we focus on the special case of totally non-maximal imaginary quadratic orders ${\cal O}_{\Delta_p}$ such that Δ _p = Δ₁p2 and the class number of the maximal order h(Δ₁)=1, and we will show that there is an $L_{\Delta_p}[\frac{1}{3},c]$ algorithm to compute discrete logarithms over the class group Cl(Δ _p ). The logarithm problem in Cl(Δ _p ) can be reduced in (expected) O(log3p) bit operations to the logarithm problem in $\mathbb{F}_p^*$ (if $(\frac{\Delta_1}{p})=1$) or $\mathbb{F}_{p^2}^*$ (if $(\frac{\Delta_1}{p})=-1$) respectively. This result implies that the recently proposed efficient DSA-analogue in totally non-maximal imaginary quadratic order ${\cal O}_{\Delta_p}$ [21] are only as secure as the original DSA scheme based on finite fields and hence loose much of its attractiveness.