Quantum homomorphic encryption for circuits of low $T$-gate complexity

Abstract

Fully homomorphic encryption is an encryption method with the property that any computation on the plaintext can be performed by a party having access to the ciphertext only. Here, we formally define and give schemes for quantum homomorphic encryption, which is the encryption of quantum information such that quantum computations can be performed given the ciphertext only. Our schemes allows for arbitrary Clifford group gates, but become inefficient for circuits with large complexity, measured in terms of the non-Clifford portion of the circuit (we use the "$\pi /8$" non-Clifford group gate, which is also known as the $T$-gate). More specifically, two schemes are proposed: the first scheme has a decryption procedure whose complexity scales with the square of the number of $T$-gates (compared with a trivial scheme in which the complexity scales with the total number of gates); the second scheme uses a quantum evaluation key of length given by a polynomial of degree exponential in the circuit's $T$-gate depth, yielding a homomorphic scheme for quantum circuits with constant $T$-depth. Both schemes build on a classical fully homomorphic encryption scheme. A further contribution of ours is to formally define the security of encryption schemes for quantum messages: we define quantum indistinguishability under chosen plaintext attacks in both the public and private-key settings. In this context, we show the equivalence of several definitions. Our schemes are the first of their kind that are secure under modern cryptographic definitions, and can be seen as a quantum analogue of classical results establishing homomorphic encryption for circuits with a limited number of multiplication gates. Historically, such results appeared as precursors to the breakthrough result establishing classical fully homomorphic encryption.

References in corpus (4)

• Quantum homomorphic encryption for circuits of low $T$-gate complexity
• Quantum walks with encrypted data
• Limitations on information theoretically secure quantum homomorphic encryption
• Delegating Private Quantum Computations

Cited by in corpus (29)

• Breaking Symmetric Cryptosystems using Quantum Period Finding
• Quantum Cryptography Beyond Quantum Key Distribution
• Quantum homomorphic encryption for circuits of low $T$-gate complexity
• Multiparty Delegated Quantum Computing
• How to Verify a Quantum Computation
• Semantic Security and Indistinguishability in the Quantum World
• Complex Quantum Networks: a Topical Review
• Unforgeable Quantum Encryption
• QFactory: classically-instructed remote secret qubits preparation
• Computational Security of Quantum Encryption
• Quantum Fully Homomorphic Encryption With Verification
• Practical quantum somewhat-homomorphic encryption with coherent states
• On the possibility of classical client blind quantum computing
• Constructions for Quantum Indistinguishability Obfuscation
• A Note on Quantum-Secure PRPs
• QEnclave -- A practical solution for secure quantum cloud computing
• The Quantum Internet: A Hardware Review
• Security Limitations of Classical-Client Delegated Quantum Computing
• Succinct Blind Quantum Computation Using a Random Oracle
• On Quantum Chosen-Ciphertext Attacks and Learning with Errors
• Quantum Fully Homomorphic Encryption by Integrating Pauli One-time Pad with Quaternions
• Composable and Finite Computational Security of Quantum Message Transmission
• Privacy and correctness trade-offs for information-theoretically secure quantum homomorphic encryption
• Quantum delegated and federated learning via quantum homomorphic encryption
• Delegating Quantum Computation in the Quantum Random Oracle Model
• Error correctable efficient quantum homomorphic encryption using Calderbank-Shor-Steane codes
• Quantum Unpredictability
• Can you sign a quantum state?
• Demonstrating Quantum Homomorphic Encryption Through Simulation