In yesterday’s post, I mentioned that one of my favorite topics is classical results informed by the quantum information processing viewpoint. There are now sufficiently many such results that Drucker and deWolf have written a survey, “Quantum Proofs for Classical Theorems.” I was surprised last month, when another such example popped up in one of the biggest cryptographic results of 2009, Craig Gentry’s discovery of a fully homomorphic encryption scheme.
Fully homomorphic encryption enables arbitrary computations to be performed on encrypted data without first decrypting. For example, suppose you store your data in encrypted form on a cloud service provider. Doing so severely limits what computations, including searches, the service provider can do for you. That is, unless you encrypt under a fully homomorphic scheme. If you use a fully homomorphic scheme, the service provide can perform any computation you want and return to you the encrypted result which you can then decrypt. In the process, the service provider learns nothing about your data values or the value of the final result. Whether a fully homomorphic scheme exists had been a long standing open question, first asked by Rivest, Adleman and Dertouzos in 1978. Gentry’s fully homomorphic scheme is not yet practical – for standard security parameters, it takes about a trillion times longer to compute the result than it does on unencrypted data – but it isn’t as impractical as it could be (a trillion is a lot better than 10^200, for example), and there is hope in the cryptographic community that some of the key ideas can be used to create a more practical scheme.
So what does Gentry’s result have to do with quantum computation? In his paper, he gives one security proof. In his thesis, however, he goes to a lot of trouble to give an additional, possibly stronger, security proof. This second proof relies on quantum computation. More specifically, whenever a new cryptographic protocol is designed, its security must be established. Empirical testing of a protocol takes a long time. Instead, whenever possible, reduction proofs are given that show that if the protocol were broken it would imply a solution to a problem believed to be hard. Gentry’s first proof reduces the security of his protocol to a plausibly hard problem, but not one that has been extensively studied. His second proof reduces the security of his protocol to a well-established hard problem, but the reduction require a step for which only an efficient quantum algorithm is known. This reduction means that if the protocol is broken then there is an efficient quantum algorithm for the well-established hard problem. It says nothing about whether an efficient classical algorithm exists.
My favorite example, by the way, of a quantum inspired classical result is Aaronson’s sleek proof of a notorious conjecture about the complexity class PP. The question was posed in 1972, and answered first in 1995. In 2005, Aaronson provided a page long argument that the quantum complexity class PostBQP = PP. From there, the proof of the original conjecture takes three lines. Thus, for some purposes at least, the correct way to view a purely classical complexity class is through the eyes of quantum computation.