Publicly verifiable delegation is a well-known problem involving a user who wishes to outsource a resource-intensive computational task to a more powerful but potentially untrusted server such that any other party is able to efficiently check the veracity of the com- putation's result. This problem has been extensively studied in the classical domain where the user and server are both non-quantum machines. However, the problem becomes more challenging when the classical user wants to delegate a quantum circuit to a single prover with quantum-computing capabilities. Previous solutions have resorted to using impractical or non-standard cryptographic solutions (e.g. indistinguishability obfuscation) to achieve this re- quirement. In this work, we relax the requirement to have time- delayed publicly verifiable proofs, where the verification key is made known to the public only when the computation (and its proof) are guaranteed to have been completed. We propose a prac- tical non-interactive scheme leveraging commitment schemes and time-lock puzzles, which can be efficiently realized through well- established and standard post-quantum assumptions. The main idea of our technique lies in using time-lock puzzles to compile a 2-round privately verifiable scheme into a non-interactive publicly verifiable scheme with timestamped proofs, outsourcing not only the quantum computation but the puzzle solving as well. Security is proven in the quantum random oracle model with a common reference string (CRS).
Publicly verifiable delegation is a well-known problem involving a user who wishes to outsource a resource-intensive computational task to a more powerful but potentially untrusted server such that any other party is able to efficiently check the veracity of the com- putation's result. This problem has been extensively studied in the classical domain where the user and server are both non-quantum machines. However, the problem becomes more challenging when the classical user wants to delegate a quantum circuit to a single prover with quantum-computing capabilities. Previous solutions have resorted to using impractical or non-standard cryptographic solutions (e.g. indistinguishability obfuscation) to achieve this re- quirement. In this work, we relax the requirement to have time- delayed publicly verifiable proofs, where the verification key is made known to the public only when the computation (and its proof) are guaranteed to have been completed. We propose a prac- tical non-interactive scheme leveraging commitment schemes and time-lock puzzles, which can be efficiently realized through well- established and standard post-quantum assumptions. The main idea of our technique lies in using time-lock puzzles to compile a 2-round privately verifiable scheme into a non-interactive publicly verifiable scheme with timestamped proofs, outsourcing not only the quantum computation but the puzzle solving as well. Security is proven in the quantum random oracle model with a common reference string (CRS).
Publicly verifiable delegation is a well-known problem involving a user who wishes to outsource a resource-intensive computational task to a more powerful but potentially untrusted server such that any other party is able to efficiently check the veracity of the computation's result. This problem has been extensively studied in the classical domain where the user and server are both non-quantum machines. However, the problem becomes more challenging when the classical user wants to delegate a quantum circuit to a single prover with quantum-computing capabilities. Previous solutions have resorted to using impractical or non-standard cryptographic solutions (e.g. indistinguishability obfuscation) to achieve this requirement. In this work, we relax the requirement to have time-delayed publicly verifiable proofs, where the verification key is made known to the public only when the computation (and its proof) are guaranteed to have been completed. We propose a practical non-interactive scheme leveraging commitment schemes and time-lock puzzles, which can be efficiently realized through well-established and standard post-quantum assumptions. The main idea of our technique lies in using time-lock puzzles to compile a 2-round privately verifiable scheme into a non-interactive publicly verifiable scheme with timestamped proofs, outsourcing not only the quantum computation but the puzzle solving as well. Security is proven in the quantum random oracle model with a common reference string (CRS).
Delegated quantum computation enables a client with limited quantum capabilities to outsource computations to a more powerful quantum server while preserving correctness and privacy. Verification is crucial in this setting to ensure that the untrusted quantum server performs the computation honestly and returns correct results. A common verification method is the quantum cut-and-choose technique. Inspired by classical verification methods for two-party computation, the client uses the majority of the delegated rounds to test the server's honesty, while keeping the remaining ones for the actual computation. Combining this technique with other methods, such as quantum error correction, could help achieve negligible cheating probabilities for the server; however, such methods can impose significant overheads making implementations unfeasible for the near-term future. In this work, we investigate whether cut-and-choose can yield efficient and secure verifiable quantum computation without additional costly techniques. We find that verifiable delegated quantum computation protocols relying solely on cut-and-choose techniques cannot be secure and efficient at the same time.
The importance of being able to verify quantum computation delegated to remote servers increases with recent development of quantum technologies. In some of the proposed protocols for this task, a client delegates her quantum computation to non-communicating servers. The fact that the servers do not communicate is not physically justified and it is essential for the proof of security of such protocols. For the best of our knowledge, we present in this work the first verifiable delegation scheme where a classical client delegates her quantum computation to two entangled servers that are allowed to communicate, but respecting the plausible assumption that information cannot be propagated faster than speed of light. We achieve this result by proposing the first one-round two-prover game for the Local Hamiltonian problem where provers only need polynomial time quantum computation and access to copies of the groundstate of the Hamiltonian.
Quantum computers can make use of quantum mechanics to achieve surprising speed-ups relative to classical computers, for important computational problems. Quantum computers are gradually coming into reality, but the current implementations are big, require advanced facilities and could only be used as a cloud service in the foreseeable future. If we want to run quantum computations on secret data, we require protocols for performing computations on a remote quantum server without leaking information to the server about the data being processed. In the quantum computation delegation problem, a client with limited quantum computing resources wishes to evaluate a secret quantum circuit C with the help of a more powerful remote server. The protocol is deemed secure if the server learns nothing about either the circuit or the input state even if the server acts maliciously. This problem, first raised in (Childs05), has become fundamental to the study of quantum cryptography, because of its practical importance, and because it provides a testbed for new techniques that can be later applied to related problems (for example, quantum computation verification [FK12]). Prior to our work, known protocols for this problem were either proven secure against all possible attackers, without any complexity-theoretic assumptions, but highly inefficient for the client; or efficient but proven secure only based on strong cryptographic assumptions. This second category of protocols is only secure if there exist public-key encryption schemes that are secure against quantum attacks and that have special additional properties. Very few candidates for such schemes are known, and their security remains poorly understood. We seek to understand how efficient quantum delegation schemes can be designed based on weaker or different complexity assumptions. We study how the availability of symmetric-key primitives, modeled by a random oracle, changes the complexity of quantum computation delegation. In contrast with public-key primitives, there are many candidates for symmetric-key schemes secure against quantum attacks. We aim for protocols that require as little quantum computing as possible for the client. Specifically, we ask that the client only needs to run a quantum circuit of size independent of the circuit being evaluated. Known unconditionally-secure protocols all require the client to evaluate quantum circuits of size at least linear in the original circuit size. In this thesis, we construct two new quantum computation delegation protocols. The first protocol is for the delegation of a large special circuit family, which we call "C+P circuits". This scheme is non-interactive, and can be used to delegate a very important quantum algorithm---Shor's algorithm (Shor,97) for integer factorization and discrete logarithms. Our second protocol requires interaction---one quantum message from the client to the server, and many rounds of classical computation---but supports arbitrary quantum computation (instead of a specific circuit family), and is thus much more general than the first protocol in both theory and practice. Both protocols are proved secure in the quantum random oracle model. The protocols can be instantiated in practice with a symmetric-key cipher such as AES.
Quantum computers promise to offer a considerable speed-up in solving certain problems, compared to the best classical algorithms. In many instances, the gap between quantum and classical running times is conjectured to be exponential. While this is great news for those applications where quantum computers would provide such an advantage, it also raises a significant challenge: how can classical computers verify the correctness of quantum computations? In attempting to answer this question, a number of protocols have been developed in which a classical client (referred to as verifier) can interact with one or more quantum servers (referred to as provers) in order to certify the correctness of a quantum computation performed by the server(s). These protocols are of one of two types: either there are multiple non-communicating provers, sharing entanglement, and the verifier is completely classical; or, there is a single prover and the classical verifier has a device for preparing or measuring quantum states. The latter type of protocols are, arguably, more relevant to near term quantum computers, since having multiple quantum computers that share a large amount of entanglement is, from a technological standpoint, extremely challenging. Before the realisation of practical single-prover protocols, a number of challenges need to be addressed: how robust are these protocols to noise on the verifier's device? Can the protocols be made fault-tolerant without significantly increasing the requirements of the verifier? How do we know that the verifier's device is operating correctly? Could this device be eliminated completely, thus having a protocol with a fully classical verifier and a single quantum prover? Our work attempts to provide answers to these questions. First, we consider a single-prover verification protocol developed by Fitzsimons and Kashefi and show that this protocol is indeed robust with respect to deviations on the quantum state prepared by the verifier. We show that this is true even if those deviations are the result of a correlation with the prover's system. We then use this result to give a verification protocol which is device- independent. The protocol consists of a verifier with a measurement device and a single prover. Device-independence means that the verifier need not trust the measurement device (nor the prover) which can be assumed to be fully malicious (though not communicating with the prover). A key element in realising this protocol is a robust technique of Reichardt, Unger and Vazirani for testing, using non-local correlations, that two untrusted devices share a large number of entangled states. This technique is referred to as rigidity of non-local correlations. Our second result is to prove a rigidity result for a type of quantum correlations known as steering correlations. To do this, we first show that steering correlations can be used in order to certify maximally entangled states, in a setting in which each test is independent of the previous one. We also show that the fidelity with which we characterise the state, in this specific test, is optimal. We then improve the previous result by removing the independence assumption. This then leads to our desired rigidity result. We make use of it, in a similar fashion to the device-independent case, in order to give a verification protocol that is one-sided device-independent. The importance of this application is to show how different trust assumptions affect the efficiency of the protocol. Next, we describe a protocol for fault-tolerantly verifying quantum computations, with minimal "quantum requirements" for the verifier. Specifically, the verifier only requires a device for measuring single-qubit states. Both this device, and the prover's operations are assumed to be prone to errors. We show that under standard assumptions about the error model, it is possible to achieve verification of quantum computation using fault-tolerant principles. As a proof of principle, and to better illustrate the inner workings of the protocol, we describe a toy implementation of the protocol in a quantum simulator, and present the results we obtained, when running it for a small computation. Finally, we explore the possibility of having a verification protocol, with a classical verifier and a single prover, such that the prover is blind with respect to the verifier's computation. We give evidence that this is not possible. In fact, our result is only concerned with blind quantum computation with a classical client, and uses complexity theoretic results to argue why it is improbable for such a protocol to exist. We then use these complexity theoretic techniques to show that a client, with the ability to prepare and send quantum states to a quantum server, would not be able to delegate arbitrary NP problems to that server. In other words, even a client with quantum capabilities cannot exploit those capabilities to delegate the computation of NP problems, while keeping the input, to that computation, private. This is again true, provided certain complexity theoretic conjectures are true.
A time-lock puzzle allows a sender to hide a message in a puzzle such that recovering the message requires substantially more sequential computation than the time required to generate the puzzle, even when parallel computation is allowed. Applications of time-lock puzzles include timed-release encryption, sealed-bid auctions, electronic voting, fair contract signing, coin flipping, and Byzantine consensus. However, time-lock puzzles are known to be impossible in the classical random oracle model.
To overcome the classical barrier, in this work we consider quantum time-lock puzzles, in which the puzzle itself is a quantum state. Our construction in the quantum random oracle model achieves generation in one oracle round, solving in at most T oracle rounds, and security against polynomial-width quantum adversaries of depth o(T) for every polynomially bounded delay T=T(λ), resolving an open problem posed by Mahmoody, Moran, and Vadhan (2011).