I am somewhat familiar with current research on fully homomorphic enryption schemes and their possible application to Cloud computing.

I've just noticed (somewhat late) that a marketing-savvy group of Physicists working on quantum information is approaching the same possible application: they call their approach blind quantum computing.

Is this a serious contender with respect to the claimed application (the group's reputation in Physics is not in doubt) and are there any significant similarities between the two approaches on a fundamental level?

  • 1
    $\begingroup$ It appears to require a quantum computer and thus is not a serious contender for cloud computing applications. $\endgroup$ – David Cash Dec 23 '12 at 19:31

Well, since I'm one of the authors on the paper, let me try to answer your question.

First I should explain that the paper you link to is not the original paper proposing that approach, but rather the first implementation of it (in this case using quantum optics). The original paper which introduced the Universal Blind Quantum Computing (UBQC) protocol which the experiments demonstrate was written by myself along with Anne Broadbent and Elham Kashefi, and appeared at FOCS in 2009, so at least some people in the CS community took us seriously. I should also point out that of the three of us, only I am a physicist. Elham and Anne are both computer scientists. Indeed Anne's PhD supervisor was Gilles Brassard, one of the Bs in BB84, and one of the discovers of quantum key distribution.

One might ask why our original paper doesn't reference fully homomorphic encryption, but that is easy to answer. It simply didn't exist when we wrote the paper in 2008.

As David Cash mentions in the comments above, UBQC is a quantum protocol, and hence requires quantum information processing, meaning at least some quantum computational abilities. It is certainly not something you can expect to deploy tomorrow, and any large scale version of this kind of thing is likely decades off. We worked with one of the top experimental groups to implement it, and still only managed 4 qubits (essentially hiding a 12 bit description of the circuit).

Now, we're certainly not the only ones to have written about the concept of blind quantum computation. The term is taken from a 2003 paper by Arrighi and Salvail which introduced a non-universal blind computation protocol, although there was earlier work by Childs. A few months after us, and apparently independently, Aharonov, Ben-Or and Eban came up with a similar idea in the context of interactive proofs.

There are some important differences between blind quantum computing and homomorphic encryption. First, blind computation and homomorphic encryption are fundamentally different in what they seek to achieve. In blind computation the aim is to have a remote computer perform a computation for you in such a way that it remains "blind" to the computation (i.e. the input, output, and the actual computation performed), and should only learn upper bounds on the resource requirements. In homomorphic encryption the situation is somewhat different, since while the intention is indeed to hide the input and output, the computation itself is known to the remote computer and not necessarily to the user. This is a fundamental difference in the goals of the various protocols. Secondly, protocols such as ours and the Aharonov-Ben-Or-Eban approach, take measures to ensure that the remote computer cannot interfere with the protocol without being detected, which is in completely the opposite direction to homomorphic encryption. Thirdly, there is a fundamental difference in security. Many of the blind quantum computation protocols are information theoretically secure, meaning that they are secure independent of the computational power of their adversary. This is not true of current schemes for fully homomorphic encryption. And, last, but certainly not least, blind quantum computing allows you to essentially boost the computational power of the user, in computational complexity terms, expanding the class of decision problems they can solve from P to BQP, which contains certain problems believed to be NP-intermediate problems such as factoring, which is not something fully homomorphic encryption currently allows for.

Let me close by saying why I think people should be interested in blind quantum computation. As I have said, as a tool for cloud computing, practical technologies would be decades off, and I certainly don't want to be guessing the future that far in advance. Rather, I would suggest, the main reason people currently find such protocols interesting is because of their possible consequences for the study of complexity classes, and as a practical means for verifying that purported quantum computing technologies do indeed function correctly (which is a non-trivial task since BQP is believed not to be contained in NP, and hence there exist no efficient means to verify the outcome of certain quantum computations after the fact).

I hope this helps answer your question.


Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.