How can I prove that ElGamal encryption in $\mathbb{Z}_p^*$ with OAEP padding is ind-CPA secure?

Question

How I can prove that ElGamal encryption in $\mathbb{Z}_p^*$ with Optimal Asymmetric Encryption Padding (OAEP) is IND-CPA secure?

Answer 1

This is not a full answer: I only motivate the use of OAEP on top of ElGamal encryption.

ElGamal encryption as stated in modern literature, that is with message in a group where the Decisional Diffie-Hellman problem is hard, is demonstrably CPA-secure. That does not hold for the original scheme in Taher ElGamal's A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, in proceedings of Crypto 1984, even with the obviously necessary and minor correction of excluding $m=0$ from the message space, which we do hereafter.

The original ElGamal encryption scheme uses as public parameters a large prime $p$ and a primitive element $\alpha$ of $\Bbb Z_p^*$ (the multiplicative group modulo $p$). Thus $x\mapsto \alpha^x\bmod p$ is a bijection over $[1,p)$. Insuring that $p-1$ has a large prime factor makes reversing this function (the Discrete Logarithm Problem) hard.

Recipient B chooses a random secret private key $x_B\in[1,p)$, computes and publishes his public key $y_B=\alpha^{x_B}\bmod p$.

Sender A, wanting to encipher a secret message $m\in[1,p)$ to B, picks a random secret $k\in[1,p)$, computes the secret key $K={y_B}^k\bmod p$, computes $c_1=\alpha^k\bmod p$ then $c_2=K\,m\bmod p$, and sends ciphertext $(c_1,c_2)$ to B.

Recipient B receives $(c_1,c_2)$, and deciphers¹ per $m={c_1}^{p-1-x_B}\,c_2\bmod p$. This works because $K={c_1}^{x_B}\bmod p$.

Observe that given $y=\alpha^x\bmod p$ with $y\in[1,p)$, we can determine with certainty if $x$ is odd or even: we compute $y^{(p-1)/2}\bmod p$ and that's $1$ when $x$ is even, $p-1$ when $x$ is odd. Expressed using the Legendre symbol for $y$ modulo $p$, that's $\left(\frac yp\right)=+1$ when $y^{(p-1)/2}\bmod p=1$ (even $x$), or $\left(\frac yp\right)=-1$ when $y^{(p-1)/2}\bmod p=p-1$ (odd $x$). This allows an adversary to win the IND-CPA game with certainty, by:

• Choosing two messages $m_0$ and $m_1$ with $\left(\frac{m_0}p\right)=+1$ and $\left(\frac{m_1}p\right)=-1$. The choice of $m_1=1$ and $m_2=\alpha$ will do, or it can be found by trial and error meaningful messages until two have different Legendre symbols.
• Submiting $m_0$ and $m_1$ to the challenger, which picks $b\in\{0,1\}$ at random, sets $m=m_b$, computes and reveals $(c_1,c_2)$ as above.
• Finding $b$ per the following table: $$\begin{array}{ccc|c} \left(\frac{y_B}p\right)&\left(\frac{c_1}p\right)&\left(\frac{c_2}p\right)&b\\ \hline -1&-1&-1&0\\ -1&-1&+1&1\\ \text{any}&+1&-1&1\\ \text{any}&+1&+1&0\\ +1&\text{any}&-1&1\\ +1&\text{any}&+1&0\\ \end{array}$$

This works because $\left(\frac{y_B}p\right)=-1\iff x_B\text{ odd}$ and $\left(\frac{c_1}p\right)=-1\iff k\text{ odd}$. Since $K=\alpha^{x_B\,k}$ that allows to determine $\left(\frac Kp\right)$, which is $-1$ if and only if both $\left(\frac{c_1}p\right)=-1$ and $\left(\frac{c_1}p\right)=-1$. And then $\left(\frac{c_2}p\right)=\left(\frac Kp\right)\,\left(\frac{m_b}p\right)$ allows to conclude on $b$.

---

Further leaks can occur when $(p-1)/2$ has small prime factors. But when choosing $p$ such that $(p-1)/2$ is prime ($p$ a so-called safe prime), the strategy of restricting to $m$ with $\left(\frac mp\right)=+1$ is believed to make ElGamal encryption IND-CPA secure² against classical computers. That can be done without an iterative process to transform a practical message into a suitable $m$, and back on the decryption side: see poncho's nice squaring technique in comment.

---

The motivation of using OAEP padding in order to prepare the message to form $m$ in ElGamal encryption are²:

• it is non-iterative, and faster than even poncho's nice squaring technique;
• it should make ElGlamal encryption IND-CPA secure, because the partial information that may leak won't be enough to allow the adversary to undo the padding;
• unless I err once more, it should also make ElGlamal encryption IND-CCA1 secure (but not IND-CCA2 secure for the reason pointed there, even if we add range checks on $c_1$ and $c_2$ on decryption).

But I have no proof for the IND-CPA and IND-CCA1 assertions.

---

¹ The paper computes $K={c_1}^{x_B}\bmod p$, then asks to "divide $c_2$ by $K$ to recover $m$". That requires computation of a modular inverse, perhaps using the extended Euclidean algorithm.

² The complexity is believed super-polynomial in $\log p$, including in a known dip down in security for $p$ of a special form $r^e\pm s$ with $r$ and $s$ small, which enables SNFS.