## Abstract

We discuss the discrete logarithm problem over the class group Cl(Δ) of an imaginary quadratic order O_{Δ}, 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_{Δ}[1/2, c] and is far less efficient than the number field sieve with L_{p}[1/3, c] to compute logarithms in IF*_{p}. Thus one can choose smaller parameters to obtain the same level of security. It is an open question whether there is an L_{Δ}[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 O_{Δp}such that Δ_{p} = Δ_{1}p^{2} and the class number of the maximal order h(Δ_{1}) = 1, and we will show that there is an L_{Δp}[1/3, c] lgorithm to compute discrete logarithms over the class group Cl(Δ_{p}). The logarithm problem in Cl(Δ_{p}) can be reduced in (expected) O(log^{3} p) bit operations to the logarithm problem in IF*_{p} (if (Δ_{1}/ p) = 1) or IF *_{p2} (if (Δ_{1}/ p) = -1) respectively. This result implies that the recently proposed efficient DSA-analogue in totally non-maximal imaginary quadratic order O_{Δp} [21] are only as secure as the original DSA scheme based on finite fields and hence loose much of its attractiveness.

Original language | English |
---|---|

Title of host publication | Advances in Cryptology - ASIACRYPT 1999 - International Conference on the Theory and Application of Cryptology and Information Security, Proceedings |

Editors | Kwok Yan Lam, Eiji Okamoto, Chaoping Xing |

Publisher | Springer Verlag |

Pages | 220-231 |

Number of pages | 12 |

ISBN (Print) | 3540666664, 9783540666660 |

DOIs | |

Publication status | Published - 1999 |

Externally published | Yes |

Event | 5th International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 1999 - Singapore, Singapore Duration: Nov 14 1999 → Nov 18 1999 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 1716 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 5th International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 1999 |
---|---|

Country/Territory | Singapore |

City | Singapore |

Period | 11/14/99 → 11/18/99 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- General Computer Science