# How to implement homomorphic multiplication for Elgamal?

I want to add the homomorphic property to Elgamal in libgcrypt.

This is the core code I added to the library.

static void
do_homo_mul (gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t data1_a, gcry_mpi_t data1_b, gcry_mpi_t data2_a, gcry_mpi_t data2_b, ELG_public_key *pkey)
{
mpi_normalize (data1_a);
mpi_normalize (data1_b);
mpi_normalize (data2_a);
mpi_normalize (data2_b);

mpi_mulm (a, data1_a, data2_a, pkey->p);
mpi_mulm (b, data1_b, data2_b, pkey->p);
}


But I cannot get the right result. What is wrong with my code?

• Could you explain the parameters and the variables? Maybe comment each line... – Hilder Vitor Lima Pereira Dec 20 '14 at 15:34

If $(R_1,c_1)=(g^{r_1}, A^{r_1}m_1)$ and $(R_2,c_2)=(g^{r_2},A^{r_2}m_2)$ are ciphertexts (with respect to the same public key $A$) corresponding to two messages $m_1$ and $m_2$, then $$(R_1R_2,c_1c_2)=(g^{r_1+r_2},A^{r_1+r_2}m_1m_2)$$ is an encryption of the message $m_1m_2$ (note that the calculations are performed in $\mathbb Z/p\mathbb Z$, that is, modulo $p$).

Assuming that mpi_mulm(r, x, y, m) denotes the computation $r=xy\bmod m$ (which quick inspection of the GnuPG source code seems to confirm), this implies that (a, b) should indeed decrypt to the product of the plaintexts corresponding to (data1_a, data1_b) and (data2_a, data2_b).

This, in turn, likely means your correctness checks are flawed. If you care to post some example data and/or code, I can take a further look at the problem.