International Association for Cryptologic Research
The authors consider the cryptographic group of signed quadratic residues. This group is particularly useful for cryptography since it is a \"Gap-group,\" in which the computational problem (i.e., computing square roots) is as hard as factoring, while the corresponding decisional problem (i.e., recognizing signed quadratic residues) is easy. They are able to show that under the factoring assumption, the strong Diffie-Hellman assumption over the signed quadratic residues holds. That is, in this group the Diffie-Hellman problem is hard, even in the presence of a decisional Diffie-Hellman oracle.