Léo Colisson

Léo Colisson, Frédéric Grosshans, Elham Kashefi

We propose the first generalization of the famous Non-Interactive Zero-Knowledge (NIZK) proofs to quantum languages (NIZKoQS) and we provide a protocol to prove advanced properties on a received quantum state non-destructively and non-interactively (a single message being sent from the prover to the verifier). In our second orthogonal contribution, we improve the costly Remote State Preparation protocols [CCKW18,CCKW19,GV19] that can classically fake a quantum channel (this is at the heart of our NIZKoQS protocol) by showing how to create a multi-qubits state from a single superposition. Finally, we generalize these results to a multi-party setting and prove that multiple parties can anonymously distribute a GHZ state in such a way that only participants knowing a secret credential can share this state, which could have applications to quantum anonymous transmission, quantum secret sharing, quantum onion routing and more.

Christian Badertscher, Alexandru Cojocaru, Léo Colisson et al.

Secure delegated quantum computing allows a computationally weak client to outsource an arbitrary quantum computation to an untrusted quantum server in a privacy-preserving manner. One of the promising candidates to achieve classical delegation of quantum computation is classical-client remote state preparation ($RSP_{CC}$), where a client remotely prepares a quantum state using a classical channel. However, the privacy loss incurred by employing $RSP_{CC}$ as a sub-module is unclear. In this work, we investigate this question using the Constructive Cryptography framework by Maurer and Renner (ICS'11). We first identify the goal of $RSP_{CC}$ as the construction of ideal RSP resources from classical channels and then reveal the security limitations of using $RSP_{CC}$. First, we uncover a fundamental relationship between constructing ideal RSP resources (from classical channels) and the task of cloning quantum states. Any classically constructed ideal RSP resource must leak to the server the full classical description (possibly in an encoded form) of the generated quantum state, even if we target computational security only. As a consequence, we find that the realization of common RSP resources, without weakening their guarantees drastically, is impossible due to the no-cloning theorem. Second, the above result does not rule out that a specific $RSP_{CC}$ protocol can replace the quantum channel at least in some contexts, such as the Universal Blind Quantum Computing (UBQC) protocol of Broadbent et al. (FOCS '09). However, we show that the resulting UBQC protocol cannot maintain its proven composable security as soon as $RSP_{CC}$ is used as a subroutine. Third, we show that replacing the quantum channel of the above UBQC protocol by the $RSP_{CC}$ protocol QFactory of Cojocaru et al. (Asiacrypt '19), preserves the weaker, game-based, security of UBQC.

Alexandru Cojocaru, Léo Colisson, Elham Kashefi et al.

The functionality of classically-instructed remotely prepared random secret qubits was introduced in (Cojocaru et al 2018) as a way to enable classical parties to participate in secure quantum computation and communications protocols. The idea is that a classical party (client) instructs a quantum party (server) to generate a qubit to the server's side that is random, unknown to the server but known to the client. Such task is only possible under computational assumptions. In this contribution we define a simpler (basic) primitive consisting of only BB84 states, and give a protocol that realizes this primitive and that is secure against the strongest possible adversary (an arbitrarily deviating malicious server). The specific functions used, were constructed based on known trapdoor one-way functions, resulting to the security of our basic primitive being reduced to the hardness of the Learning With Errors problem. We then give a number of extensions, building on this basic module: extension to larger set of states (that includes non-Clifford states); proper consideration of the abort case; and verifiablity on the module level. The latter is based on "blind self-testing", a notion we introduced, proved in a limited setting and conjectured its validity for the most general case.

Alexandru Cojocaru, Léo Colisson, Elham Kashefi et al.

We define the functionality of delegated pseudo-secret random qubit generator (PSRQG), where a classical client can instruct the preparation of a sequence of random qubits at some distant party. Their classical description is (computationally) unknown to any other party (including the distant party preparing them) but known to the client. We emphasize the unique feature that no quantum communication is required to implement PSRQG. This enables classical clients to perform a class of quantum communication protocols with only a public classical channel with a quantum server. A key such example is the delegated universal blind quantum computing. Using our functionality one could achieve a purely classical-client computational secure verifiable delegated universal quantum computing (also referred to as verifiable blind quantum computation). We give a concrete protocol (QFactory) implementing PSRQG, using the Learning-With-Errors problem to construct a trapdoor one-way function with certain desired properties (quantum-safe, two-regular, collision-resistant). We then prove the security in the Quantum-Honest-But-Curious setting and briefly discuss the extension to the malicious case.