The Group of Signed Quadratic Residues and Applications

We 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. We 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.

We demonstrate the usefulness of our results by applying them to the Hybrid ElGamal encryption scheme (aka Diffie-Hellman integrated encryption scheme - DHIES). Concretely, we consider the security of the scheme when instantiated over the group of signed quadratic residues. It is known that, in the random oracle model, the scheme is chosenciphertext (CCA) secure under the Strong Diffie-Hellman assumption and hence, by our results, under the standard factoring assumption. We show that furthermore, in the standard model, Hybrid ElGamal is CCA secure under the higher residuosity assumption, given that the used hash function is four-wise independent. The latter result is obtained using the recent “randomness extraction framework” for hash proof systems.