We present a quantumly-enhanced protocol to achieve unconditionally secure delegated classical computation where the client and the server have both limited classical and quantum computing capacity. We prove the same task cannot be achieved using only classical protocols. This extends the work of Anders and Browne on the computational power of correlations to a security setting. Concretely, we present how a client with access to a non-universal classical gate such as a parity gate could achieve unconditionally secure delegated universal classical computation by exploiting minimal quantum gadgets. In particular, unlike the universal blind quantum computing protocols, the restriction of the task to classical computing removes the need for a full universal quantum machine on the side of the server and makes these new protocols readily implementable with the currently available quantum technology in the lab.
We present a quantumly-enhanced protocol to achieve unconditionally secure delegated classical computation where the client and the server have both limited classical and quantum computing capacity. We prove the same task cannot be achieved using only classical protocols. This extends the work of Anders and Browne on the computational power of correlations to a security setting. Concretely, we present how a client with access to a non-universal classical gate such as a parity gate could achieve unconditionally secure delegated universal classical computation by exploiting minimal quantum gadgets. In particular, unlike the universal blind quantum computing protocols, the restriction of the task to classical computing removes the need for a full universal quantum machine on the side of the server and makes these new protocols readily implementable with the currently available quantum technology in the lab.
We present a family of quantumly-enhanced protocols to achieve unconditionally secure delegated classical computation where the client and the server have both their classical and quantum computing capacity limited. We prove the same task cannot be achieved using only classical protocols. This extends the work of Anders and Browne on the computational power of correlations to a security setting. In doing so we are able to highlight the power of online quantum communication as we prove the same task could not be achieved using pre-shared (offline) quantum correlations.
A longstanding question is whether it is possible to delegate computational tasks securely---such that neither the computation nor the data is revealed to the server. Recently, both a classical and a quantum solution to this problem were found [C. Gentry, in Proceedings of the 41st Annual ACM Symposium on the Theory of Computing (Association for Computing Machinery, New York, 2009), pp. 167--178; A. Broadbent, J. Fitzsimons, and E. Kashefi, in Proceedings of the 50th Annual Symposium on Foundations of Computer Science (IEEE Computer Society, Los Alamitos, CA, 2009), pp. 517--526]. Here, we study the first step towards the interplay between classical and quantum approaches and show how coherence can be used as a tool for secure delegated classical computation. We show that a client with limited computational capacity---restricted to an XOR gate---can perform universal classical computation by manipulating information carriers that may occupy superpositions of two states. Using single photonic qubits or coherent light, we experimentally implement secure delegated classical computations between an independent client and a server, which are installed in two different laboratories and separated by 50m. The server has access to the light sources and measurement devices, whereas the client may use only a restricted set of passive optical devices to manipulate the information-carrying light beams. Thus, our work highlights how minimal quantum and classical resources can be combined and exploited for classical computing.
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.
Abstract Blind quantum computation (BQC) allows a client without enough quantum technologies to delegate her quantum computation to a remote quantum server, while keeping her input, output and algorithm secure. In this paper, we propose a universal single-server and almost-classical-client BQC protocol. In this protocol, the client interfaces with only one server and the only ability of the client required is to get particles from the trusted center and forward them to the server. We present an analysis of this protocol and modify it to a universal single-server and fully-classical-client BQC protocol by improving the ability of the trusted center. Based on our protocols and recent works, a new ‘Cloud + Certificate Authority (CA)’ style is proposed for the BQC.
In this paper, we propose a multiparty delegated quantum computing protocol for the completely classical clients. Our protocol is mainly based on the work of Cojocaru et al, in which they proposed a concrete protocol that can make a classical client instruct a quantum server to prepare a random qubit. We simplify their protocol by replacing the one-way functions with the one-way permutations that are post-quantum secure only. Then we extend this improved scheme to multiparty delegated quantum computation, where a group of classical clients can delegate their joint computation task to a distrusted quantum server.
The rapid evolution of quantum technologies is likely to cause major shifts in the mainstream computing landscape. In order to fully reach their potential in a wide base accessible to any user, remote access of quantum computers and manipulation of data with strong privacy and integrity guarantees are essential. Consider a setting where a client having a fully classical computer wants to determine the result of some quantum computation, but lacks the necessary resources to perform the computation herself. She has access to a more powerful server which has quantum resources and can solve the problem and send the outcome back to the client. However, the client does not trust the powerful server, so she needs to find a way to hide her data. Therefore, the main question that arises is how can we guarantee the client’s privacy of the input and even the computation itself against the server possessing quantum computational capabilities. In the present thesis, we study this problem, denoted here as classical secure delegation of quantum computations (CSDQC) between a fully classical honest client and a quantum untrusted server. We focus on different models of security, analyzing the limitations and potential of each of the settings. Concretely, we first study the CSDQC problem under information-theoretic security. We analyse two categories of quantum computations, decision and sampling problems and in both cases we provide evidence indicating the impossibility of achieving information-theoretic security. Subsequently, we consider relaxing the security framework and specifically, we will analyze this task in the computational security setting (against quantum polynomial-time adversaries). As a result, in the second part of the thesis we put forward the remote state preparation as a key component that would allow us to achieve classical secure delegation of universal quantum computations. We present two protocols realizing the remote state preparation primitive assuming only a classical channel between client and server. The first candidate is shown to be secure in the honest-but-curious model, while the second candidate is proven secure against the server in the malicious setting. The security of both constructions relies on the hardness of the learning with errors problem. Finally, given the important role the remote state preparation plays not only in CSDQC, but also in other quantum communication protocols, we analyze its composable security to determine the privacy loss as a result of using remote state preparation as a sub-module in different protocols.