Delegation of quantum computation using a random oracle
Jiayu Zhang
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.
•Jan 1, 2022•0 citations