How can I compute homomorphic multiplication in ElGamal? That is: Given two ciphertexts $(R_1,c_1)$ and $(R_2,c_2)$ corresponding to plaintexts $m_1$ and $m_2$ under some public key; how can I compute a ciphertext $(R,c)$ that is an encryption of $m_1\cdot m_2$ under that same public key?

  • $\begingroup$ Just apply the group operation componentwise to the ciphertexts. No, you dont need the messages. Btw. shouldnt be that hard to find a resource after seconds of searching the web. $\endgroup$ – DrLecter May 19 '15 at 22:22

Assume we are working in a cyclic group $G$ with generator $g$ and let $A$ denote the public key in use.

From the definition of ElGamal encryption, we have $R_i = g^{r_i}$ and $c_i=A^{r_i}\cdot m_i$, where $r_i$ is some random number, for $i\in\{1,2\}$. Hence, with $R:=R_1\cdot R_2$ and $c:=c_1\cdot c_2$ (where $\cdot$ denotes $G$'s operation), we have obtained $$ R = g^{r_1}\cdot g^{r_2} = g^{r_1+r_2} $$ and $$ c = A^{r_1}m_1\cdot A^{r_2}m_2 = A^{r_1+r_2}\cdot m_1m_2 \text, $$ so $(R,c)$ is precisely an encryption of the message $m_1\cdot m_2$.

| improve this answer | |

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.