In the universal blind quantum computation problem, a client wants to make use of a single quantum server to evaluate C|0⟩ where C is an arbitrary quantum circuit while keeping C secret. The client’s goal is to use as few resources as possible. This problem, first raised by Broadbent, Fitzsimons and Kashefi [FOCS 2009], has become fundamental to the study of quantum cryptography, not only because of its own importance, but also because it provides a testbed for new techniques that can be later applied to related problems (for example, quantum computation verification). Known protocols on this problem are mainly either information-theoretically (IT) secure or based on trapdoor assumptions (public key encryptions). In this paper we study how the availability of symmetric-key primitives, modeled by a random oracle, changes the complexity of universal blind quantum computation. We give a new universal blind quantum computation protocol. Similar to previous works on IT-secure protocols (for example, Broadbent-Fitzsimons-Kashefi), our protocol can be divided into two phases. In the first phase the client prepares some quantum gadgets with relatively simple quantum gates and sends them to the server, and in the second phase the client is entirely classical — it does not even need quantum storage. Crucially, the protocol’s first phase is succinct, that is, its complexity is independent of the circuit size. Given the security parameter κ, its complexity is only a fixed polynomial of κ, and can be used to evaluate any circuit (or several circuits) of size up to a subexponential of κ. In contrast, known schemes either require the client to perform quantum computations that scale with the size of the circuit, or require trapdoor assumptions.
In the universal blind quantum computation problem, a client wants to make use of a single quantum server to evaluate C|0⟩ where C is an arbitrary quantum circuit while keeping C secret. The client’s goal is to use as few resources as possible. This problem, first raised by Broadbent, Fitzsimons and Kashefi [FOCS 2009], has become fundamental to the study of quantum cryptography, not only because of its own importance, but also because it provides a testbed for new techniques that can be later applied to related problems (for example, quantum computation verification). Known protocols on this problem are mainly either information-theoretically (IT) secure or based on trapdoor assumptions (public key encryptions). In this paper we study how the availability of symmetric-key primitives, modeled by a random oracle, changes the complexity of universal blind quantum computation. We give a new universal blind quantum computation protocol. Similar to previous works on IT-secure protocols (for example, Broadbent-Fitzsimons-Kashefi), our protocol can be divided into two phases. In the first phase the client prepares some quantum gadgets with relatively simple quantum gates and sends them to the server, and in the second phase the client is entirely classical — it does not even need quantum storage. Crucially, the protocol’s first phase is succinct, that is, its complexity is independent of the circuit size. Given the security parameter κ, its complexity is only a fixed polynomial of κ, and can be used to evaluate any circuit (or several circuits) of size up to a subexponential of κ. In contrast, known schemes either require the client to perform quantum computations that scale with the size of the circuit, or require trapdoor assumptions.
Quantum computers can make use of quantum mechanics to achieve surprising speed-ups relative to classical computers, for important computational problems. Quantum computers are gradually coming into reality, but the current implementations are big, require advanced facilities and could only be used as a cloud service in the foreseeable future. If we want to run quantum computations on secret data, we require protocols for performing computations on a remote quantum server without leaking information to the server about the data being processed. In the quantum computation delegation problem, a client with limited quantum computing resources wishes to evaluate a secret quantum circuit C with the help of a more powerful remote server. The protocol is deemed secure if the server learns nothing about either the circuit or the input state even if the server acts maliciously. This problem, first raised in (Childs05), has become fundamental to the study of quantum cryptography, because of its practical importance, and because it provides a testbed for new techniques that can be later applied to related problems (for example, quantum computation verification [FK12]). Prior to our work, known protocols for this problem were either proven secure against all possible attackers, without any complexity-theoretic assumptions, but highly inefficient for the client; or efficient but proven secure only based on strong cryptographic assumptions. This second category of protocols is only secure if there exist public-key encryption schemes that are secure against quantum attacks and that have special additional properties. Very few candidates for such schemes are known, and their security remains poorly understood. We seek to understand how efficient quantum delegation schemes can be designed based on weaker or different complexity assumptions. We study how the availability of symmetric-key primitives, modeled by a random oracle, changes the complexity of quantum computation delegation. In contrast with public-key primitives, there are many candidates for symmetric-key schemes secure against quantum attacks. We aim for protocols that require as little quantum computing as possible for the client. Specifically, we ask that the client only needs to run a quantum circuit of size independent of the circuit being evaluated. Known unconditionally-secure protocols all require the client to evaluate quantum circuits of size at least linear in the original circuit size. In this thesis, we construct two new quantum computation delegation protocols. The first protocol is for the delegation of a large special circuit family, which we call "C+P circuits". This scheme is non-interactive, and can be used to delegate a very important quantum algorithm---Shor's algorithm (Shor,97) for integer factorization and discrete logarithms. Our second protocol requires interaction---one quantum message from the client to the server, and many rounds of classical computation---but supports arbitrary quantum computation (instead of a specific circuit family), and is thus much more general than the first protocol in both theory and practice. Both protocols are proved secure in the quantum random oracle model. The protocols can be instantiated in practice with a symmetric-key cipher such as AES.
Universal blind quantum computation allows a client who has limited quantum abilities to delegate his or her private computation to an untrusted quantum server. The first universal blind quantum computation protocol was proposed by Broadbent, Fitzsimons, and Kashefi. In their work the computation resource is the so-called brickwork state, which can be constructed by a number of specific single qubits. The number of single qubits is in theory linearly related to the size of the quantum circuit. However, due to the fixed structure of the brickwork states, the actual number of qubits is usually far more than the linear size. In this work we mainly construct three improved brickwork states whose structures are no longer fixed, thus they can efficiently reduce the client's qubit consumption. Using those improved brickwork states we propose a class of efficient universal blind quantum computation protocols. In our basic protocol, to implement a single-qubit basic gate the client needs to prepare only two ancillary qubits, while in the original protocol it will consume four ancillary qubits. Making use of our improved brickwork states the qubit consumption of implementing a nonadjacent two-qubit gate such as a control-X gate can be sharply reduced.
Blind quantum computing (BQC) allows a client to have a server carry out a quantum computation for them such that the client's input, output, and computation remain private. A desirable property for any BQC protocol is verification, whereby the client can verify with high probability whether the server has followed the instructions of the protocol or if there has been some deviation resulting in a corrupted output state. A verifiable BQC protocol can be viewed as an interactive proof system leading to consequences for complexity theory. We previously proposed [A. Broadbent, J. Fitzsimons, and E. Kashefi, in Proceedings of the 50th Annual Symposium on Foundations of Computer Science, Atlanta, 2009 (IEEE, Piscataway, 2009), p. 517] a universal and unconditionally secure BQC scheme where the client only needs to be able to prepare single qubits in separable states randomly chosen from a finite set and send them to the server, who has the balance of the required quantum computational resources. In this paper we extend that protocol with additional functionality allowing blind computational basis measurements, which we use to construct another verifiable BQC protocol based on a different class of resource states. We rigorously prove that the probability of failing to detect an incorrect output is exponentially small in a security parameter, while resource overhead remains polynomial in this parameter. This resource state allows entangling gates to be performed between arbitrary pairs of logical qubits with only constant overhead. This is a significant improvement on the original scheme, which required that all computations to be performed must first be put into a nearest-neighbor form, incurring linear overhead in the number of qubits. Such an improvement has important consequences for efficiency and fault-tolerance thresholds.
The question of whether a fully classical client can delegate a quantum computation to an untrusted quantum server while fully maintaining privacy (blindness) is one of the big open questions in quantum cryptography. Both yes and no answers have important practical and theoretical consequences, and the question seems genuinely hard. The state-of-the-art approaches to securely delegating quantum computation, without exception, rely on granting the client modest quantum powers, or on additional, non-communicating, quantum servers. In this work, we consider the single server setting, and push the boundaries of the minimal devices of the client, which still allow for blind quantum computation. Our approach is based on the observation that, in many blind quantum computing protocols, the "quantum" part of the protocol, from the clients perspective, boils down to the establishing classical-quantum correlations (independent from the computation) between the client and the server, following which the steering of the computation itself requires only classical communication. Here, we abstract this initial preparation phase, specifically for the Universal Blind Quantum Computation protocol of Broadbent, Fitzsimons and Kashefi. We identify sufficient criteria on the powers of the client, which still allow for secure blind quantum computation. We work in a universally composable framework, and provide a series of protocols, where each step reduces the number of differing states the client needs to be able to prepare. As the limit of such reductions, we show that the capacity to prepare just two pure states, which have an arbitrarily high overlap (thus are arbitrarily close to identical), suffices for efficient and secure blind quantum computation.
The universal blind quantum computation protocol (UBQC) enables an almost classical client to delegate a quantum computation to an untrusted quantum server (in the form of a garbled quantum circuit) while the security for the client is unconditional. In this contribution, we explore the possibility of extending the verifiable UBQC, to achieve further functionalities following the analogous research for classical circuits (Yao 1986). First, exploring the asymmetric nature of UBQC (the client preparing only single qubits, while the server runs the entire quantum computation), we present a “Yao”-type protocol for secure two-party quantum computation. Similar to the classical setting, our quantum Yao protocol is secure against a specious (quantum honest-but-curious) garbler, but in our case, against a (fully) malicious evaluator. Unlike the previous work on quantum two-party computation of Dupuis et al., 2010, we do not require any online-quantum communication between the garbler and the evaluator and, thus, no extra cryptographic primitive. This feature will allow us to construct a simple universal one-time compiler for any quantum computation using one-time memory, in a similar way to the classical work of Goldwasser et al., 2008, while more efficiently than the previous work of Broadbent et al., 2013.
Blind delegation protocols allow a client to delegate a computation to a server so that the server learns nothing about the input to the computation apart from its size. For the specific case of quantum computation we know that blind delegation protocols can achieve information-theoretic security. In this paper we prove, provided certain complexity-theoretic conjectures are true, that the power of information-theoretically secure blind delegation protocols for quantum computation (ITS-BQC protocols) is in a number of ways constrained. In the first part of our paper we provide some indication that ITS-BQC protocols for delegating BQP computations in which the client and the server interact only classically are unlikely to exist. We first show that having such a protocol with O(nd) bits of classical communication implies that BQP⊂MA/O(nd). We conjecture that this containment is unlikely by providing an oracle relative to which BQP⊂MA/O(nd). We then show that if an ITS-BQC protocol exists with polynomial classical communication and which allows the client to delegate quantum sampling problems, then there exist non-uniform circuits of size 2n−Ω(n/log(n)), making polynomially-sized queries to an NPNP oracle, for computing the permanent of an n×n matrix. The second part of our paper concerns ITS-BQC protocols in which the client and the server engage in one round of quantum communication and then exchange polynomially many classical messages. First, we provide a complexity-theoretic upper bound on the types of functions that could be delegated in such a protocol, namely QCMA/qpoly∩coQCMA/qpoly. Then, we show that having such a protocol for delegating NP-hard functions implies coNPNPNP⊆NPNPPromiseQMA.