[MBCook]

I tried to look homomorphic encryption up casually earlier this year. I saw references that it was being used, but I don’t think they said where.

This is one topic I have a very hard time with, I just don’t know enough math to really grok it.

It just seems crazy a system could operate on encrypted data (which is effectively random noise from the server’s point of view) and return a result that is correctly calculated and encrypted for the client, despite never understanding the data at any point.

I sort of understand the theory (at a very simple level) but my brain doesn’t want to agree.

[oblvious-earth]

Maybe it’s the fact it can be done with multiple operators and strong encryption that is hard to grok, but at least here is a very simple example of a limited partially homomorphic encryption:

You have a 7-bit character representation (e.g. ASCII) and your encryption is to add 1 mod 128. E.g. 0 -> 1, 1 -> 2, ... 126 -> 127, 127 -> 0.

As it turns out, all your operations can be represented as adding or subtracting constants. You can now encrypt your data (+1), send it to a remote server, send all the adding and subtracting operations, pull back the processed data, decrypt the data (-1).

Of course, this example is neither useful encryption nor generally useful operation, but can be useful for grokking why it might be possible.

[kmeisthax]

Let's say I want you to add two numbers, but I don't want you to know what those numbers are, nor what the result is. What I can do is multiply both numbers by some other number you don't know. I then give you the premultiplied numbers, you add them, and give back a premultiplied answer. I can then divide out the number to get the true result.

What we've done here is this:

(a * key) + (b * key) = (c * key)

The rules of elementary algebra allow us to divide out the key on both sides because of a few useful symmetries that addition and multiplication have. Namely, these two equations are always the same number:

(a + b) * key = (a * key) + (b * key)

This is known as the distributive property. Normally, we talk about it applying to numbers being added and multiplied, but there are plenty of other mathematical structures and pairs of operations that do this, too. In the language of abstract algebra, we call any number system and pair of operations that distribute like this a "field", of which addition and multiplication over real[0] numbers is just one of.

A simple example of a field that isn't the normal number system you're used to is a 'finite field'. To visualize these, imagine a number circle instead of a line. We get a finite field by chopping off the number line at some prime[1] number that we decide is the highest in the loop. But this is still a field: addition and multiplication keep distributing.

It turns out cryptography loves using finite fields, so a lot of these identities hold in various cryptosystems. If I encrypt some data with RSA, which is just a pair of finite field exponents, multiplying that encrypted data will multiply the result when I decrypt it later on. In normal crypto, this is an attack we have to defend against, but in homomorphic crypto we want to deliberately design systems that allow manipulation of encrypted data like this in ways we approve of.

[0] Also complex numbers.

[1] Yes, it has to be prime and I'm unable to find a compact explanation as to why, I assume all the symmetries of algebra we're used to stop working if it's not.

[tjade273]

A set of numbers with addition and multiplication is a _ring_ and is a _field_ only if every nonzero number has a multiplicative inverse.

Integers mod N for composite N (like in RSA) form a ring, not a field - if N = p*q then there is is no well-defined division by `p` or `q` (for example, there is no element corresponding to `2/p`).

When p is prime, every nonzero integer `x` has a multiplicative inverse `1/x` mod p. That's why the integers mod `p` form a field (denoted F_p).

In fact there is another kind of finite field that has `p^n` elements where `p` is any prime and `n` is any positive integer. These fields are not composed of the integers mod p^n, but are made of polynomials of degree `n` with coefficients in F_p.

[innermatrix]

Finite fields have multiplicative inverse only if the base is a prime, and that's what makes the rest of your usual algebra work (or not).

For example, for N = 5, 0 * 2 = 2, 1 * 2 = 2, 2 * 2 = 4, 3 * 2 = 1, 4 * 2 = 3, so the inverse of "* 2" is uniquely defined. On the other hand, for N = 4, 0 * 2 = 0, 1 * 2 = 2, 2 * 2 = 4, 3 * 2 = 2, so the inverse of "* 2" is not uniquely defined.

[rozap]

Thanks, this is a nice explanation. Appreciate the clarity.