ElGamal Encryption Algorithm¶

Overview¶

The ElGamal encryption algorithm is an asymmetric encryption algorithm proposed by Taher Elgamal in 1985, based on Diffie-Hellman key exchange, achieving semantic security. The algorithm relies on the difficulty of the discrete logarithm problem in modular arithmetic to implement encryption.

ElGamal is another well-known asymmetric encryption algorithm besides RSA, and has been adopted as an ISO international standard.

Core Properties¶

Asymmetric Encryption: ElGamal is an asymmetric encryption system with a pair of keys -- one public key and one private key.

Homomorphism: ElGamal encryption satisfies multiplicative homomorphism, meaning E(m1) * E(m2) = E(m1 * m2). This means the product of two ciphertexts equals the ciphertext of the product of the plaintexts.

Elliptic Curve Variant: Elliptic Curve ElGamal (EC-ElGamal) can achieve additive homomorphism, meaning E(m1) + E(m2) = E(m1 + m2), which is more useful in certain applications.

Randomized Encryption: ElGamal uses a random number k during encryption, meaning the same plaintext encrypted twice produces different ciphertexts, enhancing security.

Technical Principles¶

Key Generation: 1. Choose a large prime p and generator g 2. Choose private key x (random number) 3. Compute public key y = g^x mod p 4. Public key is (p, g, y), private key is x

Encryption Process: 1. Choose random number k 2. Compute c1 = g^k mod p 3. Compute c2 = m * y^k mod p 4. Ciphertext is (c1, c2)

Decryption Process: 1. Compute s = c1^x mod p 2. Compute m = c2 * s^(-1) mod p

Use Cases¶

Electronic Voting: Leveraging homomorphism, total vote counts can be tallied without decrypting individual votes.

Secure Multi-Party Computation: In multi-party computation, parties can perform computations on encrypted data without revealing the original data.

Hybrid Encryption Systems: Commonly used in Key Encapsulation Mechanisms (KEM), combined with symmetric encryption.

Digital Signatures: ElGamal can also be used to construct digital signature schemes (ElGamal signature).

Comparison with RSA¶

Feature	ElGamal	RSA
Underlying Problem	Discrete logarithm	Integer factorization
Ciphertext Size	2x plaintext	Comparable to plaintext
Homomorphism	Multiplicative	Multiplicative
Randomization	Yes	No (standard version)
Standardization	ISO standard	Widely standardized

Security¶

Discrete Logarithm Difficulty: ElGamal's security is based on the difficulty of the discrete logarithm problem; no effective polynomial-time algorithm currently solves this problem.

Chosen Plaintext Attack: ElGamal is secure against chosen plaintext attacks (CPA) due to its randomization property.

Quantum Threat: Like other discrete logarithm-based systems, ElGamal is vulnerable to Shor's quantum algorithm.

Elliptic Curve ElGamal¶

EC-ElGamal: Implements ElGamal on elliptic curves, offering shorter key lengths and higher efficiency. The elliptic curve version achieves additive homomorphism, which is more practical in certain applications.

Applications: EC-ElGamal has wide applications in blockchain privacy protection, secure voting, and other scenarios.