ElGamal Encryption

tl;dr: I’ve got nothing1 .

I will elaborate a bit on why ElGamal public key encryption can be thought of as approximately equivalent to using an ephemeral Diffie-Hellman (DH) exchanged key as a one-time pad.

Prerequisite

Diffie-Hellman (DH) Key Exchange

  1. Let GG be a cyclic group of prime order qq with generator gg.
  2. Party A:
    • Picks a secret key aZqa \in \mathbb{Z}_q.
    • Computes the public key: pkA=ga\textcolor{teal}{pk_A} = g^a.
  3. Party B:
    • Picks a secret key bZqb \in \mathbb{Z}_q.
    • Computes the public key: pkB=gb\textcolor{orange}{pk_B} = g^b.
  4. Both parties compute the shared key:
    • A computes: (pkB)a=gba(pk_B)^a = g^{ba}.
    • B computes: (pkA)b=gab(pk_A)^b = g^{ab}.

Both parties arrive at the same shared secret gab\textcolor{#8B4513}{g^{ab}}, which can be used for symmetric encryption.

See also: Ephemeral and/or static keys.

Original ElGamal Encryption

Let’s first recall the original ElGamal Encryption. Let GG be a cyclic group of prime order qq with generator gg. An ElGamal Encryption is a tuple of 3 PPT algorithms:

  1. KeyGen:
    • Choose a random secret key skZqsk \in \mathbb{Z}_q.
    • Compute the public key pk=gskpk = g^{sk}.
    • Output: (pk,sk)(pk, sk).
  2. Encrypt(pk, m):
    • Choose a random rZqr \in \mathbb{Z}_q.
    • Compute c1=grc_1 = g^r.
    • Compute c2=mpkr=mgrskc_2 = m \cdot pk^r = m \cdot g^{r \cdot sk}.
    • Output: ciphertext c=(c1,c2)c = (c_1, c_2).
  3. Decrypt(sk, c):
    • Parse ciphertext c=(c1,c2)c = (c_1, c_2).
    • Compute shared secret s=c1sk=grsks = c_1^{sk} = g^{r \cdot sk}.
    • Recover message: m=c2s1m = c_2 \cdot s^{-1}.

So, why does ElGamal Encryption resemble an Ephemeral DH Key Exchange?

Suppose A wants to send a message to B and knows B’s ElGamal public key. In this scenario:

  • B’s public key in ElGamal encryption is essentially a static DH key, written as gskB\textcolor{orange}{g^{sk_B}}.
  • When A encrypts a message using B’s public key, it effectively performs a DH key exchange:
    • A picks a random rr and computes gr\textcolor{teal}{g^r}, an ephemeral DH key.
    • A then computes a shared key grskB\textcolor{#8B4513}{g^{r \cdot sk_B}} and uses it to blind the message mm.

What are the differences?

  • It’s not a pure One-Time Pad (OTP) because the encryption uses multiplication rather than XOR2 Hashed ElGamal emulates OTP by hashing the shared key p=H(pkr)p = H(pk^r) and XORing it with the message. This avoids encoding/decoding messages into the group used by ElGamal..