# Is 2 a safe generator for elgamal encryption

From what I understand here https://en.wikipedia.org/wiki/ElGamal_encryption and here: https://ritter.vg/security_adventures_elgamal.html, any number can be used as a generator. Is there something wrong with using 2 as the generator? Are there other constraints?

• If 2 is a generator of a sufficiently large (sub)group then using it is 100% fine. – SEJPM Oct 31 '16 at 23:01

As far as we know, any generator of a given subgroup of $\mathbb Z_p$ is about as safe as any other one for ElGamal encryption; and $2$ is no exception. Argument (this is not a proof): ElGamal encryption is closely related to (and not harder than) the Discrete Logarithm Problem in that subgroup, and consistently solving the DLP with generator $2$ in the subgroup of $\mathbb Z_p$ that it generates is not much harder than solving the DLP with any other generator $g$ of the same subgroup. Close-to-a-proof of the later: If we could consistently solve the DLP with generator $2$ in that subgroup, and knew that subgroup's order $r$, we likely could solve $2^y\equiv g\pmod p$ for $y$, and then for $a$ in the subgroup we could consistently solve $g^x\equiv a\pmod p$ for $x$, by first solving $2^z\equiv a\pmod p$ for $z$ using the hypothetical method, then solving $z=x\,y\bmod r$ for $x$ which is easy.
However if would be wrong to conclude that $2$ can safely be used as the generator for any large enough $p$. Common wisdom is to use a subgroup which order $r$ is a large prime $q$ of at least $2b$ bits for security against effort $O(2^b)$ (and otherwise sound choices). It is not enough that the order of the subgroup is large: if $r$ was smooth, the Pohlig-Hellman algorithm would apply, and allow plaintext recovery for any ciphertext. Note: I defer making a statement as to what exactly are the necessary conditions on $r$ and messages to reach IND-CPA security until I'm sure of what I write!
Update: a stronger argument in favor of the first assertion in this answer is given by poncho: being able to recover plaintext encrypted by ElGamal with generator $2$ (always, or extremely consistently) implies ability to do so with any generator $g$ of that same subgroup (heuristically always, or with possibly sizable odds), even if the DLP itself was insurmountable.
• Actually, you can strengthen your argument by noting that a) recovering a ElGamal-encrypted text with the public key is actually equivalent to the computational Diffie-Hellman (cDH) problem, and b) if you can solve the cDH problem with generator 2 consistently, you can solve it with any generator with the same sized subgroup. This isn't quite proof, because the reduction involves $O(\log p)$ cDH problems with generator 2, and so it doesn't work if your g=2 Oracle fails with moderate probability; however, it's a stronger argument. – poncho Nov 1 '16 at 13:08