# 15.3: ElGamal Encryption

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

## ElGamal Encryption

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

Construction $$15.6 \quad$$ The public parameters are a choice of cyclic group $$\mathbb{G}$$ with $$n$$ elements and generator $$g$$. (ElGamal)

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, }}$$, 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: The starting point is the $$\mathcal{L}_{\text {pk-ots } \ \text {-real library, shown here }}$$ with the details of ElGamal filled in.

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.
$$(A, B, C) \leftarrow$$ DHQUERY ()
count $$=0$$
GETPK():

$$\mathcal{L}_{\mathrm{dh}-\text { real }}$$
$$\frac{\text { DHQUERY }():}{a, b \leftarrow \mathbb{Z}_{n}}$$
$$\operatorname{return}\left(g^{a}, g^{b}, g^{a b}\right)$$
We can factor out the genera-
$$\operatorname{return} A$$ tion of $$A, B, C$$ in terms of the $$\mathcal{L}_{\text {dh-real }}$$ library from the De-
$$\underline{\text { QUERY }}(M \in \mathbb{G}):$$ cisional Diffie-Hellman security
$$\operatorname{coun} t: \operatorname{coun} t+1$$ definition (Definition 14.5). if count $$>1$$ : return null $$X:=M \cdot C$$

$$(A, B, C) \leftarrow$$ DHQUERY () count $$=0$$

 $$\mathcal{L}_{\mathrm{dh} \text {-rand }}$$ $$\frac{\text { DHQUERY }():}{a, b, c \leftarrow \mathbb{Z}_{n}}$$ $$\operatorname{return}\left(g^{a}, g^{b}, g^{c}\right)$$

GETPK():

$$\operatorname{QUERY}(M \in \mathbb{G}):$$

count $$:$$ count $$+1$$ Applying the security of $$\mathrm{DDH}$$, we can replace $$\mathcal{L}_{\text {dh-real }}$$ with $$\mathcal{L}_{\text {dh-rand }}$$. if count $$>1$$ : return null $$X:=M \cdot C$$

return $$(B, X)$$

$$a, b, c \leftarrow \mathbb{Z}_{n}$$

$$A:=g^{a} ; B:=g^{b} ; C:=g^{c}$$

count $$=0$$

GETPK():

The call to DHQUERY has been inlined.

return $$A$$

QUERY $$(M \in \mathbb{G}):$$

count : count $$+1$$

if count $$>1$$ : return null $$X:=M \cdot C$$

return $$(B, X)$$

 $$a \leftarrow \mathbb{Z}_{n}$$ $$A:=g^{a}$$ $$\operatorname{coun} t=0$$ $$\frac{\operatorname{GETPK}():}{\operatorname{return} A}$$ QUERY $$(M \in \mathbb{G}):$$ $$\operatorname{count}:$$ count $$+1$$ if $$\operatorname{count}>1:$$ return null $$b, c \leftarrow \mathbb{Z}_{n}$$ $$B:=g^{b} ; C:=g^{c}$$ $$X:=M \cdot C$$ return $$(B, X)$$

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. 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. }}^{\text {. }}$$.

15.3: ElGamal Encryption is shared under a not declared license and was authored, remixed, and/or curated by LibreTexts.