Homomorphic encryption

Homomorphic Encryption is a form of encryption where one can perform a specific algebraic operation on the plaintext by performing a (possibly different) algebraic operation on the ciphertext. Depending on one's viewpoint, this can be seen as a positive or negative attribute of the cryptosystem. Homomorphic encryption schemes are malleable by design and are thus unsuited for secure data transmission. On the other hand, the homomorphic property of various cryptosystems can be used to create [http://web.mit.edu/6.857/OldStuff/Fall02/handouts/L15-voting.pdf secure voting systems] (pdf), collision-resistant hash functions and private information retrieval schemes.

There are several efficient Homomorphic cryptosystems:

*RSA Cryptosystem
*ElGamal cryptosystem
*Goldwasser-Micali cryptosystem
*Benaloh cryptosystem
*Okamoto-Uchiyama cryptosystem
*Paillier cryptosystem
*Naccache-Stern cryptosystem
*Damgård-Jurik cryptosystem
*Boneh-Goh-Nissim cryptosystem

Examples

In the following examples, we use the notation $mathcal\{E\}(x)$ to denote the encryption of the message "x".

Unpadded RSA

If the public key is "m","e", then the encryption of a message "x" is given by $mathcal\{E\}(x)\; =\; x^e\; mod\; m$. Then we have the homomorphic property

:$mathcal\{E\}(x\_1)\; cdot\; mathcal\{E\}(x\_2)\; =\; x\_1^e\; x\_2^e\; mod\; m\; =\; (x\_1x\_2)^e\; mod\; m\; =\; mathcal\{E\}(x\_1\; cdot\; x\_2\; mod\; m)$

ElGamal

In a group $G$, if the public key is $(G,\; q,\; g,\; h)$, where $h\; =\; g^x$, and $x$ is the secret key, then the encryption of a message $m$ is $mathcal\{E\}(m)\; =\; (g^r,xcdot\; h^r)$, for some $r\; in\; \{0,\; ldots,\; q-1\}$. Then we have the homomorphic property

:$mathcal\{E\}(x\_1)\; cdot\; mathcal\{E\}(x\_2)\; =\; (g^\{r\_1\},x\_1cdot\; h^\{r\_1\})(g^\{r\_2\},x\_2\; cdot\; h^\{r\_2\})\; =\; (g^\{r\_1+r\_2\},(x\_1cdot\; x\_2)\; h^\{r\_1+r\_2\})\; =\; mathcal\{E\}(x\_1\; cdot\; x\_2)$

Goldwasser-Micali

If the public key is the modulus "m", and quadratic non-residue "x", then the encryption of a bit "b" is $mathcal\{E\}(b)\; =\; r^2\; x^b\; mod\; m$. Then we have the homomorphic property

:$mathcal\{E\}(b\_1)cdot\; mathcal\{E\}(b\_2)\; =\; r\_1^2\; x^\{b\_1\}\; r\_2^2\; x^\{b\_2\}\; =\; (r\_1r\_2)^2\; x^\{b\_1+b\_2\}\; =\; mathcal\{E\}(b\_1\; oplus\; b\_2)$

where $oplus$ denotes addition modulo 2, (i.e. exclusive-or).

Benaloh

If the public key is the modulus "m", the base "g" and the blocksize "r", then the encryption of a message "x" is $g^x\; u^r\; mod\; m$. Then we have the homomorphic property

:$mathcal\{E\}(x\_1)\; cdot\; mathcal\{E\}(x\_2)\; =\; (g^\{x\_1\}\; u\_1^r)(g^\{x\_2\}\; u\_2^r)\; =\; g^\{x\_1+x\_2\}\; (u\_1u\_2)^r\; =\; mathcal\{E\}(x\_1\; +\; x\_2\; mod\; phi(m)/r\; )$

Paillier

If the public key is the modulus "m" and the base "g", then the encryption of a message "x" is $mathcal\{E\}(x)\; =\; g^x\; r^m\; mod\; m^2$. Then we have the homomorphic property

:$mathcal\{E\}(x\_1)\; cdot\; mathcal\{E\}(x\_2)\; =\; (g^\{x\_1\}\; r\_1^m)(g^\{x\_2\}\; r\_2^m)\; =\; g^\{x\_1+x\_2\}\; (r\_1r\_2)^m\; =\; mathcal\{E\}(\; x\_1\; +\; x\_2\; mod\; m)$

Open question

While these examples allow one-to-one group operation on plaintexts (either addition or multiplication in these examples), no one has created a cryptosystem which preserves the ring structure of the plaintexts, i.e. allows both addition and multiplication. The best result in this direction is the Boneh-Goh-Nissim cryptosystem which, through operations on the cipthertext, allows addition of plaintext followed by a single multiplication followed by an arbitrary number of additions. This allows evaluation of polynomials of degree 2 on the plaintext through operations on the ciphertext. The system is only practical when the space of plaintexts is relatively small.

References

* [http://www.adastral.ucl.ac.uk/~helger/crypto/link/public/homomorphic.php Homomorphic encryption] in [http://www.adastral.ucl.ac.uk/~helger/crypto/ Cryptology Pointers]
* [http://www.cs.virginia.edu/~pev5b/writing/academic/thesis/node7.html Homomorphic encryption]
* [http://citeseer.ist.psu.edu/726875.html Sufficient conditions for collision-resistant hashing]