Homomorphic Encryption

A function that satisfies... 

f(x*y) = f(x)*f(y)

is called a homomorphism. The symbol "*" can stand for any operation, and it need not stand for the same thing on both sides of the equation. Technically * is the group operation, and if the function f maps elements of one group to another, the group operation may be different in the two groups.

Examples

Below are three examples of homomorphisms that people usually see before learning the term "homomorphism."

Exponential

For example, the function f( x) = e is a homomorphism where * stands for the addition of real numbers on the left and multiplication of positive real numbers on the right. That is:

e^x+y = e^x e^y.

In words, the exponential of a sum is the product of exponentials.

Determinants

Another example of a homomorphism is determinant. Let A and B be two n by n matrices. Then:

det(AB) = det(A) det(B).

In other words, the determinant of a product is the product of determinants. But "product" refers to two different things in the previous sentence. The first product is a matrix product and the second product is a product of real numbers.

Fourier Transform

One last example of a homomorphism is the Fourier transform F. It satisfies

F(f * g) = F(f) F(g)

where the group operation * on the left is convolution. In other words, the Fourier transform of the convolution of two functions is the product of their Fourier transforms.

Homomorphic Encryption

Homomorphic encryption is an encryption algorithm that is also a homomorphism. It allows the recipient of encrypted data to encrypt the result of some computation without knowing the inputs. I give three examples below.

Simple Substitution

Here's a trivial example. Suppose you have a simple substitution cipher, i.e. every letter is simply replaced by some other letter. This is homomorphic encryption where the group operation is string concatenation [1]. If you encrypt two unknown words as xxw and jkh, I know that the encrypted form of the two words stuck together is xxwjkh.

A block cipher like AES is also homomorphic with respect to concatenation if implemented naively. That is:

E(A + B) = E(A) + E(B)

where + means concatenation. The encrypted form of the concatenation of two blocks is the concatenation of the two blocks encrypted separately.

The approach is called Electronic Code Book or ECB mode. It's never used in practice. Instead, you might use something like Cipher Block Chaining, CBC mode. Here the encrypted form of one block is XOR'd with the next clear block before encrypting it. [2]

An important point here is that when we say an encryption method is homomorphic, we have to say what operations it's homomorphic with respect to. Being homomorphic with respect to concatenation is not useful, and is, in fact, a weakness.

Goldwasser-Micali

A non-trivial example is the Goldwasser-Micali algorithm. If you're given the encrypted form of two bits, you can compute an encrypted form of the XOR of the two bits without knowing the value of either bit. Specifically, bits are encoded as large numbers modulo a public key. If c₁ and c₂ are encrypted forms of bits b₁ and b₂, then c₁c₂ is an encrypted form of

The same bit can be encrypted in many different ways, so this isn't a homomorphism in the simplest mathematical sense. That's why I said "an encrypted form" rather than "the encrypted form." This is common in homomorphic encryption.

Paillier

The Paillier encryption algorithm is something like RSA, and is homomorphic with respect to the addition of messages. That is, if you encrypt two messages, m₁ and m₂, and multiply the results, you get something that decrypts to m₁ + m₂. Here, the addition and multiplication are modulo some large integer.

As with the G-M algorithm above, encryption is not unique. Decryption is unique, but there's a random choice involved in the encryption process. The recipient of the encoded data is able to compute an encrypted form of their sum.

The Paillier algorithm lets you encrypt two numbers and have someone securely add them for you without learning what the two numbers were. That doesn't sound very exciting in itself, but it's a useful building block for more useful protocols. For example, you may want to let someone carry out statistical calculations on private data without letting them see the data itself.

References

[1] Strings with concatenation don't form a group because there are no inverses. So technically, we have a homomorphism of semigroups, not groups.

[2] There's a famous example of the weakness of ECB mode using the Linux penguin logo. If you encrypt the logo image using ECB mode, you can still recognize the penguin in the encrypted version since repetitive parts of the original image corresponding to repetitive parts of the encrypted image. If you use CBC mode, however, the encrypted image becomes white noise.