Fact-checked by Grok 2 weeks ago

ElGamal encryption

ElGamal encryption is a probabilistic public-key cryptosystem designed for secure message transmission, where a sender uses the recipient's public key to encrypt data that only the recipient can decrypt using their private key, relying on the hardness of the discrete logarithm problem in finite fields for security.^[1] Developed by Egyptian-American cryptographer Taher ElGamal and first published in 1985, the scheme builds on earlier work in public-key cryptography, such as the Diffie-Hellman key exchange, by extending it to asymmetric encryption without requiring shared secrets.^[1] In the original formulation, it operates over the multiplicative group of integers modulo a large prime p, where p and a primitive root α (a generator of the group) are publicly known parameters selected for their computational properties.^[2] Key generation involves the recipient choosing a random private key x (an integer between 1 and p-2) and computing the public key y = α^x mod p, which is shared openly.^[1] To encrypt a message m (represented as an integer between 0 and p-1), the sender selects a random ephemeral key k (also between 1 and p-2) and computes the ciphertext as a pair (c₁, c₂), where c₁ = α^k mod p and c₂ = m · (y^k mod p) mod p; this ensures the encryption is randomized, so identical messages produce different ciphertexts, enhancing security against certain attacks.^[2] Decryption by the recipient recovers m by first computing the shared secret s = c₁^x mod p (which equals y^k mod p), then m = c₂ · s^{-1} mod p, where the modular inverse exists because s is coprime to p.^[1] This process doubles the size of the ciphertext compared to the plaintext, a trade-off for its security model.^[2] The security of ElGamal encryption is provably equivalent to the difficulty of solving the discrete logarithm problem—finding x given α, y, and p—which is believed to be computationally infeasible for sufficiently large p (at least 2048 bits, with 3072 bits or more recommended for long-term security as of 2025, though modern recommendations favor elliptic curve variants for efficiency).^[1]^[3] It provides semantic security under the decisional Diffie-Hellman assumption when properly implemented, but the basic scheme is malleable, meaning ciphertexts can be modified without detection, necessitating hybrid use with symmetric ciphers for robust applications.^[4] ElGamal has influenced numerous protocols and is implemented in tools like GNU Privacy Guard (GnuPG) for email encryption subkeys and in Pretty Good Privacy (PGP) for secure messaging, though its use in OpenPGP has faced scrutiny for potential vulnerabilities in key handling.^[5]^[6] Variants, such as elliptic curve ElGamal, address performance issues by operating over elliptic curve groups, offering stronger security per bit length.^[4]

Background

Historical Development

Taher ElGamal developed the ElGamal encryption scheme during his doctoral studies at Stanford University, where he earned his PhD in electrical engineering in 1984 under the supervision of Martin Hellman. The scheme originated as part of his research on discrete logarithm-based cryptography, building directly on foundational work in public-key systems. ElGamal formally published the encryption algorithm in 1985 in the paper "A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms," appearing in IEEE Transactions on Information Theory.^[2]^[7] The invention drew significant influence from the Diffie-Hellman key exchange protocol introduced in 1976, which established the viability of discrete logarithms as a hard problem for key agreement. This marked a shift from early public-key systems like RSA—published in 1977 and reliant on integer factorization—toward discrete logarithm-based alternatives that offered greater flexibility in finite fields. Key motivations included creating a patent-free option amid RSA's licensing restrictions and addressing RSA's deterministic nature, which lacked inherent semantic security; ElGamal's probabilistic design randomized ciphertexts to prevent leakage of message information under chosen-plaintext attacks.^[2]^[8] Adoption accelerated in the 1990s with integration into secure email tools like PGP, where ElGamal's efficiency and royalty-free status made it a preferred choice for public-key encryption in open-source implementations such as GnuPG. By the 2000s, elliptic curve variants emerged, adapting the scheme to elliptic curve discrete logarithms for smaller keys and faster computation; these influenced standards like ANSI X9.63, which incorporated ElGamal extensions such as DHIES for hybrid encryption.^[8]^[9]

Mathematical Foundations

ElGamal encryption is built upon the algebraic structure of cyclic groups, which provide the foundational framework for its operations. A cyclic group G is a group that can be generated by a single element g, known as a generator, such that every element in G can be expressed as g^k for some integer k. Generators, also called primitive elements in this context, have order equal to the size of the group, meaning the smallest positive integer m such that g^m = 1 is m = |G|. In cryptography, cyclic groups are preferred for their simplicity and the well-understood hardness of certain computational problems within them.^[10] A common instantiation used in ElGamal is the multiplicative group of nonzero elements modulo a prime p, denoted (\mathbb{Z}/p\mathbb{Z})^*, which forms a finite field and is cyclic of order p-1. This group consists of integers from 1 to p-1 under multiplication modulo p, and for prime p, it is guaranteed to be cyclic, ensuring the existence of generators that produce all elements through successive powers. The choice of such finite fields allows efficient computation while leveraging the large order for security.^[11] Central to ElGamal's security is the discrete logarithm problem (DLP) within these cyclic groups. Given a generator g of a cyclic group G of order q and an element y = g^x for some secret x \in \{0, \dots, q-1\}, the DLP asks to compute x. The hardness of the DLP—meaning no efficient algorithm exists to solve it in polynomial time—is assumed in groups like (\mathbb{Z}/p\mathbb{Z})^* for sufficiently large primes p, forming the basis for discrete logarithm-based cryptosystems. This intractability underpins the inability of adversaries to recover secrets from public information in such schemes.^[12] ElGamal achieves semantic security, equivalent to indistinguishability under chosen-plaintext attack (IND-CPA), meaning an adversary cannot distinguish encryptions of two plaintexts with non-negligible advantage, even after choosing the plaintexts adaptively. This security holds under the decisional Diffie-Hellman assumption in the relevant cyclic groups, ensuring that shared secrets derived from public elements remain hidden. Theoretical analyses often employ the random oracle model, where hash functions are idealized as random functions mapping inputs to uniformly random outputs, facilitating proofs by simulating adversary interactions and bounding advantages relative to underlying hard problems like the DLP or Diffie-Hellman.^[13]^[14] For enhanced security, ElGamal typically operates over prime-order subgroups of larger cyclic groups, where the subgroup order q is prime. This structure ensures no nontrivial proper subgroups exist, as any subgroup of a cyclic group of prime order must be the full group or trivial, thereby preventing attacks that exploit elements of small order, such as invalid curve or small subgroup confinement, and guaranteeing that random elements behave uniformly.^[15]

Algorithm

Key Generation

The key generation process in ElGamal encryption begins with the selection of cryptographic parameters to establish a secure finite field environment. A large prime number p is chosen, typically with a bit length of at least 3072 bits to provide 128-bit security in line with contemporary recommendations, serving as the modulus for all computations. A primitive root g modulo p (a generator of the full multiplicative group \mathbb{Z}_p^* of order p-1) is identified. These parameters are fixed for the system and shared publicly. Modern implementations often use a large prime subgroup of order q dividing p-1 for enhanced security against certain attacks, with p and q selected per NIST guidelines.^[16] The private key is a randomly selected integer x from the set \{1, 2, \dots, p-2\}, which must be generated using a cryptographically secure pseudorandom number generator (CSPRNG) to ensure unpredictability and resistance to guessing or reconstruction attacks. Standards such as NIST SP 800-90A specify approved Deterministic Random Bit Generators (DRBGs), like those based on AES-CTR, for producing such values, emphasizing the need for high-entropy seeds and continuous reseeding during key generation. The secrecy of x relies on the computational difficulty of the discrete logarithm problem, where recovering x from g and g^x \mod p is infeasible for large parameters. The public key consists of the computed value y = g^x \mod p, published alongside the system parameters p and g. This computation is performed using efficient modular exponentiation algorithms to handle large exponents without excessive overhead.

Encryption Process

The encryption process in the ElGamal cryptosystem requires the sender to have the recipient's public key, which consists of a large prime modulus p, a primitive root g modulo p, and the value y = g^x \mod p, where x is the recipient's private key. The message m is first encoded as an integer satisfying $0 < m < p, typically by converting the plaintext string to a numerical representation, such as interpreting it in a base compatible with g or applying padding to fit the range.^[1]^[17] To produce the ciphertext, the sender generates a random ephemeral key k \in \{1, \dots, p-2\}. The resulting ciphertext is a pair of integers (c_1, c_2), computed via the following modular exponentiations:

c_1 = g^k \mod p

c_2 = m \cdot y^k \mod p

Since y = g^x \mod p, this expands to c_2 = m \cdot (g^x)^k \mod p = m \cdot g^{xk} \mod p, where g^{xk} \mod p serves as a shared secret mask for the message.^[1] For messages larger than the bit length of p, which limits direct encryption to short plaintexts, a hybrid variant is commonly used. Here, ElGamal encrypts a randomly generated symmetric key K, and K is then employed with a symmetric encryption algorithm (e.g., AES) to secure the full message, enabling efficient handling of arbitrary-sized data while leveraging public-key key exchange.^[18]

Decryption Process

The decryption process in the ElGamal encryption scheme enables the recipient to recover the plaintext message m from the received ciphertext (c_1, c_2) using their private key x and the public parameters, which include a large prime p, the primitive root g modulo p, and the public key y = g^x \mod p.^[2]^[19] The recipient first computes the shared secret value s = c_1^x \mod p. Since c_1 = g^k \mod p for a random ephemeral key k selected by the sender during encryption, this computation yields s = (g^k)^x \mod p = g^{kx} \mod p = y^k \mod p.^[2]^[20] To recover the message, the recipient then calculates the modular multiplicative inverse s^{-1} of s modulo p (which exists because p is prime and s \not\equiv 0 \mod p), and computes m = c_2 \cdot s^{-1} \mod p. This step succeeds because c_2 = m \cdot y^k \mod p from the encryption, so m = c_2 \cdot (y^k)^{-1} \mod p.^[2]^[20] The decrypted value m is verified by checking that it lies in the valid range, typically $0 < m < p, ensuring it corresponds to an encoded plaintext element in the field.^[20] Decryption may fail in cases of invalid ciphertext, such as when c_1 or c_2 is outside [1, p-1], or if s shares a common factor with p (preventing the inverse from existing), leading to an erroneous output; practical implementations often include bounds checks or redundancy to detect and handle such failures.^[20]^[21]

Security Analysis

Cryptographic Assumptions

The security of ElGamal encryption fundamentally relies on the hardness of the discrete logarithm problem in a cyclic group of prime order, but formal proofs of its security properties are established under the stronger decisional Diffie-Hellman (DDH) assumption.^[22] The DDH assumption posits that, for a cyclic group G of prime order q with generator g, and randomly chosen a, b \in \mathbb{Z}_q, no probabilistic polynomial-time adversary can distinguish the tuple (g, g^a, g^b, g^{ab}) from a random tuple (g, g^a, g^b, g^r) where r \in \mathbb{Z}_q is uniformly random, with non-negligible advantage.^[23] Under this assumption, ElGamal achieves indistinguishability under chosen-plaintext attack (IND-CPA) security through a direct reduction: a hypothetical IND-CPA adversary \mathcal{A} can be transformed into a DDH solver \mathcal{B} by embedding a DDH challenge instance into the public key and challenge ciphertext. Specifically, \mathcal{B} sets the receiver's public key to g^a from the DDH tuple (g, g^a, g^b, Z), uses g^b as the ephemeral public value in the challenge ciphertext, and computes the second ciphertext component as Z \cdot m_b (where m_b is the challenged message and b is \mathcal{A}'s bit guess). If Z = g^{ab}, the ciphertext is a valid encryption of m_b; otherwise, it hides the message completely, and \mathcal{A}'s advantage in distinguishing m_0 from m_1 implies a DDH solution. This hybrid argument ensures that \mathcal{A}'s view is indistinguishable across security games, yielding negligible advantage if DDH holds.^[22]^[15] ElGamal's semantic security—equivalent to IND-CPA for public-key encryption—stems from its probabilistic nature, where the ephemeral random value k randomizes each ciphertext, producing an output distribution independent of the plaintext beyond its length. This randomization prevents malleability in the basic scheme by ensuring that any modification to a ciphertext yields a decryption that is computationally unpredictable, unlike deterministic constructions.^[22] In contrast, textbook RSA encryption is deterministic and thus not semantically secure, as an adversary can exploit the fixed mapping from plaintext to ciphertext to test partial message information without randomization. For variants incorporating hashing, such as hashed ElGamal (where the blinding factor for the message is derived as H(c_1)^x with c_1 = g^k and H a hash function), the scheme achieves stronger chosen-ciphertext attack (IND-CCA) security in the random oracle model under the DDH assumption (or the closely related internal computational Diffie-Hellman assumption). The proof follows a similar reduction, leveraging the random oracle to bind components and prevent invalid ciphertexts from revealing information.^[24]

Known Vulnerabilities and Attacks

One significant vulnerability in ElGamal encryption arises from small subgroup attacks, which occur when the order of the multiplicative group modulo the prime p (i.e., p-1) has small prime factors, allowing an attacker to confine the generator g to a subgroup of small order where the discrete logarithm problem becomes feasible using algorithms like Pohlig-Hellman.^[25] This attack can reveal partial information about the private key or ephemeral values if parameters are not properly validated. To mitigate this, implementations should use safe primes where p = 2q + 1 and both p and q are prime, ensuring the only subgroups are of order 2 or q, thus restricting attackers to computationally hard problems.^[26] ElGamal is also susceptible to invalid ciphertext attacks, where malformed ciphertexts lead to decryption failures or unintended information leakage during the recovery of the message from m = c_2 \cdot (c_1^x)^{-1} \mod p, potentially enabling chosen-ciphertext adversaries to distinguish encryptions or extract bits of the plaintext.^[27] Such attacks exploit the scheme's lack of inherent integrity checks, allowing an adversary to submit modified pairs (c_1, c_2) that cause errors or biases in decryption outputs. Countermeasures include adding probabilistic padding schemes, such as OAEP-like constructions adapted for ElGamal, to ensure semantic security against adaptive chosen-ciphertext attacks and reject invalid inputs without leaking information.^[27] In the 1990s, research identified vulnerabilities in ElGamal with weak parameters, such as short private exponents or small primes, reducing security to levels solvable by methods like the baby-step giant-step algorithm.^[28] More recently, the 2015 Logjam attack demonstrated how export-grade Diffie-Hellman parameters (512-bit primes) shared across ElGamal-like systems could be precomputed for discrete log recovery using the number field sieve, enabling man-in-the-middle decryption of sessions in affected protocols.^[29] In 2021, researchers identified implementation-specific vulnerabilities in OpenPGP's use of ElGamal, such as cross-configuration attacks where ciphertexts generated with one library can be decrypted by another due to inconsistent parameter handling, and invalid curve attacks exploiting non-prime-order groups. These affected approximately 2,000 public keys, allowing practical plaintext recovery.^[30] As a result, ElGamal encryption is increasingly deprecated in modern OpenPGP tools in favor of RSA or ECC-based schemes. Side-channel attacks pose another practical threat to ElGamal, particularly timing leaks during modular exponentiation in key generation, encryption (computing g^k \mod p), or decryption (computing c_1^x \mod p), where variable execution times reveal bits of the secret exponent through statistical analysis of repeated operations.^[31] For instance, implementations using square-and-multiply without blinding can leak the Hamming weight of exponents via cache or power traces. Mitigation requires constant-time exponentiation algorithms, such as Montgomery ladders or windowed methods with masking, to eliminate timing variations regardless of input.^[31] Finally, ElGamal's reliance on the discrete logarithm problem renders it vulnerable to quantum threats, as Shor's algorithm can solve the DLP in polynomial time on a sufficiently large quantum computer, efficiently computing private keys from public ones and breaking the scheme entirely. Post-quantum alternatives, such as lattice-based encryption schemes like Kyber, are recommended for long-term security in quantum-resistant deployments.

Implementations

Computational Efficiency

The computational efficiency of ElGamal encryption stems primarily from the cost of modular exponentiations required in its operations, performed within a multiplicative group of order q modulo a large prime p. Key generation involves selecting a random private key x \in \{1, \dots, q-1\} and computing the public key y = g^x \mod p, where g is a generator; this requires a single modular exponentiation, which can be executed in O(\log q) modular multiplications using the square-and-multiply algorithm.^[2] Encryption of a plaintext message m requires generating a random ephemeral key k \in \{1, \dots, q-1\} and performing two independent modular exponentiations: c_1 = g^k \mod p and c_2 = m \cdot y^k \mod p, yielding the ciphertext (c_1, c_2). Each exponentiation takes O(\log q) modular multiplications via square-and-multiply, for a total of approximately $2 \cdot O(\log q) such operations, excluding the final scalar multiplication by m. Decryption similarly demands one modular exponentiation to compute c_1^x \mod p, followed by a modular multiplication to recover m = c_2 \cdot (c_1^x)^{-1} \mod p, again amounting to roughly two exponentiations in practice.^[2] In terms of bit-level operations for a typical 2048-bit modulus p (with q \approx p), each modular exponentiation entails about 3000 modular multiplications of 2048-bit integers via square-and-multiply (roughly \log_2 q squarings plus half that many additional multiplications on average), resulting in approximately $10^4 such multiplications for encryption. This computational cost is broadly similar to that of RSA for equivalent security levels, though ElGamal's ciphertext expansion—twice the plaintext size, as it encodes two full group elements of size \approx \log_2 p bits each—imposes higher bandwidth overhead compared to RSA's single-element output. Space requirements are linear in the key size, with keys and ciphertext each occupying O(\log p) bits.^[32] Common optimizations include precomputing tables of powers like g^{2^i} \mod p to reduce online exponentiation steps, potentially halving the number of multiplications in some cases; however, such tables can leak information via side-channel attacks, including cache-timing exploits that observe memory access patterns during table lookups. On 2020s-era CPUs (e.g., Intel Core i7 or equivalent), 2048-bit ElGamal encryption completes in under 1 ms per operation, benefiting from hardware-accelerated modular arithmetic in libraries like Crypto++.^[33]^[32]

Practical Applications and Variants

ElGamal encryption has found practical applications in secure communication protocols, particularly for key transport and digital signatures. In the 1990s, it was employed in Pretty Good Privacy (PGP) for public-key encryption of symmetric session keys, enabling secure email exchange by encapsulating a symmetric key within an ElGamal ciphertext.^[34] The ElGamal signature scheme, introduced in 1985, served as the foundational basis for the Digital Signature Algorithm (DSA), standardized by NIST in FIPS 186, where modifications were made to integrate hashing and optimize for government use while retaining the discrete logarithm core.^[35] Additionally, ElGamal supports hybrid encryption setups, such as key encapsulation mechanisms in protocols like HPKE, for encapsulating symmetric keys alongside Diffie-Hellman primitives.^[36] A prominent variant is Elliptic Curve ElGamal (EC-ElGamal), which adapts the scheme to elliptic curve groups instead of multiplicative groups over finite fields, achieving equivalent security with significantly smaller key sizes—for instance, a 256-bit elliptic curve key provides security comparable to a 3072-bit prime field in classical ElGamal.^[37] This efficiency stems from the harder discrete logarithm problem on elliptic curves, reducing computational overhead and bandwidth in resource-constrained environments like mobile devices. The Cramer-Shoup cryptosystem extends ElGamal by incorporating additional public keys and a hash function on ciphertexts, adding redundancy to achieve provable security against adaptive chosen-ciphertext attacks (CCA), unlike the basic ElGamal's vulnerability to such attacks.^[38] Introduced in 1998, it maintains the core ElGamal structure but includes a verification tag in decryption, ensuring integrity and enabling practical deployment in scenarios requiring stronger security models, such as secure messaging. ElGamal exhibits multiplicative homomorphic properties, where the product of two ciphertexts decrypts to the product of the plaintexts, facilitating operations like secure multiplication in encrypted data. An additive variant modifies the encryption—typically by raising the message to the random exponent in the group—to support addition of plaintexts via ciphertext multiplication, which is useful in privacy-preserving computations such as secure voting or statistical analysis without decryption.^[39] Due to performance advantages, there has been a shift from classical ElGamal over finite fields to elliptic curve variants, driven by smaller key sizes and faster operations; NIST's SP 800-56A, revised in 2018 and proposed for further updates in the 2020s, recommends discrete logarithm-based key establishment but prioritizes elliptic curves for new systems to align with efficiency standards.^[40] However, due to advances in quantum computing, discrete logarithm-based schemes including ElGamal and its variants are vulnerable to Shor's algorithm. As of 2024, NIST has released post-quantum cryptography standards (FIPS 203, 204, 205) and plans to deprecate discrete logarithm-based key establishment for new applications after 2030 (per NIST IR 8547 and SP 800-131A Rev. 2).^[41]^[42]

References

[1]
A Public Key Cryptosystem and a Signature Scheme Based on ...
A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. Download book PDF. Taher ElGamal. Part of the book series: Lecture Notes in ...
[2]
https://ieeexplore.ieee.org/document/1057074
[3]
[PDF] The ElGamal Public-‐key System - Applied Cryptography Group
Key exchange (e.g. in HTTPS). Encryp3on in non-‐interac3ve seKngs: • Secure Email: Bob has Alice's pub-‐key and sends her an email. • Encrypted File Systems.
[4]
Getting Started - GnuPG
An ElGamal subordinate keypair is also created for encryption. Option 2 is similar but creates only a DSA keypair. Option 4[1] creates a single ElGamal ...
[5]
(In)security of ElGamal in OpenPGP - IBM Research
Jul 20, 2021 · First described in 1985 by Taher Elgamal, it is one of the oldest and best studied algorithms used in public-key cryptography. While ElGamal ...Missing: original | Show results with:original
[6]
[PDF] ElGamal Public-Key Encryption and Decryption - CS@UCSB
Taher ElGamal, originally from Egypt, was a graduate student at. Stanford University, and earned a PhD degree in 1984, Martin. Hellman as his dissertation ...Missing: invention | Show results with:invention
[7]
On the (In)Security of ElGamal in OpenPGP
Jun 1, 2023 · The 1984 ElGamal cryptosystem is one of the oldest and best-known public key encryption schemes. In the 80s and 90s, it earned wide adoption for ...Missing: X9. 42
[8]
[PDF] DHIES: An encryption scheme based on the Diffie-Hellman Problem
It is a simple extension of the ElGamal encryption scheme and is now in the draft standards of ANSI X9.63 and IEEE P1363a [2, 23] and in the corporate standard ...
[9]
Group Theory - Cyclic Groups
A cyclic group is a group generated by a single element, where every element has the form for some integer.
[10]
[PDF] CYCLICITY OF (Z/(p)) 1. Introduction For a prime p, the group (Z/(p ...
For a prime p, the group (Z/(p))× is cyclic, which is important in number theory and has practical significance. For most composite m, (Z/(m))× is not cyclic.<|separator|>
[11]
[PDF] A public key cryptosystem and a signature scheme based on ...
The paper described a public key cryptosystem and a signature scheme based on the difficulty of computing discrete logarithms over finite fields. The ...
[12]
[PDF] A tutorial introduction to CryptHOL - Cryptology ePrint Archive
As a running example, we formalize a variant of the hash-based ElGamal encryption scheme and its IND-CPA security in the random oracle model.
[13]
[PDF] the random oracle model: a twenty-year retrospective
Apr 28, 2015 · 1. Introduction. The random oracle model is a powerful tool introduced by Bellare and. Rogaway in [8] in order to make it possible to give ...
[14]
[PDF] El Gamal A DDH based encryption scheme - Computer Science
El Gamal, based on the hardness of the decisional Diffie-Hellman (DDH) problem, is commonly used public-key encryption scheme. Before introducing the scheme ...
[15]
https://cs.wellesley.edu/~cs310/lectures/27_el_gamal_slides_handouts.pdf
[16]
ElGamal crypto system
The ElGamal encryption system is a public key encryption algorithm by Taher Elgamal [3] in 1985 that is based on the Diffie-Hellman key exchange.
[17]
https://math-sites.uncg.edu/sites/pauli/112/HTML/secelgamal.html
[18]
Public key cryptography using discrete logarithms. Part 3: ElGamal ...
It uses the same domain parameters (p,q,g) and private/public key pair (b,B=gbmodp) for a recipient B. The plaintext message to be encrypted needs to be encoded ...Missing: pqg | Show results with:pqg
[19]
[PDF] The ElGamal Public Key Encryption Algorithm
The ElGamal Algorithm provides an alternative to the RSA for public key encryption. 1) Security of the RSA depends on the (presumed) difficulty of factoring ...
[20]
[PDF] Implementing several attacks on plain ElGamal encryption
In “Why Textbook ElGamal and RSA Encryption are Insecure” [BJN00], several algorithms for attacking the plain ElGamal public-key cryptosystem are described.
[21]
[PDF] Lecture 19: 2006.03.21 19.1 Proof of Security for El Gamal
Mar 21, 2006 · Theorem 19.1 If the Discrete Diffie-Hellman problem is hard (i.e. if the DDH assumption holds), El Gamal is IND-CPA secure. Proof: Assume, by ...
[22]
[PDF] The Decision Di e-Hellman Problem - Applied Cryptography Group
The Decision Di e-Hellman assumption (ddh) is a gold mine. It enables one to construct e cient cryptographic systems with strong security properties. In this ...
[23]
[PDF] CCA secure ElGamal encryption over an integer group where ICDH ...
In the random oracle model, hashed ElGamal is proved to be CCA secure (i.e., to be semantically secure against Chosen Ciphertext Attack) under the ICDH.
[24]
[PDF] Security Analysis of ElGamal Implementations - Inria
ElGamal (ElGamal, 1985) is an asymmetric encryp- tion scheme, it enjoys homomorphic properties that are fundamental for the electronic voting systems. El-.
[25]
[PDF] Measuring small subgroup attacks against Diffie-Hellman
For a safe prime, it suffices to check that y is strictly between 1 and p − 1. Small subgroup key recovery attacks. Lim and Lee [54] discovered a further attack ...Missing: ElGamal mitigation
[26]
[PDF] On the CCA1-Security of Elgamal and Damgård's Elgamal
By following a very similar proof, a variant of the DEG cryptosystem where the decryption, given an invalid ciphertext, returns a random plaintext instead of.<|control11|><|separator|>
[27]
On the (in)security of ElGamal in OpenPGP - Part I - IBM
Jul 20, 2021 · We found two types of vulnerabilities in the way OpenPGP implementations handle ElGamal encryption. We call the first type cross-configuration attacks.
[28]
[PDF] Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice
ABSTRACT. We investigate the security of Diffie-Hellman key exchange as used in popular Internet protocols and find it to be less secure.
[29]
[PDF] New Single-Trace Side-Channel Attacks on a Specific Class of ...
In this paper, we propose a new type of the N − 1 low-order attack on a specific class of Elgamal which is implemented based on the square-and-multiply-always.
[30]
RSA-2048 vs ElGamal (Variable key size) - MojoAuth
RSA-2048 has a fixed 2048-bit key size, while ElGamal's security depends on its prime modulus size, allowing variable key sizes. RSA-2048 has fixed performance ...
[31]
[PDF] On the (in)security of ElGamal in OpenPGP - Cryptology ePrint Archive
Jul 7, 2021 · One of the earliest proposals to construct public key encryption is by Taher ElGamal [14]. As a first approximation, the construction is as ...
[32]
RFC 4880 - OpenPGP Message Format - IETF Datatracker
For example, there may be a single- key RSA key in V4 format, a DSA primary key with an RSA encryption key, or RSA primary key with an Elgamal subkey, etc.
[33]
https://eprint.iacr.org/2021/923.pdf
[34]
draft-irtf-cfrg-hpke-04 - IETF Datatracker
May 8, 2020 · Hybrid Public Key Encryption. Abstract. This document describes a scheme for hybrid public-key encryption (HPKE). This scheme provides ...
[35]
SP 800-57 Part 1 Rev. 5, Recommendation for Key Management
May 4, 2020 · This Recommendation provides cryptographic key-management guidance. It consists of three parts. Part 1 provides general guidance and best practices.
[36]
[PDF] Design and Analysis of Practical Public-Key Encryption Schemes ...
Aug 14, 2003 · This paper proposes a new practical public-key encryption scheme, proven secure against adaptive chosen ciphertext attack, and is the first to ...
[37]
https://csrc.nist.gov/pubs/sp/800/57/pt1/r5/final
[38]
SP 800-56A Rev. 3, Recommendation for Pair-Wise Key ...
Apr 16, 2018 · This Recommendation specifies key-establishment schemes based on the discrete logarithm problem over finite fields and elliptic curves.