5
$\begingroup$

What are the properties a generator $g$ should have to be secure for ElGamal signatures (original scheme)?

I am aware that it is poorly chosen and not secure when $g|p-1$ or $g^{-1}|p-1$, where $p$ is the large prime so that $g$ generates $Z_p^*$ and $g$ has maximum order (that is, $p-1$).

Are there other properties one should consider? Additionally, should $g$ be picked randomly over $[1..p-1]$ or is it safe to choose it to be a small integer to start with?

$\endgroup$
2
$\begingroup$

First you should know that Elgamal encryption and signature security is based on DDH problem (Decisional Diffie Hellman) which is tractable in some groups that CDH problem is believed to be hard (Computational Diffie Hellman). As in the case of $\mathbb{Z_q}$ in which CDH is believed to be hard but DDH is apparently tractable.

Let $p = 2p_1 + 1$ where both $p$ and $p_1$ are prime. Let $Q_p$ be the subgroup of quadratic residues in $\mathbb{Z_p}$. $Q_p$ is a cyclic group of prime order itself in which DDH assumption is believed to be hard. This group and some other groups in which DDH problem is intractable are mentioned in this paper by Dan Boneh.

Any randomly chosen primitive element in $\mathbb{Z_p}$, say $g$, to the power of two ($g_1=g^2$) is a 'safe' generator for the subgroup of quadratic residues in $\mathbb{Z_p}$ (it is defined above as $Q_p$). A primitive element of $\mathbb{Z_q}$ is an element which are relatively prime to $p$. ($gcd(g,p)=1$)

|improve this answer|||||
$\endgroup$
  • $\begingroup$ What you write is true for semantic security of ElGamal encryption. But security oft ElGamal signatures is not related to the DDH assumption in the used group. It would be more than surprising if unforgeability of ElGamal signatures could be reduced to a decisional problem instead of a computational one. $\endgroup$ – DrLecter Feb 21 '14 at 21:46

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.