Blind quantum computing — generic structure variable selection

Question

Background

Recently I came upon a research article entitled Experimental Demonstration of Blind Quantum Computing. Within this research article, the scientists claimed that - through the proper choice of a generic structure - a data engineer can hide the information about how the data was calculated.

Question

If a scientist were to use a BQC (Blind Quantum Computation) protocol to calculate private measurements, what types of variables would they have to use to formulate a generic structure for the blind quantum state?

Thoughts

I would like to understand what types of variables could go into the generic structure in order to help keep the data calculations hidden from the server. If you select certain known generic variables, I do not understand why the selection of other known generic variables would prevent the data calculations from being hidden.

Answer 1

It looks like you're asking about this part of the paper:

Therefore, a quantum computation is hidden as long as these measurements are successfully hidden. In order to achieve this, the BQC protocol exploits special resources called blind cluster states that must be chosen carefully to be a generic structure that reveals nothing about the underlying computation (see Figure 1).

-"Experimental Demonstration of Blind Quantum Computing" (2011)

That last part, about how they want a "generic structure that reveals nothing about the underlying computation" might make a reader wonder about how a computer's structure could leak information about its computations.

As a simple example of structure leaking information about a cypto scheme, suppose that Bob asks Sally question to which we assume that Sally'll respond yes or no. Sally directly encrypts her response using their shared one-time pad (OTP), resulting in the ciphertext rk4. Despite the OTP scheme having perfect secrecy in general, it's clear that Sally responded yes.

In this case, the computer was structured to leak information about the length of a message given that message, which was especially disastrous in this contrived example. In general, structure can leak information about the computation. Avoiding such leaks would be necessary for a blind-computation server like the one the paper intends to discuss.

Generally speaking, attacks that operate like this are called side-channel attacks.

In the case of this paper (disclaiming that I just skimmed it quickly), it looks like they're basically talking about creating a generic computational structure that doesn't leak information through its structural traits. For example, if the structure behaved differently in any way based on a secret aspect of the message, then it may leak secret information to the server when the server observes its own computational behavior.

The paper appears to be trying to point out that the computational unit needs to be designed to avoid such information leaks.

Later in the paper, they discuss stuff about blinding:

In cryptography, blinding is a technique by which an agent can provide a service to (i.e., compute a function for) a client in an encoded form without knowing either the real input or the real output. Blinding techniques also have applications to preventing side-channel attacks on encryption devices.

-"Blinding (cryptography)", Wikipedia

And, really, blinding's what this paper's all about: figuring out a way to have a server do work for clients without the clients revealing their secrets to the server.

One way to enable blind computation is for the client to use homomorphic encryption on its job request before sending it to the server:

Homomorphic encryption is a form of encryption that allows computation on ciphertexts, generating an encrypted result which, when decrypted, matches the result of the operations as if they had been performed on the plaintext. The purpose of homomorphic encryption is to allow computation on encrypted data.

-"Homomorphic encryption", Wikipedia

Answer 2

As one of the authors of the paper, and of the original theory papers on which that experimental realisation is based, perhaps I can attempt to answer. The BQC protocol used in that paper is based on a model of computations where measurements are made on a specially chosen entangled state (this is known as measurement-based quantum computation or MBQC, and was introduced in 2003 by Raussendorf and Briegel (PRA, arXiv). In MBQC the resource state is called a graph state, because a circuit to construct the graph state can be associated with a graph: for every vertex prepare a qubit in $|+\rangle$, and then perform a CZ gate between every pair of qubits for which the corresponding vertices share an edge in the graph. It turns out that you can implement an arbitrary quantum computation by first preparing a suitable graph state, and then by measuring out each qubit in turn, with measurement bases determined based on the target computation and on previous measurement outcomes.

What the BQC protocol does is to effectively implement an MBQC in a way that hides measurement bases from Bob. The reason we mention a need for a generic structure is because the protocol does not hide the graph. Now, it turns out that you can actually choose a generic graph which can implement any quantum computation which can be expressed as a quantum circuit of a given depth and breadth if the measurement bases are chosen appropriately. Using such a graph ensures that only circuit depth and breadth are leaked, and not the details of the computation. Furthermore, the computation can always be randomly padded to ensure that only an upper bound on depth and breadth are leaked. This is the minimum possible leakage, since ultimately Bob knows how much memory his device has (~circuit breadth) and how long it ran (~circuit depth), and so it is impossible to avoid leaking such upper bounds.

For more information you may wish to take a look at the following review paper, and references contained therein: Private quantum computation: an introduction to blind quantum computing and related protocols, J.F. Fitzsimons, npj Quantum Information 2017.