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
- Let be a cyclic group of prime order with generator .
- Party A:
- Picks a secret key .
- Computes the public key: .
- Party B:
- Picks a secret key .
- Computes the public key: .
- Both parties compute the shared key:
- A computes: .
- B computes: .
Both parties arrive at the same shared secret , 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 be a cyclic group of prime order with generator . An ElGamal Encryption is a tuple of 3 PPT algorithms:
- KeyGen:
- Choose a random secret key .
- Compute the public key .
- Output: .
- Encrypt(pk, m):
- Choose a random .
- Compute .
- Compute .
- Output: ciphertext .
- Decrypt(sk, c):
- Parse ciphertext .
- Compute shared secret .
- Recover message: .
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 .
- When A encrypts a message using B’s public key, it effectively performs a DH key exchange:
- A picks a random and computes , an ephemeral DH key.
- A then computes a shared key and uses it to blind the message .
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 and XORing it with the message. This avoids encoding/decoding messages into the group used by ElGamal..