1. Homomorphic Encryption

1.1. Definition

The encryption algorithm \(E()\) is homomorphic if given \(E(x)\) and \(E(y)\), one can obtain \(E(x~op~y)\) without decrypting \(x\) and \(y\).

The \(op\) is for addition / multiplication (XOR / AND for bits).

  • partially homomorphism : arbitrary addition or multiplication

  • fully homomorphism: arbitrary addition and multiplication

1.2. Example

  1. RSA:

Let \(c_1 = E(M_1)\) and \(c_2 = E(M_2)\),

\[\begin{split}c_1 \cdot c_2 =& E(M_1) \cdot E(M_2) = M_1^e~mod~n \cdot M_2^e~mod~n \\=& M_1^e \cdot M_2^e ~mod~n = (M_1M_2)^e~mod~n\\=& E(M_1M_2).\\\end{split}\]

So RSA has multiplicative homomorphism.

  1. ELGamal

For a cyclic group \(G\) order of \(q\) and generator \(g\),

  • public key: \((G, q, g, h)\) where \(h=g^x\)

  • private key: \(x\)

\[\begin{split}&E(M_1) = (g^{r_1}, M_1 h^{r_1}), E(M_2) = (g^{r_2}, M_2 h^{r_2})\\ &E(M_1)E(M_2) = (g^(r_1+r_2), (M_1M_2)h^(r_1+r_2)) = E(M_1M_2)\end{split}\]

ElGamal also has multiplicative homomorphism.

  1. GM:

For \(E(b_1) = x^{b_1} r_1^2~mod~n\) and \(E(b_2) = x^{b_2} r_2^2~mod~n\)

\[E(b_1) E(b_2) = (r_1 r_2)^2 X^{b_1+b_2} = E(b_1 \oplus b_2).\]

GM has additive homomorphism.

We need better homomorphic algorithms because all the algorithms above are neither semantic secure nor support fully homomorphism.