In ElGamal encryption scheme, in order to achieve IND-CPA security, one must use a group where the DDH problem is assumed to be hard. As this answer suggests, one way to achieve that is the following:

When working in $\Bbb Z^*_p$, let $p$ be a safe prime $p=2q+1$, where $q$ is also prime, let $g$ be a generator of the cyclic subgroup of quadratic residues of order $q$ and restrict the message space to quadratic residues only.

My question is: lets say my given message space is $\Bbb Z_p^*$, where $p$ is a prime, but not a safe prime. How can I embed this message space into one that can be encrypted with ElGamal scheme so that all the properties of ElGamal (IND-CPA security, homomorphicity) still hold?

  • $\begingroup$ Can we at least assume that the discrete logarithm is hard in $\Bbb Z_p^*$, including that $p-1$ has a large prime factor? Is strict homomorphicity (for multiplication modulo $p$) to be preserved for all elements of $\Bbb Z_p^*$? $\endgroup$
    – fgrieu
    May 29 '18 at 12:42
  • 1
    $\begingroup$ We can assume that $p-1$ has a large prime factor (but again, $p$ is not of the form $2q+1$) and yes, homomorphicity should be preserved for all elements. $\endgroup$
    – Lumlum
    May 29 '18 at 13:20
  • $\begingroup$ for any finite field crypto system, you would not use a safe prime. You need a big prime p (e.g. > 2048 bits), where p-1 is divisible by a smaller prime q (e.g. >256 bits). $\endgroup$
    – user27950
    May 30 '18 at 4:52
  • $\begingroup$ @Cryptostase Thank you for your comment, I guess my question was formulated too restrictive. Using a safe prime is one option, but certainly not the only one. Is it that what you meant or am I missing something? $\endgroup$
    – Lumlum
    May 30 '18 at 7:40
  • $\begingroup$ With a safe prime you get an unnecessarily large private key size. I am not aware of such a real world crypto system. Can you show me one? $\endgroup$
    – user27950
    May 30 '18 at 7:46

ElGamal encryption

Given a prime $p$, a quadratic residue (implicitly: modulo $p$) is defined as an $a\in\Bbb Z_p^*$ such that $\exists b\in\Bbb Z_p^*, a\equiv b^2\pmod p$. Quadratic residuosity is efficiently testable using Euler's criterion $a^{(p-1)/2}\equiv1\pmod p$.

Select a $g\in\Bbb Z_p^*$ that is a generator of the subgroup of quadratic residues, of order $q=(p-1)/2$. That is, $g^q\equiv1\pmod p$; and $g^{q/r}\not\equiv1\pmod p$ for all prime(s) $r$ dividing $q$.

The private key is $x\in\Bbb Z_q$, a secret drawn uniformly randomly.

The public key is $h\in\Bbb Z_p^*$ computed as $h=g^x\bmod p$.

Define encryption of $m\in\Bbb Z_p^*$ as $E(m)=(c_1,c_2)=(g^y\bmod p,h^y\,m\bmod p)$ with $y\in\Bbb Z_q$ drawn uniformly randomly for each encryption, then discarded. And define the matching decryption $D(c_1,c_2)={c_1}^{q-x}\,c_2\bmod p$. It holds $D(E(m))=m$.

The encryption system is multiplicatively homomorphic: multiplying any number of ciphertexts componentwize in $\Bbb Z_p^*$ yields a pair which decrypts to the product of the plaintexts in $\Bbb Z_p^*$.

For strong medium-term security, $p$ should be an at-least 2000-bit prime not generated to have $p=t^k\pm s$ for small $s$ and $t$, and $q=(p-1)/2$ should have an at-least 250-bit prime factor.

When restricting to $m$ that are quadratic residues, ElGamal encryption is then believed to have IND-CPA security. A problem otherwise is that $E(m)$ leaks whether $m$ is a quadratic residue, as the residuosity of $c_2$.

Note: other descriptions of ElGamal encryption make $g$ a generator of the full $\Bbb Z_p^*$, of order $q=p-1$. Similarly, $E(m)$ leaks whether $m$ is a quadratic residue, as the residuosity of $c_1\,c_2\bmod p$.

Fixing the residuosity leak while keeping homomorphicity

Find the smallest $u>1$ that is not a quadratic residue. Check that $u^4<p$, which will hold for overwhelmingly most large $p$.

Define encryption $$\begin{align}E'(m)&=((c_1,c_2),(c'_1,c'_2))\\ &=\begin{cases} (E(m),E(1))&\text{when }m\text{ is a quadratic residue}\\ (E(m\,u\bmod p),E(u^2))&\text{otherwise}\\ \end{cases}\end{align}$$ and define $D'((c_1,c_2),(c'_1,c'_2))=D(c_1,c_2)\,\left(\sqrt{D(c'_1,c'_2)}\right)^{-1}\bmod p$, failing if the argument to the square root is not the square of an integer.

For any $m\in\Bbb Z_p^*$ it holds $D'(E'(m))=m$.

The encryption system is multiplicatively homomorphic within a limit: multiplying up to $l=\lfloor\log(p)/2\log(u)\rfloor\ge2$ ciphertexts componentwize in $\Bbb Z_p^*$ yields a pair of pairs which decrypts to the product of the plaintexts in $\Bbb Z_p^*$. If $u=2$ is not a quadratic residue, we can multiply at least 1023 ciphertexts for 2048-bit $p$.

That encryption is CPA-secure, because ElGamal encryption $E$ is only used on messages that are quadratic residues.


  • The detection of decryption failure, if leaked by the decrypter, can be abused into a decryption oracle. Don't allow that!
  • In homomorphic use, the decrypter (with the private key) can compute how many plaintexts that are not quadratic residues have been multiplicatively combined, as $\log({D(c'_1,c'_2)})/2\log(u)$.


  • If the later property is undesirable, what the decrypter learns beside the deciphered product can be limited to learning a crude approximation of how many plaintexts that are not quadratic residues have been multiplicatively combined: change $(E(m\,u\bmod p),E(u^2))$ to $(E(m\,u^{-1}\bmod p),E(u^{-2}\bmod p))$ with probability 50%, and adjusts decryption to deal with $D(c'_1,c'_2)^{-1}\bmod p$ being a square (also, the order of $u$ must be large enough). Further, by changing $(E(m),E(1))$ to $(E(m\,u^2\bmod p),E(u^4))$ or $(E(m\,u^{-2}\bmod p),E(u^{-4}\bmod p))$ with probability 25% for each of the alternatives, the proportion of quadratic residues is masked (but $l$ is halved).
  • It is possible to massively increase $l$ by having the decrypter solve $D(c'_1,c'_2)\equiv(u^2)^x\pmod p$ for small $x$ or $|x|$ (e.g. using Baby Step / Giant Step), then compute $D(c_1,c_2)\,u^{-x}\bmod p$ (also, the order of $u$ must be large enough). Still, homomorphically computing sizable powers (e.g. using square and multiply) is out of reach.
  • If use of another cryptosystem and key pair is game, we can replace $(c'_1,c'_2)$ with a Paillier ciphertext for plaintext 0 or 1 according to if $m$ is a quadratic residue or not. That simplifies decryption while keeping a multiplicative homomorphic property (with a different modulus for the Paillier component), and $l$ skyrockets. A variant of Paillier accepting negative plaintext can be used to mask from the decrypter the proportion (and to some degree the number) of plaintexts that are not quadratic residues.

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.