Institute of Information Science, Academia Sinica

This talk contains two parts. First, we construct a new scheme for delegating a large circuit family, which we call "C+P 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. Our construction is based on the quantum generalization of the garbled circuit construction.
Second, we discuss some ideas to construct a universal blind quantum computation protocol in the quantum random oracle model, without using trapdoor assumptions. Our construction requires succinct client side quantum resources, which means, the total number of client side quantum gates is at most a fixed polynomial of the security parameter, independent to the circuit size. The construction is through a “remote gadget preparation” protocol, which allows the server to prepare many gadgets from only succinct size of “initial seed”, and has a special kinds of security. Then we reduce the UBQC protocol to it to solve the problem.
The first part is based on arXiv:1810.05234 and the second part is based on some unpublished works.