In this paper, we construct a new scheme for delegating a large circuit
family, which we call circuits. C+P circuits are the circuits composed
of Toffoli gates and diagonal gates. Our scheme is non-interactive, only
requires small quantum resources on the client side, and can be proved secure
in the quantum random oracle model, without relying on additional assumptions,
for example, the existence of fully homomorphic encryption. In practice the
random oracle can be replaced by appropriate hash functions or symmetric key
encryption schemes, for example, SHA-3, AES. This protocol allows a client to delegate the most expensive part of some
quantum algorithms, for example, Shor's algorithm. The previous protocols that
are powerful enough to delegate Shor's algorithm require either many rounds of
interactions or the existence of FHE. The quantum resources required by the
client are fewer than when it runs Shor's algorithm locally. Different from many previous protocols, our scheme is not based on quantum
one time pad, but on a new encoding called entanglement We then
generalize the garbled circuit to reversible garbled circuit to allow the
computation on this encoding. To prove the security of this protocol, we study key dependent message(KDM)
security in the quantum random oracle model. Then as a natural generalization,
we define and study quantum KDM security. KDM security was not previously
studied in quantum settings.
In this paper, we construct a new scheme for delegating a large circuit
family, which we call circuits. C+P circuits are the circuits composed
of Toffoli gates and diagonal gates. Our scheme is non-interactive, only
requires small quantum resources on the client side, and can be proved secure
in the quantum random oracle model, without relying on additional assumptions,
for example, the existence of fully homomorphic encryption. In practice the
random oracle can be replaced by appropriate hash functions or symmetric key
encryption schemes, for example, SHA-3, AES. This protocol allows a client to delegate the most expensive part of some
quantum algorithms, for example, Shor's algorithm. The previous protocols that
are powerful enough to delegate Shor's algorithm require either many rounds of
interactions or the existence of FHE. The quantum resources required by the
client are fewer than when it runs Shor's algorithm locally. Different from many previous protocols, our scheme is not based on quantum
one time pad, but on a new encoding called entanglement We then
generalize the garbled circuit to reversible garbled circuit to allow the
computation on this encoding. To prove the security of this protocol, we study key dependent message(KDM)
security in the quantum random oracle model. Then as a natural generalization,
we define and study quantum KDM security. KDM security was not previously
studied in quantum settings.
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.
Homomorphic encryption is a cryptographic primitive that enables information processing on encrypted data. Such primitives are useful in a delegated computing setting in which a client delegates processing to a server, but does not trust the server fully with her information. Here, I discuss a way of performing quantum homomorphic encryption. A homomorphic encryption protocol comprises of four algorithms: random key generation, encryption, evaluation, and decryption. Our technique requires that a pair of commuting operators be used to implement the encryption and evaluation. The client randomly selects the former, while the server implements the latter. Then post-evaluation, if the client decrypts using the inverse of the encryption, he retrieves the input state with the desired computation implemented. The code space has to be chosen carefully so that non-trivial evaluations can be performed on the logical qubits. Since the encryption key is not known to the server, the randomness introduced by key generation hides some information about the encoded data despite it being put into the hands of the server. This framework is powerful because it gives a general description for implementing quantum homomorphic encryption. For example, families of commuting groups of operators are known to exist via the Schur-Weyl duality. However, it is limited by a no-go theorem that states that an exponential overhead is needed if arbitrary computation and perfect security are desired. Nonetheless, our protocols are still interesting as an application for near-term quantum computers, especially when the computational tasks require only low-depth circuits.
In the universal blind quantum computation problem, a client wants to make use of a single quantum server to evaluate C|0⟩ where C is an arbitrary quantum circuit while keeping C secret. The client’s goal is to use as few resources as possible. This problem, first raised by Broadbent, Fitzsimons and Kashefi [FOCS 2009], has become fundamental to the study of quantum cryptography, not only because of its own importance, but also because it provides a testbed for new techniques that can be later applied to related problems (for example, quantum computation verification). Known protocols on this problem are mainly either information-theoretically (IT) secure or based on trapdoor assumptions (public key encryptions). In this paper we study how the availability of symmetric-key primitives, modeled by a random oracle, changes the complexity of universal blind quantum computation. We give a new universal blind quantum computation protocol. Similar to previous works on IT-secure protocols (for example, Broadbent-Fitzsimons-Kashefi), our protocol can be divided into two phases. In the first phase the client prepares some quantum gadgets with relatively simple quantum gates and sends them to the server, and in the second phase the client is entirely classical — it does not even need quantum storage. Crucially, the protocol’s first phase is succinct, that is, its complexity is independent of the circuit size. Given the security parameter κ, its complexity is only a fixed polynomial of κ, and can be used to evaluate any circuit (or several circuits) of size up to a subexponential of κ. In contrast, known schemes either require the client to perform quantum computations that scale with the size of the circuit, or require trapdoor assumptions.
Abstract Quantum computing on encrypted data allows a client who has limited quantum capacity to delegate his or her private computation to an untrusted quantum server, while the input and output are encrypted by the quantum one-time pad and only the client can correctly decrypt them. Generally, the client is required to have ability to prepare some single qubits and perform some basic gates. In this work, we consider a further restricted situation where the client can only prepare one single qubit and perform one basic gate. Specifically, we show that as long as the client can prepare a fixed qubit and perform a fixed phase gate P , then he or she can still achieve the secure delegated quantum computation. Besides, our protocol can provide a more rigorous security for any quantum computation. For example, even if some encryption keys about the computation are leaked, it can still guarantee the privacy of the input and output. Finally, our protocol experimentally has a great significance in reducing the device complexity of the client's side.
We give a protocol for the delegation of quantum computation on encrypted data. More specifically, we show that in a client–server scenario, where the client holds the encryption key for an encrypted quantum register held by the server, it is possible for the server to perform a universal set of quantum gates on the quantum data. All Clifford group gates are non-interactive, while the remaining non-Clifford group gate that we implement (the π/8 gate) requires the client to prepare and send a single random auxiliary qubit (chosen among four possibilities), and exchange classical communication. This construction improves on previous work, which requires either multiple auxiliary qubits or two-way quantum communication. Using a reduction to an entanglement-based protocol, we show privacy against any adversarial server according to a simulation-based security definition.
The universal blind quantum computation protocol (UBQC) enables an almost classical client to delegate a quantum computation to an untrusted quantum server (in the form of a garbled quantum circuit) while the security for the client is unconditional. In this contribution, we explore the possibility of extending the verifiable UBQC, to achieve further functionalities following the analogous research for classical circuits (Yao 1986). First, exploring the asymmetric nature of UBQC (the client preparing only single qubits, while the server runs the entire quantum computation), we present a “Yao”-type protocol for secure two-party quantum computation. Similar to the classical setting, our quantum Yao protocol is secure against a specious (quantum honest-but-curious) garbler, but in our case, against a (fully) malicious evaluator. Unlike the previous work on quantum two-party computation of Dupuis et al., 2010, we do not require any online-quantum communication between the garbler and the evaluator and, thus, no extra cryptographic primitive. This feature will allow us to construct a simple universal one-time compiler for any quantum computation using one-time memory, in a similar way to the classical work of Goldwasser et al., 2008, while more efficiently than the previous work of Broadbent et al., 2013.