Quantum inspired classical results

on

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.

7 Comments

  1. Twitter Comment


    RT @HCIR_GeneG: Posted “Quantum inspired classical results” by Eleanor Rieffel [link to post]

    Posted using Chat Catcher

  2. Twitter Comment


    Posted “Quantum inspired classical results” by Eleanor Rieffel [link to post]

    Posted using Chat Catcher

  3. Anonymous cryptographer says:

    The quantum-reduction technique used in Gentry’s paper is actually due to Oded Regev, from his paper “On lattices, learning with errors, random linear codes, and cryptography.” Gentry then uses Regev’s algorithm as a “black-box” in his setting.

  4. Anonymous cryptographer – Thanks for the clarification. Yes, Gentry makes clear that he is using Regev’s reduction from the 2005 paper you mention in which Regev uses it to prove the security of the lattice-based cryptosystem he develops there. It is exciting to see the same quantum reduction used again, this time in Gentry’s work.

    For four years Regev’s proof using the quantum reduction was the only security proof for his lattice-based cryptosystem. This year Peikert provided a classical security proof here. Peikert points out that the hardness result that underlies the new proof is incomparable to Regev’s original one. The new one is based on a decision problem, where as the original is based on a stronger search problem, but at the cost of requiring quantum computation as part of the reduction. The same situation holds for the two security proofs of Gentry’s result.

  5. Greg Kuperberg says:

    Hi folks. Eleanor also suggested that I mention my quantum proof of Johansson’s theorem in arXiv:math/9909104 and arXiv:math/0202035.

    In a nutshell: Johansson’s theorem concerns the limiting RSK shape of a long word in a fixed alphabet with k letters. He proves that this shape converges in distribution to the spectrum of a familiar type of k x k random matrix. In my proof of this result, I obtain the entire matrix. The entries are quantum random variables that do not commute for any fixed word length, but they converge to commuting as the word length goes to infinity.

  6. Greg — It is exciting to have another example of a quantum inspired classical result in addition to the ones mentioned in Drucker and de Wolf’s survey. Gentry’s result is very recent, but yours is early. Skimming Drucker and de Wolf’s survey suggests it is older than all of the examples they describe except the Cleve et al paper on the communication complexity of the inner product function.

  7. [...] my post on quantum inspired classical results, I gave as one example Gentry’s recent discovery of a fully homomorphic encryption scheme. His beautiful work deserves its own blog post. [...]

Comments are closed.