Homomorphic cipher is a cryptographic algorithm that lets you perform operations on the encrypted text.

It gets its name from the fact that there exists a mathematical homomorphism between the cleartext and the ciphertext. The very encryption procedure is the homomorphism. Suppose we have objects of some type (i.e. integers) and we can perform certain operation on them (i.e. addition). A cipher homomorphic with respect to addition will let you encrypt those numbers and still add them up.

ENCRYPTED(a) (+) ENCRYPTED(b) = ENCRYPTED(a + b)

Here "(+)" is the symbol of the operation on encrypted objects that reflects cleartext number addition. We say that this operation is a homomorphic image of addition.

The best known homomorphic cipher is RSA. It belongs to the family of ciphers that are based on modular exponentiation, which (as we all know) is a homomorphism between the group of numbers with modular addition and the group of numbers with modular multiplication. In fact, the homomorphic image of addition in RSA is multiplication. We have to multiply two encrypted numbers to get their encrypted sum.

exp(a) * exp(b) = exp(a + b)

A different similar cryptosystem based on exponentiation is the Paillier cryptosystem. It has the same homomorphic properties as RSA but is slightly more secure. What can you do in Paillier cryptosystem?

• You can add two numbers up.
• You can multiply a number by a cleartext constant.
• You can evaluate a linear polynomial with many variables and cleartext constant factors.
• You can add zero to any number and get a different encryption of the same number, providing malleability.

Unfortunately, you can't multiply two encrypted numbers. That is something Paillier cryptosystem can not do. As addition is the only operation you can perform on two encrypted numbers, this cryptosystem is said to be partially-homomorphic.

Are there better homomorphic algorithms? Yes and no.

If a cryptographic algorithm lets us perform both addition and multiplication on encrypted values, we say that it is fully homomorphic. Being able to make these two operation lets us in fact perform every computable function. Do such algorithms exist?

There is the Gentry's cryptosystem and the family of algorithms based on it. While this algorithm in theory is fully homomorphic, its efficiency in practice is unacceptable. Performing even the simplest computations on current hardware takes days or even weeks.

To reinstate, there is no practical fully homomorphic cryptosystem for today. However, research is ongoing, so maybe we will have some working solution soon.

What if we had fast fully homomorphic cryptosystem?

The usual scenario where we wanted to use homomorphic ciphers is when we delegate computations to somebody else, while still want to preserve secrecy of our data.

Suppose we want to serve an application in a cloud. Unfortunately, cloud providers are known for spying on their clients, peeking into their data and censoring based on their content.

What if we were able to upload encrypted data to the cloud, perform all the necessary calculations and send the user the encrypted result? Then the authorized user could decrypt the received result using a key in their possession. This way, we can host the application in the cloud, present results to selected users and the cloud provider can not learn anything about our data.

A different scenario is when the user itself wants to protect their privacy against the application provider. Suppose we are hosting an application holding a list of names. Some user wants to know if he is on the list, but he doesn't want to show us his name, nor we want to reveal the list to the user. How can we solve it with homomorphic encryption?

The user could send us his own public encryption key and his encrypted name, keeping his decryption key private. Then we can encrypt the list of names using the user's key, perform a search algorithm and send the user encrypted result whether his name was found. We don't know the user's name and we don't even know if it was found in our database. Only the user can decrypt the result with his private key and get the answer.

Homomorphic cryptography could also find applications in blockchains. We have implementations of "coins" like Bitcoin, where all transactions are open and publicly available. We also have private "coins" like ZCash that provide secrecy and anonymity. No one can learn the state of our account or the value of our transfers, thanks to cryptographic technique known as zk-snarks.

On the other hand we have Turing-complete blockchains like Ethereum that allow us to create smart contracts. They are also public and open, like Bitcoin. Is it possible to make a private equivalent of Ethereum, where the state of the contract is secret, while still the contract does the right thing? Yes, and it could be done with homomorphic encryption.

To sum up, fully homomorphic encryption is a very promising future technology, but still immature for today use. However seeing the progress the field of cryptography is experiencing, we could expect some breakthrough in a couple of years.