How to encrypt data so you can still work with it.
I've just published a new a paper on quantum homomorphic encryption which is now available to read on arxiv for free here or from the journal here. This is my first paper during my affiliation at Singapore University of Technology and Design (SUTD) so I thought it would be appropriate to write an article explaining what the paper is about and why homomorphic encryption is going to be such an important topic in the coming years - both in the classical and quantum regimes.
What is homomorphic encryption?
I usually find this topic is best explained by example. Lets imagine a scenario: You are some person with some private data. Very private data. In fact, you don't want anoyone knowing what it is.
Now, imagine you want to run an algorithm on your data to give you some ouptut. You may think of this algorithm either as a mathimatical function being applied to an input or something more abstract (prehaps a filter on your photos).
Prehaps you have financial data and this algorithm will tell you whether your business would benifit from a merger, or if a stock price is likely to go up.
But you don't have the ability to run the algorithm. This may be because its very computationally intensive so you'd have to run it in the cloud using someone elses computer. Or maybe the algorithm has been developed by some other person who doesn't trust to give it to anyone else for fear they may copy it. What do you do?
Well - one solution is homomorphic encryption; here you would encrypt your data in a very special way. You have to encrypt it just that it is still malleable, that means you can still apply algorithms to the data and you will get some sort of encrypted answer which you can the decrypt. The encryption on the answer should only be dependent on the encryption of the original data, and not the algorithm applied to it. That way, if the algorithm i meant to be hidden from you, the designer doesn't need to tell you anything about the algorithm invoked.
With such a scheme you may run your data and give it to a third party who applys a function on it. They never know your data and you (may, if they wish) never know the function. This encryption would is homomorphic encryption.
So the scheme would work as follows.
- Encrypt your data
- Send this encrypted data to someone else with a computer and a program to run on the data
- They run the program
- They return some encrypted result back to you
- You decrypt this to to get your answer
Is this even possible?
Well, a few years ago, a scheme was preposed by Gentry showing that it is possible to do with classical computers -
this was a HUGE result.
However, as with alomst all classical encryption problems, its makes use of the assumption that certain problems are hard to solve
(in this specific application it is related a shortest path problem on ideal lattices). These assumptions are unproven one way or the other
(in fact proving them would be an incredibly important result in regards to complexity theory). But it got us wondering - could we do better with a qunatum computer?
Here in the quantum lab we really don't like making these kind of assumptions on the hardness of problem - instead aiming for information theoretic security. That is, for us, security guarenteed by the laws of nature.
One reason for this is if we do, one day, get a quantum computer then many of these assumptions on the hardness of certain problems become false (for example RSA key distribution, a relative to Dickie-Helman encryption which forms the basis of many of our day to day protocols, gets broken by Shors Algorithm which finds the prime factors of a number efficiently. This would be really really bad as many things, such as your bank account, and whatapp message, become insecure to anyone with a quantum computer and you are in effect at the mercy of hackers).
But prehaps if we USE quantum mechanics to do the encryption we can make a homomorphic encryption scheme which is secure, no matter what.
What is homomorphic encryption?Sounds good so far? Unfortunately there exists a no-go theorem (also coming out of our group in Singapore) that proves its such a scheme impossible to do this efficiently and with perfect information protection even if you use a quantum computer. Alas
But this is only for perfect security- what if you leak just a tiny tiny bit of information? Or what is the compuation has some fintie probability of failure? Then that would still be pretty useful! Thats the work around idea with this paper - we describe an encryption scheme that could potentially leak a tiny amount of information about your data, but it allows computation to be preformed on the encrypted data.
So how do you do it?
This result is achieved by allowing the operation that correspond to computation to commute with operations that do encryption and decryption (meaning they don't affect each other - this should be quite obvious when you think about how the scheme has to function). This is quite easy to accomplish in quantum mechanics by simply using the internal rotations on quantum states to be the encryption (like changing the basis of measurement - this is comparable to papers on random walks with encrypted data, and thus the boson sampling model of computation). The computation is then preformed on the spatial mode of the quantum objects - which could be, for example, acheived passively using linear optics.
Here we use group theoretic insights to give a general framework for constructing quantum homomorphic encryption schemes. These schemes that have two important advantages over their classical counterparts. First, they would allow non-classical computations to be performed, and second, their security is based on physical laws and not on computational assumptions. Our novel method relies on finding encryption and computation operators that commute with each other, and we show that computations from a unitary group of a large dimension are allowed. Non-trivial encryption operators can then be constructed and we prove that for a particular logical encoding, a constant fraction of the encrypted information can be hidden where this fraction can be made arbitrarily close to unity with overhead scaling only polynomially in the message length.
A particular instance of our encoding hides up to a constant fraction of the information encrypted. This fraction can be made arbitrarily close to unity with overhead scaling only polynomially in the message length. This highlights the potential of our protocol to hide a non-trivial amount of information, and is suggestive of a large class of encodings that might yield better security.
And you can run any algorithm?
Well not exactly. This is where caveats appear. To run any algorithm we would need to make sure that the operations the commute with the encryption/decryption from a universal set (any operation). The easy way to do this is to find a few operations which together are generators of a unversal set and make sure those commute.
In such a case the computation operations form a group, either the unitary group in the case of quantum computation or the symmetric group in the case of classical reversible computation, which does not usually commute with other operations... in fact any irreducible representation of these groups only commutes with operators proportional to the identity, precluding non-trivial encryption. However, for reducible representations of these groups, there can exist non-trivial operators which commute with the entire group.
Now - our work allows a REALLY BIG set of operations. But to be honest we are not clear about whether it's a universal set of operations... I orignally thought it should be, but it now appears that it isn't for group thoery reasons slightly beyond anyones grasp.
So the paper is on the ArXiv here. The reason that I have the image of marbling is that homorphic encryption schemes always remind me of this video about laminar flow... which is a pretty cool topic in itself.
Does this paper have implications for further reseach?
YES! This is the first paper on a quantum method for homomorphic encryption - and I am aware of a few follow on methods for similiar papers which should be coming out of the reseach group soon. This method is partictularly important to emerging industries such as cloud computing - and improves upon other methods such as universal blind quantum computing by allowing operations to be preformed in a single round of communication between the client with the data and the server prefroming the hidden calculation.