4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Can anyone help me? Can I start a bounty? $\endgroup$ – tarit goswami Mar 3 '20 at 9:47
  • $\begingroup$ 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". $\endgroup$ – SEJPM Mar 5 '20 at 11:59
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ "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... $\endgroup$ – poncho Apr 15 '20 at 16:42
  • $\begingroup$ @poncho: other than poncho's nice squaring technique, does it have a name, or is that to be attributed to late 198x folklore? $\endgroup$ – fgrieu Apr 15 '20 at 16:54
  • 1
    $\begingroup$ 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... $\endgroup$ – poncho Apr 15 '20 at 17:01

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.