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$
$\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$– DrLecterMay 19, 2015 at 22:22
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
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$.