How to encode messages in $\Bbb Z_p^*$ to be encrypted with ElGamal scheme?

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?

• 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^*$?
– fgrieu
May 29 '18 at 12:42
• 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. May 29 '18 at 13:20
• 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).
– user27950
May 30 '18 at 4:52
• @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? May 30 '18 at 7:40
• 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?
– 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.

Notes:

• 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)$.

Extensions:

• 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.