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

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

• Can anyone help me? Can I start a bounty? Mar 3, 2020 at 9:47
• The key to proving this will probably be that OAEP essentially turns any message into an "unrelated" random string (in the ROM), so a proof likely would have to show how well ElGamal hides a "random message". Mar 5, 2020 at 11:59

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.

• "However, that requires an iterative process to transform a practical message into a suitable $m$, and back on the decryption side." - actually, it can be done easier than that - actually encrypt $m^2$ (and do the modular square root on decryption); if we restrict the message space to $[1, (p-1)/2]$, decryption works (and avoids this specific distinguisher). Of course, OAEP is a lot easier to do... Apr 15, 2020 at 16:42
• @poncho: other than poncho's nice squaring technique, does it have a name, or is that to be attributed to late 198x folklore?
– fgrieu
Apr 15, 2020 at 16:54
• I like the term "poncho's nice squaring technique" :-). Seriously, squaring is a well known way to map random values to QRs; I wouldn't know who first suggested it... Apr 15, 2020 at 17:01