0
$\begingroup$

Can someone provide a good and thorough explanation of the El Gamal proof? Basically, I need a step-by-step breakdown of what is happening at each important part in the algorithm.

I haven't been able to find any good notes on El Gamala that explain the proof in an easy to understand format.

Here is the proof in this image:

EL GAMAL PROOF REQUIRES EXPLANATION

$\endgroup$
  • 2
    $\begingroup$ Generally when people talk about the "proof of ElGamal encryption" they refer to the proof of security. What you have there is just the derivation that shows that it is correct, i.e. that decryption actually works. Are you aware of that or is that part of the confusion? $\endgroup$ – Maeher Feb 25 at 7:36
  • $\begingroup$ Oh dear, I must be so confused then. This is what I took from my professor's notes and I assumed it was the proof because it is labeled as such. $\endgroup$ – John Doe X Feb 25 at 8:10
  • $\begingroup$ I think I mean that I need an explanation of the derivation, which is the image posted in the body of my message. $\endgroup$ – John Doe X Feb 25 at 8:10
4
$\begingroup$

First, we should make clear what we're proving here. The derivation you're showing is part of a proof of correctness of ElGamal encryption, not security.

Perfect correctness (also referred to as completeness) of a public key encryption scheme is defined as follows.

Let $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ be a public key encryption scheme. The scheme is said to be perfectly correct if it holds that for any security parameter $n\in\mathbb{N}$, any key pair $(\mathsf{ek},\mathsf{dk})\gets\mathsf{Gen}(1^n)$, any message $m$ from the message space, and any ciphertext $c \gets \mathsf{Enc}(\mathsf{ek},m)$ it holds that $\mathsf{Dec}(\mathsf{dk},c)=m$.

To see whether ElGamal encryption is correct, we first recall the definition of ElGamal encryption. I will try to follow the notation in your notes as close as possible. From the notes it's not clear what kind of group is being used. But $e_1$ is a generator of some subgroup of $\mathbb{Z}_p^*$. Let $q$ be the order of that subgroup. (If $e_1$ is a generator of $\mathbb{Z}_p^*$, then $q=p-1$, if we are in a safe prime setting, then $q=(p-1)/2$ and prime.

\begin{align} &\mathsf{Gen}(1^n) && \mathsf{Enc}(e_2,P) && \mathsf{Dec}(d,(c_1,c_2))\\ &d\gets\mathbb{Z}_q&&r \gets \mathbb{Z}_q&&P' := c_2\cdot (c_1^d)^{-1} \bmod p\\ &e_2 := e_1^d \bmod p&&c_1:= e_1^r\bmod p&&\text{return }P'\\ &\text{return } (e_2,d)&&c_2 := P\cdot e_2^r\bmod p&\\ &&&\text{return } (c_1,c_2)&&\\ \end{align}

To verify that the scheme is correct, we need to verify that for any choice of key pair, and message it always holds that $\mathsf{Dec}(d,\mathsf{Enc}(e_2,P)) = P$. This is where the derivation you're looking at comes in.

\begin{align} P' =& c_2\cdot (c_1^d)^{-1} \bmod p \tag{1}\\ =& c_2\cdot (e_1^{rd})^{-1} \bmod p\tag{2}\\ =& P\cdot e_2^r\cdot (e_1^{rd})^{-1} \bmod p\tag{3}\\ =& P\cdot e_1^{rd}\cdot (e_1^{rd})^{-1} \bmod p\tag{4}\\ =& P\cdot e_1^{rd}\cdot e_1^{-rd} \bmod p\tag{5}\\ =& P\cdot e_1^{rd-rd} \bmod p\tag{6}\\ =& P \bmod p\tag{7}\\ \end{align}

Now let's go through this line by line.

  1. In line (1) we simply have the definition of the decryption algorithm.
  2. In line (2) we use the definition of $c_1 = e_1^r\bmod p$ from the encryption algorithm and replace $c_1$ by its definition.
  3. In line (3) we do exactly the same with $c_2$ and replace it with its definition $c_2 := P\cdot e_2^r\bmod p$ from the encryption algorithm.
  4. In line (4) we now look at the key generation algorithm and replace $e_2$ by its definition from there $e_2 := e_1^d \bmod p$. Note that we have not changed anything. We have simply replaced the variables $c_1,c_2,e_2$ by their respective definitions.
  5. In line (5) we use a basic rule of exponentiation, namely that $(x^a)^b = x^{a\cdot b}$, therefore $(e_1^{rd})^{-1} = e_1^{-rd}$.
  6. In line (6) we again use a basic rule of exponentiation, namely that $x^a\cdot x^b = x^{a+ b}$, therefore $e_1^{rd}\cdot e_1^{-rd} = e_1^{rd-rd}$.
  7. Since $rd-rd=0$ and anything raised to the $0$th power equals the identity, we are left with $P\cdot 1 \bmod p$ and thereby, since $1$ is the identity of the group with $P$ in line (7).

Since this derivation makes no assumptions whatsoever about $P,d,e_2,c_1$ and $c_2$, besides that they were generated according to the above definition of ElGamal encryption, it holds for any choice of key-pair and any plaintext $P$.

The derivation thus shows that decryption always works and results in the same plaintext that was encrypted, thus showing that the encryption scheme is in fact correct.

What it does not show is anything about the security of the scheme.

$\endgroup$
  • $\begingroup$ This is amazing and exactly what I needed. However, I think my professor is using this as a proof for El Gamal's encryption and decryption process and why it works, and I don't think she is using it as a proof of the security of El Gamal. She didn't really specify, but thanks for clearing this up. $\endgroup$ – John Doe X Mar 1 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.