Skip to main content
Library homepage
 
Loading table of contents menu...
Engineering LibreTexts

15.3: ElGamal Encryption

  • Page ID
    86474
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\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]{\| #1 \|}\) \( \newcommand{\inner}[2]{\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]{\| #1 \|}\) \( \newcommand{\inner}[2]{\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\).

    image

    (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, }}\),

    image
    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:

    image

    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.

    image

    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.

    • Was this article helpful?