15.3: ElGamal Encryption

ElGamal encryption is a public-key encryption scheme that is based on DHKA.

Construction $15.6$ (ElGamal)

The public parameters are a choice of cyclic group $\mathbb{G}$ with $n$ elements and generator $g$.

Figure $\PageIndex{1}$: Copy and Paste Caption here. (Copyright; author via source)

The scheme satisfies correctness, since for all $M$:

$$\begin{aligned} \operatorname{Dec}(s k, \operatorname{Enc}(p k, M)) &=\operatorname{Dec}\left(s k,\left(g^{b}, M \cdot A^{b}\right)\right) \\ &=\left(M \cdot A^{b}\right)\left(\left(g^{b}\right)^{a}\right)^{-1} \\ &=M \cdot\left(g^{a b}\right)\left(g^{a b}\right)^{-1}=M \end{aligned}$$

Security

Imagine an adversary who is interested in attacking an ElGamal scheme. This adversary sees the public key $A=g^{a}$ and a ciphertext $\left(g^{b}, M g^{a b}\right)$ go by. Intuitively, the Decisional Diffie-Hellman assumption says that the value $g^{a b}$ looks random, even to someone who has seen $g^{a}$ and $g^{b}$. Thus, the message $M$ is masked with a pseudorandom group element - as we’ve seen before, this is a lot like masking the message with a random pad as in one-time pad. The only change here is that instead of the xor operation, we are using the group operation in $\mathbb{G}$.

More formally, we can prove the security of ElGamal under the DDH assumption:

Claim $15.7$

 

If the DDH assumption in group $\mathbb{G}$ is true, then ElGamal in group $\mathbb{G}$ is CPA$-secure.

Proof

It suffices to show that ElGamal has pseudorandom ciphertexts when the calling program sees only a single ciphertext. In other words, we will show that $\mathcal{L}_{\text {pk-ots\$-real }} \approx \mathcal{L}_{\text {pk-ots\$-rand, }}$, where these libraries are the $\mathcal{L}_{\text {pk-cpa\$-}\star}$ libraries from Definition $15.2$ but with the single-ciphertext restriction used in Definition 15.4. It is left as an exercise to show that $\mathcal{L}_{\text {pk-ots\$-real }} \approx \mathcal{L}_{\text {pk-ots\$-rand }}$ implies CPA$ security (which in turn implies CPA security); the proof is very similar to that of Claim $15.5.$

The sequence of hybrid libraries is given below:

Figure $\PageIndex{1}$: Copy and Paste Caption here. (Copyright; author via source)	The starting point is the $\mathcal{L}_{\text {pk-ots } \$ \text {-real library, shown here }}$ with the details of ElGamal filled in.
Figure $\PageIndex{1}$: Copy and Paste Caption here. (Copyright; author via source)	The main body of QUERY computes some intermediate values $B$ and $A^{b}$. But since those lines are only reachable one time, it does not change anything to precompute them at initialization time.
Figure $\PageIndex{1}$: Copy and Paste Caption here. (Copyright; author via source)	We can factor out the generation of $A, B, C$ in terms of the $\mathcal{L}_{\text {dh-real}}$ library from the Decisional Diffie-Hellman security definition (Definition 14.5).
Figure $\PageIndex{1}$: Copy and Paste Caption here. (Copyright; author via source)	Applying the security of $\mathrm{DDH}$, we can replace $\mathcal{L}_{\text {dh-real }}$ with $\mathcal{L}_{\text {dh-rand }}$.
Figure $\PageIndex{1}$: Copy and Paste Caption here. (Copyright; author via source)	The call to DHQUERY has been inlined.
Figure $\PageIndex{1}$: Copy and Paste Caption here. (Copyright; author via source)	As before, since the main body of QUERY is only reachable once, we can move the choice of $B$ and $C$ into that subroutine instead of at initialization time.
Figure $\PageIndex{1}$: Copy and Paste Caption here. (Copyright; author via source)	When $b$ is sampled uniformly from $\mathbb{Z}_{n}$, the expression $B=g^{b}$ is a uniformly distributed element of $\mathbb{G}$. Also recall that when $C$ is a uniformly distributed element of $\mathbb{G}$, then $M \cdot C$ is uniformly distributed $-$ this is analogous to the one-time pad property (see Exercise 2.5). Applying this change gives the library to the left.

In the final hybrid, the response to QUERY is a pair of uniformly distributed group elements $(B, X)$. Hence that library is exactly $\mathcal{L}_{\mathrm{pk} \text {-ots\$-rand}}$, as desired.