pdf icon
Volume 14 (2018) Article 7 pp. 1-45
Quantum Homomorphic Encryption for Polynomial-Size Circuits
Received: December 24, 2016
Revised: July 5, 2017
Published: May 17, 2018
Download article from ToC site:
[PDF (486K)] [PS (2895K)] [Source ZIP]
Keywords: quantum computing, quantum cryptography, homomorphic encryption, quantum teleportation, garden-hose model
ACM Classification: E.3, F.1.2
AMS Classification: 68P25, 69Q12, 81P68, 81P94, 94A60

Abstract: [Plain Text Version]

We present a new scheme for quantum homomorphic encryption which is compact and allows for efficient evaluation of arbitrary quantum circuits, as long as those circuits are of size, polynomial in the security parameter. Building on the framework of Broadbent and Jeffery (CRYPTO'15) and recent results in the area of instantaneous non-local quantum computation by Speelman (TQC'16), we show how to construct quantum gadgets that allow perfect correction of the errors which occur during the homomorphic evaluation of $\mathsf{T}$ gates on encrypted quantum data. Our scheme can be based on any classical (leveled) fully homomorphic encryption (FHE) scheme and requires no computational assumptions besides those already used by the classical scheme. The size of our quantum gadget depends on the space complexity of the classical decryption function -- which aligns well with the current efforts to minimize the complexity of the decryption function. Our scheme (or slight variants of it) offers a number of additional advantages such as ideal compactness, the ability to supply gadgets “on demand,” circuit privacy for the evaluator against passive adversaries, and a three-round scheme for blind delegated quantum computation which puts only very limited demands on the quantum abilities of the client.

A conference version of this paper appeared in Advances in Cryptology: Proceedings of the 36th International Cryptology Conference (CRYPTO 2016).