Biehl, Ingrid; Buchmann, Johannes; Hamdy, Safuat; Meyer, Andreas A signature scheme based on the intractability of computing roots. (English) Zbl 1024.94009 Des. Codes Cryptography 25, No. 3, 223-236 (2002). The authors introduce RDSA, a variant of the DSA signature scheme. The security of RDSA is based upon the intractability of extracting roots in a finite Abelian group. In fact, they prove that RDSA is secure against an adaptively chosen message attack in the random oracle model if and only if computing roots in the underlying group is intractable. At the end of the paper they present an efficient implementation of RDSA in class groups of imaginary quadratic orders, which they call IQ-RDSA. They also give a table of timings in milliseconds for IQ-RDSA, as well as public key sizes given in bits. Reviewer: Richard A.Mollin (Calgary) Cited in 1 ReviewCited in 11 Documents MSC: 94A62 Authentication, digital signatures and secret sharing 11T71 Algebraic coding theory; cryptography (number-theoretic aspects) 11R29 Class numbers, class groups, discriminants Keywords:signature schemes; RDSA; DSA; root problem; class groups PDFBibTeX XMLCite \textit{I. Biehl} et al., Des. Codes Cryptography 25, No. 3, 223--236 (2002; Zbl 1024.94009) Full Text: DOI