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 &amp; 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;


select a random $k \in\{1\ldots q-1\}$ 
compute $s = b^k$ - the shared secret
compute $c_1 = \alpha^k$
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:


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


Therefore the rerandomization works.