In Elgamal, the generator $g$ is always quadratic non-residue modulo $p$, where $p$ is a safe prime and the inverse of $g$ can also be generator?

Can I prove it? I can't come up with it at all.

  • 1
    $\begingroup$ Welcome to crypto.se. It would help if you described in your question what you've already tried, and where you're stuck. $\endgroup$
    – archie
    Nov 1 '13 at 1:51

Ok, I assume that you speak of ElGamal working in $Z_p^*$ and you mean that $g$ is a quadratic residue modulo $p$.

The problem with ElGamal, when taking some arbitrary prime $p$ is that you cannot achieve IND-CPA security.

Recall, in the IND-CPA security game, the adversary chooses two messages $m_0$ and $m_1$, obtains the ciphertext of $m_b$, where $b$ is the result of a coin flip, and has to guess with non negligible probability better than $1/2$ which message has been encrypted.

The problem is that you can use the Legendre symbol to efficiently decide quadratic residuosity modulo $p$. Now, if an attacker chooses one message to be a quadratic residue and one to be a non-residue, then the adversary with the knowledge of the quadratic residuosity of $g$ has non negligible advantage to guess the correct message (I guess this is homework so I do not discuss this in details).

If choosing $p$ to be a safe prime of the form $p=2q+1$ where $q$ is also prime, then the order $q$ subgroup of $Z_p^*$ represents the cyclic subgroup of quadratic residues (this is not hard to see). Then, if you choose $g$ to be a generator of this subgroup and restrict the message space to be quadratic residues, for obvious reasons, you achieve IND-CPA security.

Now, to your last point (inverse of $g$). Note that in a group of prime order ($q$ in our case) every element is a generator. This group of quadratic residues of order $q$ is a subgroup of $Z_p^*$. If you recall basic group theory then you may remember the definiton of a subgroup: Let $G$ be a group and let $H$ be a nonempty subset of $G$. If for all $a,b\in H$ it holds that $ab^{-1}\in H$, then $H$ is a subgroup of $G$. This means, that the inverse $g^{-1}$ of $g$ is in the subgroup and since every element in the subgroup is a generator you have what you want so show.


For El Gamal to be secure, $g$ has to generate a subgroup where the DDH problem is hard. Everything follows as a consequence of that.

As a consequence of this requirement, $g$ must generate a prime-order subgroup (if it doesn't, the DDH problem becomes easy). One way to ensure that $g$ generates a prime-order subgroup is to let $p$ be a safe prime (so that $q=(p-1)/2$ is prime too) and to choose a group element $g$ of order $q$. These choices ensure that $g$ will generate a prime-order subgroup. And if you choose $p$ and $g$ this way, then yes, $g$ will necessarily be a quadratic non-residue.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.