Paper 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 $C0\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 informationtheoretically (IT) secure or based on trapdoor assumptions (public key encryptions). In this paper we study how the availability of symmetrickey 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 ITsecure 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].
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 cspeople.bu.edu/jyz16 for the most recent version (with some typo fixes that do not have in print/arXiv version).
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint. MINOR revision.
 Keywords
 Quantum CryptographyBlind Quantum ComputationRandom OracleSymmetrickey Cryptography
 Contact author(s)
 jyz16 @ bu edu
 History
 20201125: revised
 20201124: received
 See all versions
 Short URL
 https://ia.cr/2020/1469
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/1469, author = {Jiayu Zhang}, title = {Succinct Blind Quantum Computation Using a Random Oracle}, howpublished = {Cryptology ePrint Archive, Paper 2020/1469}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/1469}}, url = {https://eprint.iacr.org/2020/1469} }