A signature scheme based on the intractability of computing roots (Q1862440)

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.