El-Gamal Public Key Encryption

Suppose there are two parties Alice and Bob with private keys: $a$ and $b$ in group $G$, then El-Gamal cryptosystem allows Bob to share a message $m$ as ciphertext and Alice to decrypt it.

Scheme $\Pi (\text{Gen,Enc,Dec})$:

• $\text{Gen}(1^n)\to (\mathbb{G},g,q,h)$: Choose generator $g$, with order $q$. Choose $x\in {\mathbb{Z}}_q$, calculate $h=g^x$. $pk:=(g,q,h),sk:=(g,q,x)$.
• $\text{Enc}(pk,m)\to (c_1,c_2)$: Choose $y\in {\mathbb{Z}}_q$, then $c_1\leftarrow g^y,c_2\leftarrow m\cdot h^y$.
• $\text{Dec}(sk,c)\to m$: compute $\frac{c_2}{c_1^x}=m\cdot \frac{g^{xy}}{g^{y^x}}=m$

El-Gamal PKC depends on DDH for it’s hardness and any adversary who has oracle that decrypts ElGamal ciphertexts, can use it to solve Diffie-Hellman problem. Prove that, if DDH is hard relative to $\mathcal{G}$, then $\mathrm{Pr}[{\text{PubK}}_{\mathcal{A},\Pi }^{\text{eav}}(n)=1]\le \frac{1}{2}+\text{negl}(n)$.

We’ll show that scheme is EAV secure, and for PK scheme, all EAV secure schemes are CPA secure as well.

• Run a reduction experiment using adversary ${\mathcal{A}}^{\prime }$ that simulates encryption oracle for $\mathcal{A}$, with input $(\mathbb{G},g,q,h_1=g^x,h_2=g^y,h_3)$ where $h_3\leftarrow \{g^z,g^{xy}\}$, where $z\leftarrow {\mathbb{Z}}_q$.
• Sets $pk=(\mathbb{G},g,q,h_1)$. Runs $\mathcal{A}\to (m_0,m_1)$.
• Choose a uniform bit $b\in \{0,1\}$, and output ciphertexts as $c_1=h_2,c_2=m_b\cdot h_3$
• $\mathcal{A}$ outputs $b^{\prime }\in \{0,1\}$, ${\mathcal{A}}^{\prime }$ outputs $b^{\prime }$
• if $b^{\prime }=b$, output 1, else 0

Now, there are two possibilities, $h_3=g^{xy}$ or $h_3=g^z$, let’s analyse both:

• When $z\leftarrow {\mathbb{Z}}_q$, then view of $\mathcal{A}$ run as a subroutine by ${\mathcal{A}}^{\prime }$ is identical to that of an experiment ${\Pi }^{\prime }$, where $\mathcal{A}$ has no way of decrypting the ciphertext $c_2$, and can only guess the bit. Thus $\mathrm{Pr}[{\mathcal{A}}^{\prime }(g,q,h_1,h_2,h_3=g^z)=1]=\mathrm{Pr}[{\text{PubK}}_{\mathcal{A},{\Pi }^{\prime }}^{\text{eav}}(n)=1]=\frac{1}{2}$.
• When $z\leftarrow {\mathbb{Z}}_q$, then view of $\mathcal{A}$ run as a subroutine by ${\mathcal{A}}^{\prime }$ is identical to that of EAV experiment. Thus, $\mathrm{Pr}[{\mathcal{A}}^{\prime }(g,q,h_1,h_2,h_3=g^{xy})=1]=\mathrm{Pr}[{\text{PubK}}_{\mathcal{A},\Pi }^{\text{eav}}(n)=1]$
• $\mathrm{Pr}[\mathcal{A}(\mathbb{G},q,g,g^x,g^y,g^z)=1]-\mathrm{Pr}[\mathcal{A}(\mathbb{G},q,g,g^x,g^y,g^{xy})=1]\le \text{negl}(n)$, we know from DDH assumption.
• $\frac{1}{2}-\mathrm{Pr}[{\text{PubK}}_{\mathcal{A},\Pi }^{\text{eav}}(n)=1]\le \text{negl}(n)$