Luka Music

Known protocols for the secure delegation of quantum computations from a client to a server in an information-theoretic setting require quantum communication. In this work, we investigate methods to reduce the communication overhead. First, we establish an impossibility result by proving that local processes on the server side cannot increase the number of qubits required for the computation. We develop a series of no-go results that prohibit such a process within an information-theoretic framework. Second, we present a possibility result by introducing the notion of selectively blind quantum computing (SBQC), a protocol that minimizes the number of encrypted qubits in the computation when delegating one computation from a pre-known set of computations. This approach, which we term can reduce communication costs drastically depending on the type of the possible computations and the differences between them.

Secure Delegated Quantum Computation (SDQC) protocols allow a client to delegate a quantum computation to a powerful remote server while ensuring the privacy and the integrity of its computation. Recent resource-efficient and noise- robust protocols led to experimental proofs of concept. Yet, their physical re- quirements are still too stringent to be added directly to the roadmap of quantum hardware vendors. To address part of this issue, this paper shows how to alleviate the necessity for the client to have a single-photon source. It proposes a protocol that ensures that, among a sufficiently large block of transmitted weak coherent pulses, at least one of them was emitted as a single photon. This can then be used through quantum privacy amplification techniques to prepare a single secure qubit to be used in an SDQC protocol. As such, the obtained guarantee can also be used for Quantum Key Distribution (QKD) where the privacy amplification step is classical. In doing so, it proposes a workaround for a weakness in the security proof of the decoy state method. The simplest instantiation of the protocol with only 2 intensities already shows improved scaling at low transmittance and adds verifiability to previous SDQC proposals.

With the advent of delegated quantum computing as a service, verifying quantum computations is becoming a question of great importance. Existing information theoretically Secure Delegated Quantum Computing (SDQC) protocols require the client to possess the ability to perform either trusted state preparations or measurements. Whether it is possible to verify universal quantum computations with information-theoretic security without trusted preparations or measurements was an open question so far. In this paper, we settle this question in the affirmative by presenting a modular, composable, and efficient way to turn known verification schemes into protocols that rely only on trusted gates.

With the recent availability of cloud quantum computing services, the question of verifying quantum computations delegated by a client to a quantum server is becoming of practical interest. While Verifiable Blind Quantum Computing (VBQC) has emerged as one of the key approaches to address this challenge, current protocols still need to be optimised before they are truly practical. To this end, we establish a fundamental correspondence between error-detection and verification and provide sufficient conditions to both achieve security in the Abstract Cryptography framework and optimise resource overheads of all known VBQC-based protocols. As a direct application, we demonstrate how to systematise the search for new efficient and robust verification protocols for BQP computations. While we have chosen Measurement-Based Quantum Computing (MBQC) as the working model for the presentation of our results, one could expand the domain of applicability of our framework via direct known translation between the circuit model and MBQC.

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.

With the development of delegated quantum computation, clients will want to ensure confidentiality of their data and algorithms, and the integrity of their computations. While protocols for blind and verifiable quantum computation exist, they suffer from high overheads and from over-sensitivity: When running on noisy devices, imperfections trigger the same detection mechanisms as malicious attacks, resulting in perpetually aborted computations. We introduce the first blind and verifiable protocol for delegating BQP computations to a powerful server with repetition as the only overhead. It is composably statistically secure with exponentially-low bounds and can tolerate a constant amount of global noise.

With the emergence of quantum communication, it is of folkloric belief that allowing an Adversary to perform superposition queries to otherwise classical cryptographic protocols and forcing the honest players to perform actions coherently on quantum states automatically breaks the schemes' security. Another intuition is that enforcing measurements on the exchanged messages is enough to protect protocols from these attacks. However, the reality is much more complex. The security models dealing with superposition attacks only consider unconditional security. The first seminal papers date back to 1997 and prove the impossibility of unconditionally-secure bit-commitment schemes. Follow-up works heavily rely on this assumption of unconditional security to prove strong impossibility results and their proof techniques cannot be applied to the computational setting. They essentially indicate that ideal primitives should in fact measure the input state. On the opposite, security models considering computational security assume that all supposedly classical messages are measured, which forbids by construction the analysis of superposition attacks. To fill in the gap between those models, Boneh and Zhandry have started to study the quantum computational security for classical primitives in their seminal work at Crypto'13, but only in the single-party setting. To the best of our knowledge, an equivalent model in the multiparty setting is still missing. In this work, we propose the first computational security model considering superposition attacks for multiparty protocols. We show that our new security model is satisfiable by proving the security of the well-known One-Time-Pad protocol and show an attack on a variant of the equally reputable Yao Protocol for Secure Two-Party Computations. The post-mortem of this attack reveals the precise points of failure, yielding highly counter-intuitive results: The attack vector consists of a (classically) seemingly inoffensive message and a measurement performed by the honest player. This example shows that adding extra classical communication, which is harmless for classical security, can make the protocol become subject to superposition attacks. Our results show that intuitions can be misleading when reasoning about cryptographic protocols in a quantum world, and that there is no evident answer to provide for either the vulnerabilities of classical protocols to superposition attacks or the adapted countermeasures.