1
$\begingroup$

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?

$\endgroup$
1
  • $\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, 2015 at 22:22

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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