Most of the time I use this blog to write about things I understand, so it was something of an experiment when on Sunday evening I wrote a short post about something I did not understand.

I wrote the post quickly, and posted a link to Twitter. In a shameless bid to get a few more people interested, I then tweeted:

A test of the power of Twitter. Can I reach someone who understands homomorphic encryption, and is willing to help a confused soul? (link)

I should have known better than to challenge the Power of Twitter, because that sparked a frenzy of retweeting. And so I learnt that Twitter is home to a great many kind generous people who like nothing better than to come to the aid of a stranger who calls for help — though unfortunately none of these people knows anything about homomorphic encryption.

Colin Wright was also kind enough to post my question to Hacker News, which led to a depressingly ill-informed but mercifully brief discussion there.

But it worked out well, because somehow or other David Cash found my post. David understood what I was asking, knew the answers, and explained them clearly and succinctly. Thanks, David.

For the benefit of anyone else who is curious, I should explain briefly what I’ve learnt – though I suggest you also look at David’s comments.

In the simplest proof-of-principle presentation of homomorphic encryption, each bit is encrypted separately. I failed to realise this, because I hadn’t understood that the encryption is randomised so the encryption process is unlikely to give the same result twice even when encrypting with the same key. This randomisation protects against the re-encryption attack I mentioned, though of course it means that each encrypted bit must be a lot bigger than one bit, so there is a substantial blow-up in size when encrypting the data.

So as long as there is a way to perform (say) the AND and XOR operations on encrypted values – which there is, since they correspond to multiplication and addition modulo 2 – it’s possible to perform some arbitrary computation with the encrypted values.

There is a little mathematics to be found here as well. It’s something that I probably ought to have known all along; but I didn’t, or if I ever did then I had forgotten, so perhaps you will also find it interesting.

**Claim**. If F is a finite field, then every function F^{n}→F can be represented by a polynomial in n variables.

This is not hard to prove, and it’s always more enlightening to prove something oneself than to read someone else’s proof, so I shan’t give it away. If you haven’t seen this before, and you like that sort of thing, do feel free to write your proof in the comments.

If c is any element of the (N-element) finite field F, consider the product of all the polynomials (X-d) as d ranges over all elements of F other than c. This is a polynomial in one variable of degree N-1 that evaluates to value 0 when X is not equal to c, and has value -1 at X = c. (Because every non-zero element of F has a multiplicative inverse and we are multiplying all the pairs of mutually inverse elements together, except for +/-1 which are self-inverse—or the same, in a field of characteristic two.)

These polynomials in X clearly form an F-linear basis for the set of functions mapping F to F. And by multiplying together a basis polynomial in X with a basis polynomial in Y, we get a polynomial in two variables of degree 2N-2 which isolates an element of FxF; between them these form a basis for the functions of two variables. Et cetera.

(A LaTeX-free proof. It’s like working in constructivist logic.)

I think perhaps you

areallowed in the comments. But I’m not sure, so this comment is an experiment.Edited to add: Ah good, that worked. You just have to surround your code with`$latex … $`

.