1
$\begingroup$

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?

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

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – poncho Nov 1 '16 at 13:08
  • 1
    $\begingroup$ A subgroup of just a large prime order order would be a better choice. There is a chance for an adversary to play "distinguish" games in a subgroup of an order with a small factor, if that matters. $\endgroup$ – Vadym Fedyukovych Nov 1 '16 at 18:13

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.