Homomorphic Encryption

We will talk in this post about a very useful cryptographic tool. But lets talk first about the motivation or the problem it solves first.

As the first example, we will introduce the private voting problem:
We want to make an online voting application, no one can know what anyone else has voted (not ever the server itself), but at the end, we will know how many votes each candidate has received. The problem is even harder if there is no "central" trusted server and it is a distributed system which all nodes interact with all others and no one can trust anyone else.

Now, lets introduce homomorphic encryption. Homomorphic encryption, is an encryption system which allows you to do calculations on the encrypted data, without knowing the original text. At the end you will get the encryption of the result, not the result itself.

Caution: the notation used is simplified and there are some details that are not mentioned in order to simplify the presentation.

To make it more elaborate, assume $a, b$ are plain texts, and $E(a), E(b)$, are their encryption. If the encryption system you are using allows for addition, you can then call $Add(E(a),E(b))$ and you will get $E(a+b)$.

Ok, so how can this help us in our voting problem ? We will describe the protocol to show how. There is a node which will start the voting, it is the only node that can decrypt values. He will send his vote $v_1$, either 0 or 1, encrypted to the the next node. The next node will take the encrypted vote and adds his encrypted vote, either 0 or 1, and forwards it to the next one, and so forth, in a ring-like fashion, until it reaches the first node again. The first node will then decrypt and will find the sum of the votes for the first candidate. This is repeated for each candidate.

Homomorphic encryption has a lot more applications, and is more sophisticated that the simplified version mentioned here. For example, it usually has "semantic" security, which means that it is a probabilistic encryption, which means that every time you encrypt the same value, you will get a different cipher text. That is, if two people sent you $E(1)$, you will not be able to know it is the same value just by looking at the cipher text alone. Also, there are encryption schemes that only allows for addition, and others that only allow for multiplication. There is one that allows for addition and only one multiplication. Those who supports unlimited number of addition and multiplication are called "algebraic homomorphic encryption", or "fully homomorphic". So far, fully homomorphic schemes incur very big overhead for practical purposes.

Note that homomorphic properties are usually intended in a cipher. If a cipher had these properties and it was not intended, it is called "malleable" encryption and it is considered a flaw instead. Remarkable homomorphic cryptosystem are RSA, ElGamal, and Paillier.

Note also that these schemes are also asymmetric. So anyone with public key can encrypt a value, but can not decrypt it except with a public key.

References:
- Pascal Paillier: Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. EUROCRYPT 1999:223-238

- http://en.wikipedia.org/wiki/Homomorphic_encryption


Author: Mohammad Alaggan