ElGamal

links: AC2 TOC - RSA and ElGamal Encryption - Index

---

ElGamal Encryption Scheme

• Security is based on the hardness of the DL (Discrete Logarithm) problem.

ElGamal Key Generation

The key generation of ElGamal takes a random secret key $sk$ which is a random number in the range between $1$ and a given prime $q$. The public key is then calculated by exponentiation of the generator $g$ as base with the private key $sk$ as exponent:

• ${\mathbb{Z}}_q$: Additive Group (Number between $\{1...q\}$)
• ${\mathbb{G}}_q$: Multiplicative Subgroup (see Group of Integers Modulo a Safe Prime)

ElGamal Encryption and Decryption

Encryption and Decryption with ElGamal can be done pretty sweet. For encryption we first calculate some random $r$ in the additive group ${\mathbb{Z}}_q$. Then we calculate two return values $a$ and $b$. $a$ is the generator $g$ potentiated with the random $r$ and $b$ is the public key of the receiving party potentiated with random $r$ multiplied with the message $m$. Then $a$ and $b$ are returned.

Decryption is done by reverting the calculation using the private key of the receiving party. Therefore $a$ is potentiated with the negative value of the secret key. Then is multiplied with the received ciphertext $b$. This leads to the resolution of all factors until only the plaintext $m$ is left.

Important: Each single operation is done inside the publicly known group ${\mathbb{G}}_q$, which means each operation is calculated like $operation\mathrm{mod}q$.

Resolution in detail:

• $pk=g^{sk}$
• $a=g^r$
• $b=m\ast p{k}^r=m\ast g^{sk\ast r}$
• $m=b\ast a^{-sk}=b\ast g^{-(sk\ast r)}=b\ast {\displaystyle \frac{1}{g^{sk\ast r}}}=m\ast {\displaystyle \frac{g^{sk\ast r}}{g^{sk\ast r}}}=m$

Example

ElGamal Properties

Information about Gq subgroup

Information about why DDH doesn't hold in ${\mathbb{Z}}_p^{\ast }$

GPT

The Decisional Diffie-Hellman (DDH) assumption is a computational problem in cryptography. Specifically, it's an assumption made about the difficulty of a specific computational task in a cyclic group. The problem is to distinguish between the distributions $(g^a,g^b,g^{ab})$ and $(g^a,g^b,g^c)$ for random $a$, $b$, and $c$.

In the multiplicative group ${\mathbb{Z}}_p^{\ast }$ (where $p$ is prime), the DDH assumption does not hold. This is because if you have access to a group element, you can easily compute its square root (modulo $p$). This means you can distinguish between a random group element and a square. Thus, given $(g^a,g^b,g^{ab})$ and $(g^a,g^b,g^c)$, it's possible to check whether the third element is the product of the first two (modulo $p$) or not.

On the other hand, if we consider a subgroup ${\mathbb{G}}_q$ of ${\mathbb{Z}}_p^{\ast }$, where $p=2q+1$ for $p$ and $q$ prime (which makes $p$ a safe prime), and ${\mathbb{G}}_q$ is the subgroup of quadratic residues modulo $p$, the DDH assumption is believed to hold. This is because in this subgroup, it's computationally difficult to distinguish between a random element and a square, hence making it difficult to decide whether the third element is the product of the first two or not.

To summarize, the DDH problem is easier to solve in the full group ${\mathbb{Z}}_p^{\ast }$ (thus the DDH assumption does not hold), but is believed to be hard in the specific subgroup ${\mathbb{G}}_{\mathbb{q}}$ (thus the DDH assumption is considered to hold). This difference arises due to the mathematical properties of these groups and the specific structure of the DDH problem.

---

links: AC2 TOC - RSA and ElGamal Encryption - Index