Construct another ciphertext that decrypts to same message without knowing key in Elgamal

I read about ElGamal from various resources and I was wondering if the following is true. Would appreciate if you could elaborate on it so I can understand better:

Is it possible to construct, given an encrypted message $$c_1=E(m)$$, another encrypted ciphertext $$c_2$$ that will be decrypted to the same message without knowing the key that was used for the encryption? I mean to create a $$D(c_2)=m$$ where $$c_1 \neq c_2$$

I am asking this because ElGamal from what I understand, this cryptosystem is not defined as injective because the results of the encryption depend on some random value.

To elaborate further on my thoughts: I think that ElGamal is not deterministic in the way each message can have several legal encryptions: for each of the $$p-1$$ of $$k$$, there would be a different encryption, but of course, the decryption will be reliable and return the same decrypted message: it will return the same $$x$$ without dependency on chosen $$k$$. So basically,

$$x\bmod p = x\cdot b^k\cdot (b^k)^{-1}$$ but $$x\cdot b^k =y_2$$ and

$$(b^k)^{-1} = (\alpha^{k\cdot a})^{-1}$$, and $$(y_1^\alpha)^{-1}=(\alpha^{k\cdot a})^{-1}$$.

So we get $$x \bmod p =(y_2)(y_1^\alpha)$$. Basically to encrypt we only need $$(p,\alpha,b)$$ and to decrypt we need the private key $$a$$.

I would very much appreciate understanding this.

The key is here the probabilistic Encryption

Probabilistic encryption is the use of randomness in an encryption algorithm, so that when encrypting the same message several times it will, in general, yield different ciphertexts

The first probabilistic encryption was proposed by Shafi Goldwasser and Silvio Micali Probabilistic encryption & how to play mental poker keeping secret all partial information in 1982. You randomize the encryption with a random for each message so that even the same messages get different encryptions.

This is why we call encryption can be probabilistic, but the decryption is deterministic. A plaintext can have different encryptions but all must decrypt to the original plaintext

To be semantically secure, that is, to hide even partial information about the plaintext, an encryption algorithm must be probabilistic.

• I think that ElGamal is not determinstic in the way each message can have several legal encryptions:

Yes, ElGamal is not deterministic. During the encryption, we select a random value for the encryption that makes each encryption different for the same ciphertexts. During the calculation of the shared secret, we select a random $$k \in\{1\ldots q-1\}$$ and continue with the following parameters; $$(G,q,\alpha,b)$$ as the public key;

• $$G$$ is the cyclic group
• $$q$$ is the size of $$G$$
• $$\alpha$$ is the generator of $$G$$
• $$b=\alpha^a$$ where $$a$$ is the private key.

Then the encryption performed as following;

1. select a random $$k \in\{1\ldots q-1\}$$
2. compute $$s = b^k$$ - the shared secret
3. compute $$c_1 = \alpha^k$$
4. compute $$c_2 = m\cdot s$$

If we encrypt $$m$$ with the random $$k$$ than the ciphertext pair is; $$(c_1,c_2)= (\alpha^k, m\cdot s)$$ Encrypting wiht a another random $$k' \neq k$$ will result in a different ciphertext; $$(c'_1,c'_2)= (\alpha^{k'}, m\cdot s'=b^{k'})$$

• Rerandomization: How to create new encryption of this cyphertext without knowing the plaintext and private key.

To rerandomize a ciphertext, take a new random $$k' \in\{1\ldots q-1\}$$ and calculate $$b^{k'}$$ and $$\alpha^{k'}$$ now mutiply the pair.

$$(c_1 \cdot \alpha^{k'},c_2 \cdot b^{k'}) = (\alpha^k \cdot \alpha^{k'}, m \cdot b^{k} \cdot b^{k'}) = (\alpha^{k+k'}, m \cdot b^{k+k'}) = (c_1'', m \cdot s'')$$

Therefore the new encryption is based on the combined shared secret which is $$b^{k+k'}$$. Of course, there is a problem that $$k+k'$$ can exceed the $$q-1$$, however that is no problem since the little Fermat theorem.

The two ciphertexts are different since $$\alpha^{k+k'} \neq \alpha^{k}$$.

Decryption:

1. $$s'' = (c_1'')^a$$, $$c_1'' = \alpha^{k''}$$ then $$(c_1'')^a = \alpha^{xk''} = \alpha^{k''}$$
2. Compute $$s''^{-1}$$ by ext-GCD.
3. Compute $$m=c_{2}\cdot s''^{-1} = m \cdot s'' \cdot s''^{-1} =m$$

Therefore the rerandomization works.

So in an ElGamal cipher text there are two pieces of information. A typical cipher text looks like this: ($$g^b$$, $$mg^{ab}$$)

So the answer to your question is it depends on how much you know about this cipher text message. You said you don't know the $$g^{ab}$$ (which is what most people would say is the key in this encryption), but suppose you know $$m$$, then of course. You can generate a different cipher text and here is what you do.

1. Choose random $$c$$ (different from $$b$$).
2. Grab $$g^a$$ (public key) from the receiver, compute $$(g^a)^c$$, compute $$g^c$$
3. Compute $$m \cdot g^ac$$
4. You have a new cipher text ($$g^c$$, $$m \cdot g^{ac}$$)
5. You send it, the recipient gets it, it will go compute $$(g^c)^a$$, then compute $$g^{-ac}$$, with that he can get m. Your new (and different) cipher text just decrypted into the same message.

On the other hand if you don't know m to begin with, (for example, you intecepted ($$g^{ab}\cdot m$$, $$g^b$$) from wireshark) then after a few minutes whiteboarding I can say I haven't found a way to do what you asked.

• This is incorrect. ElGamal encryption is well known to be perfectly rerandomizable. – Maeher Dec 17 '19 at 20:15
• Which part of the answer do you think is wrong? Note that my answer is exactly about how you can randomize ElGamal to produce different cipher texts from the same plain. – nuts-n-bits Dec 17 '19 at 20:20
• You claim that you need to know m to do so. Which is clearly wrong. – Maeher Dec 17 '19 at 21:44
• "then after a few minutes whiteboarding I can say I haven't found a way to do what you asked." - this might be correct (you haven't found a way), however it is certainly possible - see kelalaka's answer. – poncho Dec 17 '19 at 22:30
• I said you can do it with m, not you can't do it w/o m. I have no intention to mislead but since you all saw it that way, I'm sorry. – nuts-n-bits Dec 28 '19 at 5:44