Limitations on information theoretically secure quantum homomorphic encryption

Abstract

Homomorphic encryption is a form of encryption which allows computation to be carried out on the encrypted data without the need for decryption. The success of quantum approaches to related tasks in a delegated computation setting has raised the question of whether quantum mechanics may be used to achieve information theoretically secure fully homomorphic encryption. Here we show, via an information localisation argument, that deterministic fully homomorphic encryption necessarily incurs exponential overhead if perfect security is required.

4 pages, 1 figure

References in corpus (15)

• Quantum-enhanced measurements: beating the standard quantum limit
• Random Numbers Certified by Bell's Theorem
• Unconditionally secure quantum bit commitment is impossible
• Insecurity of Quantum Secure Computations
• Experimental Demonstration of Blind Quantum Computing
• Programmable quantum gate arrays
• Quantum private queries
• Blind quantum computation protocol in which Alice only makes measurements
• Quantum computing on encrypted data
• Experimental verification of quantum computations
• Efficient Discrete Approximations of Quantum Gates
• Quantum walks with encrypted data
• Optimal Blind Quantum Computation
• Symmetric quantum fully homomorphic encryption with perfect security
• Channel kets, entangled states, and the location of quantum information

Cited by in corpus (29)

• Unconditionally verifiable blind computation
• Quantum Cryptography Beyond Quantum Key Distribution
• Quantum homomorphic encryption for circuits of low $T$-gate complexity
• Quantum homomorphic encryption from quantum codes
• Quantum fully homomorphic encryption scheme based on universal quantum circuit
• Practical quantum computing on encrypted data
• A quantum approach to homomorphic encryption
• QFactory: classically-instructed remote secret qubits preparation
• Quantum Fully Homomorphic Encryption With Verification
• Resource Quantification for the No-Programming Theorem
• Practical quantum somewhat-homomorphic encryption with coherent states
• Computing on quantum shared secrets
• On the possibility of classical client blind quantum computing
• Homomorphic encryption of linear optics quantum computation on almost arbitrary states of light with asymptotically perfect security
• Quantum fully homomorphic encryption scheme based on quantum fault-tolerant construction
• Quantum Fully Homomorphic Encryption by Integrating Pauli One-time Pad with Quaternions
• Quantum homomorphic encryption for polynomial-sized circuits
• Privacy and correctness trade-offs for information-theoretically secure quantum homomorphic encryption
• Delegating Quantum Computation in the Quantum Random Oracle Model
• Further Limitations on Information-Theoretically Secure Quantum Homomorphic Encryption
• A quantum homomorphic encryption scheme for polynomial-sized circuits
• Limitations on Transversal Computation through Quantum Homomorphic Encryption
• Implementing Semiclassical Szegedy Walks in Classical-Quantum Circuits for Homomorphic Encryption
• Quantum Search on Encrypted Data Based on Quantum Homomorphic Encryption
• Quantum preprocessing for information-theoretic security in two-party computation
• Quantum Private Function Evaluation
• A framework for quantum homomorphic encryption with experimental demonstration
• Teleportation-based quantum homomorphic encryption scheme with quasi-compactness and perfect security
• Optical Quantum Computing