Classical Fully Homomorphic Encryption for Quantum Circuits: Difference between revisions

FHE presents a classical protocol with the help of which a completely classical Client could assign Server a quantum computation for her encrypted (hidden) input/output. Similar to any classical HE this scheme is divided into four steps: Key Generation generates keys for encryption, decryption and evaluation of the circuit; Encryption encodes the input into a secret text using the encryption key generated during Key Generation; Evaluation performs operations (implements the circuit) on the encrypted input using evaluation key generated and Decryption transforms result of the evaluation step hidden in the secret text, to outcome of the circuit for Client's input using decryption key. Following the stages of [[Secure Delegated Quantum Computation]], in preparation stage, Client encrypts her input by performing [[one time pad]] to hide it from the Server, who, in the computation stage, performs quantum computation by a completely classical evaluation step. There are two kinds of gates in Quantum Computation (See [[Glossary#Hierarchy of Quantum Gates|Glossary]]) Clifford Gates, which consists of [[Glossary#Unitary Operations|Hadamard gate]], [[Glossary#Unitary Operations|CNOT]] and [[Glossary#Unitary Operations|Pauli gates (X, Y, Z)]] and Toffoli gates (any single qubit phase/rotation gate). A universal scheme can perform both these types of gates implying that it can perform any quantum operation. Now, applying [[Glossary#Hierarchy of Quantum Gates|Clifford gates]] remains a simple step as it leaves the state with only Pauli corrections (X, Z) which are easy to handle as these gates commute with every quantum gate and hence can be shifted and cancelled out by applying corresponding inverse gate later by the Client, but when applying [[Glossary#Heirarchy of Quantum Gates|Toffoli Gates]], it leaves the state with some Pauli corrections and Clifford gate corrections depending on the one pad key used for encryption key used by Client. Decryption key cannot deal with Clifford gate errors as they do not commute with all quantum operations and hence it needs to be corrected by applying corresponding inverse gate before the operation of next gate for computation by the Server. These Clifford gate corrections are a combination of CNOT corrections dependent on encryption key and a Hadamard correction independent of encryption key. Thus, applying Hadamard requires no extra information but CNOT gate errors require revelation of the encryption key. FHE deals with this problem via Encrypted CNOT operation using Trapdoor Claw-Free Function (TCF) without revelation of encryption key to the Server (See Definitions and Proof). Finally, in the Output Correction stage, Client gets her inputs and updated encryption keys to get the correct final outcome from the secret text using her decryption key. Following is an outline of the steps to illustrate the above mentioned scheme, assuming depth of circuit (see notations used) equal to L.</br>