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 Fn→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.