Cryptology ePrint Archive: Report 2020/1469
Succinct Blind Quantum Computation Using a Random Oracle
Jiayu Zhang
Abstract: In the universal blind quantum computation problem, a client wants to make
use of a single quantum server to evaluate $C|0\rangle$ 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 [FOCS09, arXiv:0807.4154], 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, BFK [FOCS09,
arXiv:0807.4154]), 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 $\kappa$, its complexity is only
a fixed polynomial of $\kappa$, and can be used to evaluate any circuit (or
several circuits) of size up to a subexponential of $\kappa$. In contrast,
known schemes either require the client to perform quantum computations that
scale with the size of the circuit [FOCS09, arXiv:0807.4154], or require
trapdoor assumptions [Mahadev, FOCS18, arXiv:1708.02130].
Category / Keywords: cryptographic protocols / Quantum Cryptography; Blind Quantum Computation; Random Oracle; Symmetric-key Cryptography
Date: received 22 Nov 2020, last revised 25 Nov 2020
Contact author: jyz16 at bu edu
Available format(s): PDF | BibTeX Citation
Note: Contain some further revisions compared to arXiv: 2004.12621v10. Changes include some typo fixes, font change and notation simplification compared to the arXiv v10 version; add one writing convention subsection to section 2 to explain the organization better and provide some pointer for very common notations; change n+1 to 1+n and 1+\log\kappa to \log\kappa+1 to be more consistent with the protocol and security; fix more typos. See cs-people.bu.edu/jyz16 for the most recent version (with some typo fixes that do not have in print/arXiv version).
Version: 20201125:150307 (All versions of this report)
Short URL: ia.cr/2020/1469
[ Cryptology ePrint archive ]