Elham Kashefi

Quantum state purification is the functionality that, given multiple copies of an unknown state, outputs a state with increased purity. This is an essential building block for the near- and middle-term quantum ecosystems before the availability of full fault tolerance, where one may want to obtain purified quantum states instead of expectation values. We propose an effective state purification gadget with a moderate quantum overhead by projecting multiple noisy quantum inputs to their symmetry subspace defined by a set of projectors forming a subgroup of the symmetry group. This provides a state purification performance scaling inverse-linearly to the number of state copies given a fixed stochastic error rate, which drastically improves the implementation overhead in previous works. Our method may find its application in designing robust verification protocols for quantum outputs before the availability of fully fault-tolerant computing.

In this work we develop new methods for the characterisation of continuous variable quantum states using heterodyne measurement in both the trusted and untrusted settings. First, building on quantum state tomography with heterodyne detection, we introduce a reliable method for continuous variable quantum state certication, which directly yields the elements of the density matrix of the state considered and analytical condence intervals. This method neither needs mathematical reconstruction of the data, nor discrete binning of the sample space, and uses a single Gaussian measurement setting. Second, beyond quantum state tomography and without its identical copies assumption, we promote our reliable tomography method to a general efficient protocol for verifying continuous variable pure quantum states with Gaussian measurements against fully malicious adversaries, i.e. making no assumptions whatsoever on the state generated by the adversary. These results are obtained using a new analytical estimator for the expected value of any operator acting on a continuous variable quantum state with bounded support over the Fock basis, computed with samples from heterodyne detection of the state.

Physical Unclonable Functions (PUFs) are physical devices that have unique behaviour which is hard to clone. These hardware structures are considered as an effective and feasible security primitive. The application of a wide variety of PUF structures for different security purposes such as identification and key generation has been widely studied in the context of Classical PUFs. In addition, the quantum-readout PUF (QR-PUF) has been studied as a proposition for a quantum version of classical PUFs. In this paper, we do a comprehensive study on Quantum Physical Unclonable Functions with quantum cryptographic tools. We use a quantum game-based security framework for our analysis and we define a new class of quantum attacks, called General Quantum Emulation Attack (GQEA), applicable on current quantum-readout and hybrid quantum-classical PUFs. This class of attacks are based on using a database of inputs and outputs to emulate the action of an unknown quantum transformation on a new input. We define a concrete attack based on an existing emulation algorithm and use it to show the vulnerability of the current schemes under this attack. Furthermore, we formally define a QPUF for the first time and discuss the security of Unitary QPUFs (UQPUFs) by formally defining the unforgeability property of UQPUFs. We prove any UQPUF provides selective unforgeability property while they cannot provide unconditional and existential unforgeabilities.

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.

Authentication is a fundamental building block of secure quantum networks, essential for quantum cryptographic protocols and often debated as a key limitation of quantum key distribution (QKD) in security standards. Most quantum-safe authentication schemes rely on small pre-shared keys or post-quantum computational assumptions. In this work, we introduce a new authentication approach that combines hardware assumptions, particularly Physical Unclonable Functions (PUFs), along with fundamental quantum properties of non-local states, such as local indistinguishability, to achieve a provable security in an entanglement-based protocol. We propose two protocols for different scenarios in entanglement-enabled quantum networks. The first protocol, referred to as the offline protocol, requires pre-distributed entangled states but no quantum communication during the process of authentication. It enables a server to authenticate clients at any time with only minimal classical communication. The second, an online protocol, requires quantum communication but only necessitates entangled state generation on the Prover’s side. For this, we introduce a novel hardware module, the Hybrid Entangled PUF (HEPUF). Both protocols use weakly secure, off-the-shelf classical PUFs as their hardware module, yet we prove that quantum properties such as local indistinguishability enable exponential security for authentication, even in a single round. We provide a full security analysis for both protocols and establish them as the first entanglement-based extension of hardware-based quantum authentication. These protocols are suitable for implementation across various platforms, particularly photonics-based ones, and offer a practical and flexible solution to the long-standing challenge of authentication in quantum communication networks.

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.

We show the security of multi-user key establishment on a single line of quantum communication. More precisely, we consider a quantum communication architecture where the qubit generation and measurement happen at the two ends of the line, whilst intermediate parties are limited to single-qubit unitary transforms. This network topology has been previously introduced to implement quantum-assisted secret-sharing protocols for classical data, as well as the key establishment, and secure computing. This architecture has numerous advantages. The intermediate nodes are only using simplified hardware, which makes them easier to implement. Moreover, key establishment between arbitrary pairs of parties in the network does not require key routing through intermediate nodes. This is in contrast with quantum key distribution networks for which non- adjacent nodes need intermediate ones to route keys, thereby revealing these keys to intermediate parties and consuming previously established ones to secure the routing process. Our main result is to show the security of key establishment on quantum line networks. We show the security using the framework of abstract cryptography. This immediately makes the security composable, showing that the keys can be used for encryption or other tasks.

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.

We introduce a secure hardware device named a QEnclave that can secure the remote execution of quantum operations while only using classical controls. This device extends to quantum computing the classical concept of a secure enclave which isolates a computation from its environment to provide privacy and tamper-resistance. Remarkably, our QEnclave only performs single-qubit rotations, but can nevertheless be used to secure an arbitrary quantum computation even if the qubit source is controlled by an adversary. More precisely, attaching a QEnclave to a quantum computer, a remote client controlling the QEnclave can securely delegate its computation to the server solely using classical communication. We investigate the security of our QEnclave by modeling it as an ideal functionality named Remote State Rotation. We show that this resource allows blind delegated quantum computing with perfect security. Our proof relies on standard tools from delegated quantum computing. Working in the Abstract Cryptography framework, we show a construction of remote state preparation from remote state rotation preserving the security. An immediate consequence is the weakening of the requirements for blind delegated computation. While previous delegated protocols were relying on a client that can either generate or measure quantum states, we show that this same functionality can be achieved with a client that only transforms quantum states without generating or measuring them. Combined with known impossibility results for implementing remote state preparation with classical communication, our construction suggests a new way for blind secure delegated computation. Computational assumptions that circumvent this impossibility induce large overheads that prevent their practical use. But our approach does not increase the complexity of the problem, and relies on hardware assumptions that are already used in practice for classical computations. It hence provides a better way of implementing blind remote delegation on real quantum computing systems.

In this paper, we continue the line of work initiated by Boneh and Zhandry at CRYPTO 2013 and EUROCRYPT 2013 in which they formally define the notion of unforgeability against quantum adversaries. We develop a general and parameterised quantum game-based security model unifying unforgeability for both classical and quantum constructions allowing us for the first time to present a complete quantum cryptanalysis framework for unforgeability. In particular, we prove how our definitions subsume previous ones while considering more fine-grained adversarial models, capturing the full spectrum of superposition attacks. The subtlety here resides in the characterisation of a forgery. We show that the strongest level of unforgeability in our framework, namely existential unforgeability, can only be achieved if only orthogonal to previously queried messages are considered to be forgeries. We further show that deterministic constructions can only achieve the weaker notion of unforgeability, that is selective unforgeability, against such adversaries, but that selective unforgeability breaks if more general quantum adversaries (capable of general superposition attacks) are considered. On the other hand, we show that PRF is sufficient for constructing a selective unforgeable classical primitive against full quantum adversaries. Moreover, we show similar positive results relying on Pseudorandom Unitaries (PRU) for quantum primitives. \\ These results demonstrate the generality of our framework that could be applicable to other primitives beyond the cases analysed in this paper.

Cryptanalysis of quantum cryptographic systems generally involves finding optimal adversarial attack strategies on the underlying protocols. The core principle of modeling quantum attacks often reduces to the ability of the adversary to clone unknown quantum states and to extract thereby meaningful secret information. Explicit optimal attack strategies typically require high computational resources due to large circuit depths or, in many cases, are unknown. Here we introduce variational quantum cloning (VarQlone), a cryptanalysis algorithm based on quantum machine learning, which allows an adversary to obtain optimal approximate cloning strategies with short depth quantum circuits, trained using hybrid classical-quantum techniques. The algorithm contains operationally meaningful cost functions with theoretical guarantees, quantum circuit structure learning and gradient-descent-based optimization. Our approach enables the end-to-end discovery of hardware-efficient quantum circuits to clone specific families of quantum states, which we demonstrate in implementation on the Rigetti Aspen quantum hardware. We connect these results to quantum cryptographic primitives and derive explicit attacks facilitated by VarQlone. We expect that quantum machine learning will serve as a resource for improving attacks on current and future quantum cryptographic protocols.

Secure two-party computation considers the problem of two parties computing a joint function of their private inputs without revealing anything beyond the output of the computation. In this work, we take the first steps towards understanding the setting where: 1) the two parties (Alice and Bob) can communicate only via a classical channel, 2) the input of Bob is quantum and 3) the input of Alice is classical. Our first result indicates that in this setting it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. In particular, we show that the existence of a secure protocol that relies only on classical channels would contradict the quantum no-cloning argument. We circumvent this following three different approaches. The first is by considering a weaker security notion called one-sided simulation security. This notion protects the input of one party (the quantum Bob) in the standard simulation-based sense, and protects the privacy of the other party's input (the classical Alice). We realize our protocol relying on the learning with errors assumption. As a result, we put forward a first construction of secure one-sided quantum two-party computation over classical networks. The second way to circumvent the impossibility result, while at the same time providing standard simulation-based security also against Bob, is by assuming that the quantum input has an efficient classical representation. Finally, we focus our attention on the class of zero-knowledge functionalities, and provide a protocol for such a class for specific QMA relations. We note that the direct implication of our result is that Mahadev's protocol for classical verification of quantum computations (FOCS'18) can be turned into a zero-knowledge proof of quantum knowledge protocol with classical verifiers. To the best of our knowledge, we are the first to instantiate such a primitive.

Quantum physical unclonable functions, or QPUFs, are rapidly emerging as theoretical hardware solutions to provide secure cryptographic functionalities such as key exchange, message authentication, entity identification among others. Recent works have shown that in order to provide provable security of these solutions against any quantum polynomial time adversary, QPUFs are required to be a unitary sampled uniformly randomly from the Haar measure. This however is known to require an exponential amount of resources. In this work, we propose an efficient construction of these devices using unitary t-designs, called QPUF_t. Along the way, we modify the existing security definitions of QPUFs to include efficient constructions and showcase that QPUF_t still retains the provable security guarantees against a bounded quantum polynomial adversary with t-query access to the device. This also provides the first use case of unitary t-design construction for arbitrary t, as opposed to previous applications of t-designs where usually a few (relatively low) values of t are known to be useful for performing some task. We study the noise-resilience of QPUF_t against specific types of noise, unitary noise, and show that some resilience can be achieved particularly when the error rates affecting individual qubits become smaller as the system size increases. To make the noise resilience more realistic and meaningful, we conclude that some notion of error mitigation or correction should be introduced.

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.

We derive a general framework for a quantum metrology scheme where the quantum probes are exchanged via an unsecured quantum channel. We construct two protocols for this task which offer a trade-off between difficulty of implementation and efficiency. We show that, for both protocols, a malicious eavesdropper cannot access any information regarding the unknown parameter. We further derive general inequalities regarding how the uncertainty in a resource state for quantum metrology can bias the estimate and the precision. From this, we link the effectiveness of the cryptographic part of the protocol to the effectiveness of the metrology scheme with a (potentially) malicious probe resource state.

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.

Classical remote state preparation (RSPCC) is a primitive that allows an honest client to prepare a quantum state remotely with the help of an (untrustworthy) server using only a classical communication channel. With this primitive quantum protocols (such as secure delegation of quantum computations) become accessible to classical clients, by removing the need for a quantum channel. Since this cryptographic primitive’s main role is to be a building block within larger protocols, it is of utmost importance to examine its security under composition. In this work we present three results related to the composability of RSPCC protocols: 1. As our first main result, we show that no classical remote state preparation protocol RSPCC can be composable in the Abstract Cryptography framework [MR11], even when the distinguisher is computationally bounded. In other words, remote state preparation cannot be constructed with only a classical channel. 2. We further show that any classical-client delegated quantum computing protocol that uses the universal blind quantum computation (UBQC) protocol [BFK09] and a RSPCC protocol as a subroutine cannot be composable. 3. Upon relaxing the security requirement, we show that replacing the quantum channel of the UBQC protocol by the particular RSPCC protocol of [CCKW19] is secure in the game-based security framework.

Recently, major progress has been made towards the realisation of the quantum internet to enable a broad range of applications that would be out of reach for classical internet. Most of these applications such as delegated quantum computation require running a secure identification protocol between a low-resource and a high-resource party to provide secure communication. Physical Unclonable Functions (PUFs) have been shown as resource-efficient hardware solutions for providing secure identification schemes in both classical and quantum settings. In this work, we propose two identification protocols based on quantum PUFs (qPUFs) as defined recently by Arapinis et al. In the first protocol, the low-resource party wishes to prove its identity to the high-resource party and in the second protocol, it is vice versa. Unlike existing identification protocols based on Quantum Read-out of PUFs which rely on the security against a specific family of attacks, our protocols provide provable exponential security against any Quantum Polynomial-Time adversary with only polynomial resource parties. We provide a comprehensive comparison between the two proposed protocols in terms of resources such as quantum memory and computing ability required in both parties as well as the communication overhead between them. A stand-out feature of our second protocol is secure identification of a high-resource party by running a purely classical verification algorithm. This is achieved by delegating quantum operations to the high-resource party and utilising the resulting classical outcomes for identification. An interesting application idea that emerges from our second protocol is certification or benchmarking of general quantum computation schemes based on purely running a classical test on the resulting measurement outcomes.