Multi-Party Quantum Computation (MPQC) has attracted a lot of attention as a potential killer-app for quantum networks through it's ability to preserve privacy and integrity of the highly valuable computations they would enable. Contributing to the latest challenges in this field, we present a composable protocol achieving blindness and verifiability even in the case of a single honest client. The security of our protocol is reduced, in an information-theoretically secure way, to that of a classical composable Secure Multi-Party Computation (SMPC) used to coordinate the various parties. Our scheme thus provides a statistically secure upgrade of such classical scheme to a quantum one with the same level of security. In addition, (i) the clients can delegate their computation to a powerful fully fault-tolerant server and only need to perform single qubit operations to unlock the full potential of multi-party quantum computation; (ii) the amount of quantum communication with the server is reduced to sending quantum states at the beginning of the computation and receiving the output states at the end, which is optimal and removes the need for interactive quantum communication; and (iii) it has a low constant multiplicative qubit overhead compared to the single-client delegated protocol it is built upon. The main technical ingredient of our paper is the bootstraping of the MPQC construction by Double Blind Quantum Computation, a new composable resource for blind multiparty quantum computation, that demonstrates the surprising fact that the full protocol does not require verifiability of all components to achieve security.
Multi-Party Quantum Computation (MPQC) has attracted a lot of attention as a potential killer-app for quantum networks through it's ability to preserve privacy and integrity of the highly valuable computations they would enable. Contributing to the latest challenges in this field, we present a composable protocol achieving blindness and verifiability even in the case of a single honest client. The security of our protocol is reduced, in an information-theoretically secure way, to that of a classical composable Secure Multi-Party Computation (SMPC) used to coordinate the various parties. Our scheme thus provides a statistically secure upgrade of such classical scheme to a quantum one with the same level of security. In addition, (i) the clients can delegate their computation to a powerful fully fault-tolerant server and only need to perform single qubit operations to unlock the full potential of multi-party quantum computation; (ii) the amount of quantum communication with the server is reduced to sending quantum states at the beginning of the computation and receiving the output states at the end, which is optimal and removes the need for interactive quantum communication; and (iii) it has a low constant multiplicative qubit overhead compared to the single-client delegated protocol it is built upon. The main technical ingredient of our paper is the bootstraping of the MPQC construction by Double Blind Quantum Computation, a new composable resource for blind multiparty quantum computation, that demonstrates the surprising fact that the full protocol does not require verifiability of all components to achieve security.
Abstract Secure multi-party computation (SMPC) protocols allow several parties distrusting each other to collectively compute a function on their inputs, without revealing the input values. In this paper, we introduce a protocol that lifts SMPC to its quantum counterpart—secure multi-party quantum computation (SMPQC) for classical inputs and outputs—in a composable and statistically secure way, even for a single honest party. The soundness error—the maximum cheating probability of malicious parties—is shown to be proportional to the inverse of a polynomial with respect to the number of rounds in the protocol, and can be further decreased to a negligible quantity for bounded-error quantum-polynomial-time computations. Unlike previous SMPQC protocols, our proposal only requires very limited quantum resources from all but one party. In addition, the protocol exhibits some noise robustness that can facilitate small-scale implementations with near-future technologies. The protocol is based on a new technique for quantum verification that requires only the collective remote preparation of quantum states in a single plane of the Bloch sphere. To demonstrate the ability of verifying the computation with such limited clients, we uncover and use a fundamental invariance that is inherent to measurement-based quantum computing.
Secure multi-party computation (SMPC) protocols allow several parties that distrust each other to collectively compute a function on their inputs. In this paper, we introduce a protocol that lifts classical SMPC to quantum SMPC in a composably and statistically secure way, even for a single honest party. Unlike previous quantum SMPC protocols, our proposal only requires very limited quantum resources from all but one party; it suffices that the weak parties, i.e. the clients, are able to prepare single-qubit states in the X-Y plane. The novel quantum SMPC protocol is constructed in a naturally modular way, and relies on a new technique for quantum verification that is of independent interest. This verification technique requires the remote preparation of states only in a single plane of the Bloch sphere. In the course of proving the security of the new verification protocol, we also uncover a fundamental invariance that is inherent to measurement-based quantum computing.
Abstract Delegated quantum computation (DQC) has emerged as a significant research focus to expedite the practical application of quantum advantage. Since substantial progress has been made in single-client DQC, extending these developments to multi-client settings naturally leads to the concept of multi-party delegated quantum computation (MPDQC). Existing MPDQC protocols predominantly rely on the prepare-and-send mode, while neglecting the receive-and-measure mode which is experimentally more practical. A key challenge hindering the adoption of the receive-and-measure mode in the multi-client scenario is the difficulty in verifying the local measurements of clients. In this paper, we address this obstacle and propose a verifiable MPDQC scheme tailored for multi-client settings. To enable federated computation among multiple clients, we construct a multi-client hypergraph state as the foundational resource state for MPDQC. Concurrently, we introduce a Pauli measurement verification protocol enabling the verification of client behavior within the multi-client framework, leveraging assistance from the quantum server. Building upon these advancements, we present a verifiable multiparty delegated universal quantum computation (MPDUQC) protocol and demonstrate its blindness and verifiability against malicious participants. Our work effectively bridges the gap for MPDQC protocols operating in the receive-and-measure paradigm.
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.
We construct a multi-Client verifiable blind delegated quantum computing (VBDQC) protocol in which M classical Verifier Clients jointly delegate a public quantum circuit acting on their combined private inputs to two quantum-capable Provers sharing entanglement but having no direct communication channel. We begin by modifying the single-Client, entanglement-based CGJV Verifier-on-a-Leash protocol. We then prove simulator-based blind verifiability for the modified protocol using the abstract/constructive cryptography framework. We adapt the DFPR upward-reduction chain to the two-Prover setting, constructing a no-direct-communication simulator architecture. We then extend the CGJV protocol to M Clients using classical multiparty computation techniques, preserving the single-Client guarantees of completeness, soundness, and blindness while additionally guaranteeing input privacy between Clients. Security is analyzed under a threat model that allows a subset of Clients to collude with one but not both of the Provers, which do not communicate even after the protocol execution.
Blind quantum computing protocols enable a client, who can generate or measure single-qubit states, to delegate quantum computing to a remote quantum server protecting the client's privacy (i.e., input, output, and program). With current technologies, generations or measurements of single-qubit states are not too much burden for the client. In other words, secure delegated quantum computing is possible for ``almost classical" clients. However, is it possible for a ``completely classical" client? Here we consider a one-round perfectly-secure delegated quantum computing, and show that the protocol cannot satisfy both the correctness (i.e., the correct result is obtained when the server is honest) and the perfect blindness (i.e., the client's privacy is completely protected) simultaneously unless BQP is in NP. Since BQP is not believed to be in NP, the result suggests the impossibility of the one-round perfectly-secure delegated quantum computing.