Elgamal Encryption

ElGamal Encryption

ElGamal is a public-key cryptosystem based on the hardness of the Discrete Logarithm Problem in a cyclic group.

Setup

Choose a large prime $p$, a generator $g$ of the multiplicative group $\mathbb{Z}_p^*$, and a private key $x$. The public key is $h = g^x \mod p$.

Encryption

To encrypt message $m$:

1. Pick a random ephemeral key $k$
2. Compute $c_1 = g^k \mod p$
3. Compute $c_2 = m \cdot h^k \mod p$
4. Ciphertext is $(c_1, c_2)$

Decryption

Given private key $x$:

1. Compute shared secret $s = c_1^x \mod p$
2. Recover $m = c_2 \cdot s^{-1} \mod p$

Example Walkthrough

Let $p = 23$, $g = 11$, and choose private key $x = 6$.

Setup — Key Generation

$h = g^x \mod p = 11^6 \mod 23 = 9$

• Private key: $x = 6$ — known only to the recipient.
• Public key: $(p, g, h) = (23, 11, 9)$ — shared openly.

Encryption — Encrypt message $m = 7$ with random $k = 3$:

$c_1 = g^k \mod p = 11^3 \mod 23 = 20$

$c_2 = m \cdot h^k \mod p = 7 \cdot 9^3 \mod 23 = 7 \cdot 16 \mod 23 = 112 \mod 23 = 20$

Ciphertext: $(c_1, c_2) = (20, 20)$

Decryption — Recover $m$ using private key $x = 6$:

$s = c_1^x \mod p = 20^6 \mod 23 = 16$

$s^{-1} \mod 23 = 13 \quad \text{(since } 16 \cdot 13 = 208 \equiv 1 \pmod{23}\text{)}$

$m = c_2 \cdot s^{-1} \mod p = 20 \cdot 13 \mod 23 = 260 \mod 23 = 7 \quad \checkmark$

Key Properties

• Randomized: The random $k$ means encrypting the same message twice produces different ciphertexts.
• Homomorphic: Multiplying two ciphertexts gives a valid encryption of the product of the plaintexts — this is why it shows up a lot in voting schemes and privacy protocols.
• Ciphertext expansion: Output is 2x the size of the plaintext.
• Semantic security holds under the Decisional Diffie-Hellman (DDH) assumption.

Exponential ElGamal and Additive Homomorphism

Standard ElGamal encrypts a group element directly — decryption recovers it as-is. Exponential ElGamal instead encodes an integer $v$ as the group element $v \cdot G$ (or $g^v$ in multiplicative notation), which changes the homomorphic property from multiplicative to additive:

$\text{Enc}(a) + \text{Enc}(b) = \text{Enc}(a + b)$

This is the key property that makes exponential ElGamal useful for on-chain voting and privacy protocols. The chain can sum thousands of encrypted shares without decrypting any of them — the tally accumulates homomorphically.

The tradeoff is that decryption now yields $v \cdot G$, not $v$ directly. Recovering the integer $v$ from $v \cdot G$ is a discrete logarithm problem. In practice this is fine when $v$ is bounded (as it always is in a tally), because Baby-Step Giant-Step (BSGS) solves it cheaply in $O(\sqrt{v})$ time.

If we used standard ElGamal (direct group element recovery, no BSGS needed), we'd lose the additive homomorphism and couldn't accumulate encrypted votes on-chain.