## Fully homomorphic data encryption

In this day and age of free-flowing information everywhere, cryptography is a very hot topic. There has always been demand for better ways of encoding sensitive messages, but it is only really since the advent of the internet that this has taken on great importance in everyday life. Now that it looks likely computing will be increasingly outsourced to “cloud servers” in the future, a whole new form of encryption is necessary, and recent advances which have been made in the subject look set to make this kind of internet-based computing possible.

People have been encoding messages probably ever since the first advanced civilisations. The first codes were simple “monoalphabetic substitution ciphers”, the name of which is fairly self-explanatory. I want to straight away try to start talking about encryption methods in terms of mathematical functions though, as this will be important later when I explain homorphic encryption. So we can think of a monalphabetic substitution as a bijective function from an alphabet to itself. The function is the key to the code (it tells us which letter is substituted for which), and being bijective just means, firstly, that each letter is taken to only one other by the code; and secondly, that every letter has some corresponding one that is mapped to it.

More complicated are polyalphabetic substitutions. In this case there is not just one function from the alphabet to itself, but many – the function used changes as the message progresses, and the key to decoding the message is not just which functions are used, but also which is being used at any given time. For example, it might be that the first letter of a message is shifted one letter up, the second is shifted two, and so on. The number of bijective functions from the Roman alphabet to itself is$26! = 26\times 25\times 24\times \ldots,$which is a rather large number (try typing$26!$into google). And so while many polyalphabetic substitution use just a few different functions (in the case of the “letter-shifting” I mentioned, there would be cycle of only 26), these types of encryption systems could potentially use a different alphabet for every letter in the message.

The encryption method used by the German “Enigma” machine was essentially just polyalphabetic substitution, albeit a rather complex one, in which the function used at any given time was determined by the position of multiple rotors. The Enigma code was notoriously difficult to break – in fact it probably wouldn’t have been possible at all if certain documents had not been intercepted by the Allied military intelligence. These documents were “key tables”, which contained instructions as to how to set up the machine on a given day; using these in conjunction with their knowledge of the machine’s workings, cryptanalysts were able to crack the code.

It is the case with any encryption system that these two pieces of information are needed in order to decrypt a message: the algorithm, and the “key”. This used to mean that whenever an encoded message was sent, there had to at some point be a transfer of keys between the sender and recipient. Clearly this was not an ideal situation, as demonstrated by the German’s trouble with the Enigma machine.  If the key was somehow intercepted, then as long as a potential code-breaker knew which system was used to encrypt the message, he could decode it.

All this changed in the mid-70′s with the invention of public key cryptography. In public key encryption systems, two keys are used: a “public key”, which is used to encrypt information, and a “private key”, which is used to decrypt it. It works as follows: you broadcast your public key to anyone who might want to send you a message. They use this to encrypt a message and send it to you. The message can only be decrypted with your private key, which as the name suggests, you keep private. It is the invention of this kind of system which made the internet feasible: if you stop and think of the number of people you regularly exchange information with, it seems clear that it would be highly impractical and insecure to have to give them all a copy of your key. There are a lot of people out there who are very interested in your information, have the means to intercept your data-flow, and don’t feel like paying the owners of Facebook for the privilege of using it…

Up until now, public key encryption has served its purpose perfectly well. But there are some contexts in which a more advanced system is required, and foremost among them is the aforementioned cloud computing, which is is the practice of outsourcing computing needs to vast server-farms – or “clouds” – via the internet. This is widely believed to be the direction in which computing is heading…already there are many companies who find it more economically viable to pay for someone else to do some or all of their computing rather than take on the cost and labour of upkeeping their own data centres. And with the advent of operating systems like Chrome, and increasingly fast broadband connections, it seems likely that before long we will be doing all of our computing over the internet.

There is a problem with the security of this system though: in order to have someone else do your information-processing for you, it has previously been necessary to give them access to your key, thus potentially exposing sensitive information to a huge number of people, and negating the benefits of public key encryption. And this is where homorphic data encryption comes in. “Homomorphic” is a term from algebra, meaning “same shape”; if two algebraic structures are homomorphic, then there is a homomorphism between them, that is a map or function which preserves certain properties of those structures. It is a fundamental concept in mathematics, as it enables us to study objects indirectly by considering similar ones. Indeed it is often said that mathematics is the study of relations between things, rather than the things themselves.

Given my mission statement of “maths for the masses”, this blog is not an appropriate place to go into formal mathematical definitions.  For the purposes of this post, all you need to know about homomorphisms is that they enable us to manipulate mathematical objects “remotely” via operations in a different context.  But I will try to briefly explain with a simple example: suppose that we have two groups (I gave a rough definition of a group in this post) – each having the operation “multiplication” – and take any two elements of the first group.  A map from one group to the other will transform each of these numbers into elements of the second group.  If this map is a homomorphism, then it means that if we take the product of the first two numbers and map it to the second group, then we will get the same result as if we had mapped the two numbers to the second group and then taken their product.  Of course, we might not be talking about a group with a multiplication operation.  There are ring homomorphisms, vector space homomorphisms, even homomorphisms between groups of homorphisms!

But what has all this do with cryptography?  Well, when we talk about “information” in computing, we are just referring to strings of 1′s and 0′s. And when we talk of “processing” this information, really all we mean is changing these patterns of 1′s and 0′s to other patterns of 1′s and 0′s.  And it turns out that any conceivable transformation of binary information can be carried out by repeated application of just two logical operations: AND and XOR.  Each of these operations takes an input of two binary digits, and returns another one depending on these inputs.  An AND gate will return a 1 if and only if the two inputs are 1, while a XOR gate will return a 1 if and only if just one of the inputs is a 1.  These two operations correspond precisely to, respectively, multiplication and addition in the field of two elements (that is, they encapsulate the rules for multiplying and adding binary digits).

Now, as I mentioned earlier, we can think of an encryption system as a function; in the case of computerised data, the function will not be between alphabets, but from the “space of binary information” to itself.  If the function were a homomorphism, then it would mean that any additions or multiplications of digits would be preserved by the encryption.  As any information processing consists of just these two operations performed countless times, this means that we could encrypt some information, process it to our heart’s content, and then decrypt it, and we would get exactly the same result as if we’d just performed the same procedures on the original information.

To find a fully homomorphic encryption system – that is, one which preserves unlimited AND and XOR operations –  has been something of a holy grail for cryptographers for some time now.  Just last year it was announced that such a system has been created by a computer scientist called Craig Gentry, and while it is still very much in an experimental phase, the implications of this are huge.  It means that we could potentially send encrypted data anywhere to be processed without anyone ever actually decrypting the data.  We could outsource even the most sensitive computing, safe in the knowledge that no-one will ever actually know what it is they are working on.  And so, in the same way that public key encryption became feasible just in time for technology to enable the internet, now fully homomorphic data encryption is about to become a reality – just as broadband speeds, server sizes, and a whole host of other factors seem to  be coming together to enable the next computer revolution.  Nice how these things work out.