论文标题
使用随机Oracle简洁的盲量量子计算
Succinct Blind Quantum Computation Using a Random Oracle
论文作者
论文摘要
在通用盲量量子计算问题中，客户希望使用单个量子服务器来评估$ c | 0 \ rangle $，其中$ c $是任意的量子电路，同时保留$ c $ necret。客户的目标是使用尽可能少的资源。这个问题通过Broadbent，Fitzsimons和Kashefi [focs09，arxiv：0807.4154]的代表性协议已经成为量子密码学研究的基础，这不仅是因为其自身的重要性，还因为它具有以后可以应用于相关问题的新技术（例如，量子计算）。有关此问题的已知协议主要是理论上的信息（IT）安全或基于陷阱门假设（公共密钥加密）。 在本文中，我们研究了以随机甲骨文建模的对称键原始词的可用性如何改变通用盲量计算的复杂性。我们提供了新的通用盲量量子计算协议。类似于以前关于IT安全协议的作品（例如，BFK [focs09，arxiv：0807.4154]），我们的协议可以分为两个阶段。在第一阶段，客户端用相对简单的量子门准备一些量子小工具，并将其发送到服务器，在第二阶段，客户端完全是经典的 - 它甚至不需要量子存储。至关重要的是，协议的第一阶段是简洁的，也就是说，其复杂性与电路大小无关。鉴于安全参数$κ$，其复杂性仅为$κ$的固定多项式，可用于评估最高指数为$κ$的任何电路（或多个电路）。相比之下，已知的方案要求客户执行量子计算，以按照电路的大小进行扩展[focs09，arxiv：0807.4154]，或者需要陷阱门假设[Mahadev，focs18，arxiv：1708.02130]。
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, with a representative protocol 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 $κ$, 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 [FOCS09, arXiv:0807.4154], or require trapdoor assumptions [Mahadev, FOCS18, arXiv:1708.02130].
