Delegating Quantum Computation Using Only Hash Functions

In this paper, 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. Different from many previous protocols, our scheme is not based on quantum one time pad, but on a new encoding called "entanglement encoding". We then generalize the garbled circuit to reversible garbled circuit to allow the computation on this encoding.  To prove the security of this protocol, we study key dependent message(KDM) security in the quantum random oracle model. Then as a natural generalization, we define and study quantum KDM security. KDM security was not previously studied in quantum settings.