Fully Homomorphic Encryption — Classical and Quantum
Stub. The GSW fully homomorphic encryption (FHE) scheme, built on Regev's LWE-based encryption, letting arbitrary computation be performed directly on ciphertexts; extending this to evaluate quantum circuits homomorphically — applying encrypted Pauli (X/Z) and Clifford gates directly, and trapdoor claw-free functions (TCFs) as the tool for handling the one quantum gate (beyond Clifford) that resists the easy approach, including implementing an encrypted CNOT via a TCF.
Corresponds to Chapters 19–22. Fully homomorphic encryption lets a third party compute on encrypted data without ever decrypting it; the GSW scheme achieves this building directly on Regev’s LWE-based public-key encryption, representing ciphertexts so that addition and multiplication of plaintexts correspond to simple matrix operations on ciphertexts. Quantum FHE asks for the same thing where the circuit being homomorphically evaluated is itself a quantum circuit: applying an encrypted Pauli or gate, or more generally a Clifford gate, turns out to be easy (it just updates a classical “key” tracking which corrections are needed), but gates outside the Clifford group (needed for universal quantum computation) don’t commute as nicely with the encryption. Trapdoor claw-free functions (TCFs) — pairs of inputs that collide under a public function but whose collision is hard to find without a trapdoor — are the tool that resolves this, including a construction of an encrypted CNOT gate using a TCF. TCFs reappear as the central tool for testing-a-qubit-and-classical-verification-of-quantum-computation.
Outline (TODO — flesh out each)
- Regev public-key encryption, recap
- The GSW FHE scheme
- Evaluating quantum circuits homomorphically
- Applying encrypted X and Z gates
- Applying encrypted Clifford gates
- Trapdoor claw-free functions (TCFs) — definition and properties
- Obtaining a superposition over a claw
- Beyond Clifford — encrypted CNOT via a TCF