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 to hide it from the Server performing [[Supplementary Information#Quantum Cryptography Techniques#Quantum One Time Pad|Quantum One Time Pad]] (QOTP) using her encryption key, who, in the computation stage, performs quantum computation by a completely classical evaluation step. There are two kinds of gates in Quantum Computation (See Heirarchy of Quantum Gates in [[Supplementary Information]]) Clifford Gates, which consists of Hadamard gate, CNOT and 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 [[Supplementary Information#A General Introduction to Quantum Information#Heirarchy 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 [[Supplementary Information#A General Introduction to Quantum Information#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. Applying Hadamard requires no extra information but CNOT gate errors require revelation of the encryption key. FHE deals with this problem via [[Supplementary Information#Quantum Cryptography Techniques#Encrypted CNOT operation|Encrypted CNOT operation]] using [[Supplementary Information#Quantum Cryptography Techniques#Trapdoor Claw-Free Function (TCF)|Trapdoor Claw-Free Function (TCF)]] without revelation of encryption key to the Server. 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.

* '''Key Generation:''' Client generates L+1 classical homomorphic key sets consisting of public key, evaluation key, secret key, trapdoor information using HE.KeyGen (classical HE step). Evaluation key consists of first L pairs of secret key-trapdoor information encrypted with last L public keys such that secret key-trapdoor key pair and public key do not belong to the same key set. Evaluation key also contains this public key used to encrypt the pair.

* '''Encryption Client''' uses one time pad to hide her input and encrypts the pad key using a public key not used to encrypt the trapdoors and secret in the previous step. She then sends the hidden input with encypted pad key and classical evaluation key to the Server. In case of classical input Client uses the public key to encrypt her classical message and send it to the Server over classical channel.

* '''Circuit Evaluation''' For a quantum inputs, Server starts with the quantum one time padded state from the Client, while in case of a classical Client, Server prepare quantum states for the encrypted input. For each gate of the circuit that Server applies, he updates the encrypted Pauli encryption. In case of Toffoli gate operation, he also corrects the extra Clifford group error performing encrypted CNOT operation and then Hadamard operations on the target qubit. Operation of encrypted CNOT operation is performed using evaluation key as follows.<br/>

'''Encrypted CNOT operation''' This operation uses Trapdoor Claw Free function pairs which have the same image (output) for different pre-images(inputs) called random claw pair. Given the image it is rendered hard to find corresponding random claw without a trapdoor (inverse function). For this protocol, the HE Encryption function under a particular public key (provided in the evaluation key) is taken as one of the functions whose distribution is shifted from the other function by a natural (homomorphic) XOR operation of encrypted key bit. The functions have a common range and hence, any element in this range set would have a pre-image in the domain set of each function, together called random claw. Any pre-image pair (random claw) thus, obtained hides the pad key used for CNOT by a XOR operation. This is implied from the properties of homomorphic XOR. In simple language, if the functions are separated by encrypted pad key via a homomorphic XOR operation, so their inputs for a common output (random claw) would be separated by the (not encrypted) pad key bit. Thus, Server creates a superposition of inputs for the functions over some distribution. Next, in case of a classical input he creates a superposition of one time padded quantum state using the encrypted key. After applying the gates on qubits, for correction of CNOT gates he has two one time padded qubits as quantum state and a pad key for CNOT. The encrypted pad key was sent to the Server by the Client. For each correction, Server thus creates three registers. First has the superposition of quantum states to be operated, second has the superposition of inputs while third register has the output of the function, where function is chosen depending on the first qubit of quantum state register and input is taken from the second qubit. Hence these registers are entangled. Server, now measures the third register which reduces second register to a random claw pair as discussed before, hiding the pad key. Now, after some calculations it can be shown that if one performs Hadamard operation on the second register and then measures it, the first register is reduced to CNOT error corrected quantum state with some extra Pauli corrections. These final Pauli corrections require trapdoor information and measurement outcome of the second register (if this outcome is zero the Z correction is zero). To perform the above operation one needs ciphertext to be same throughtout the protocol and existence of a natural XOR operation. This is not known to have been achieved by a single HE together. Hence, one uses AltHE which can operate XOR for encrypted CNOT operation and HE for updation of Pauli keys. In order to do this, HE provides a conversion of ciphertext under HE to ciphertext under AltHE and vice versa. Thus, after encrypted CNOT operation, encrypted pad key bit and other measurement outcomes recrypted using public key of the evaluation key under HE. Hence, after using trapdoor functions and other information, he finds Pauli corrections encrypted under the same public key.<br/>

Server repeats the same procedure for each layer and finally sends the updated Pauli encryption and quantum one time padded output of the circuit to Client. Client uses the encrypted pad keys of both qubits related to the CNOT error and converts it to another ciphertext using AltHE.

* '''Decryption''' The sent Pauli corrections are updated with public key of the last evaluation key used. This is the (L + 1)th public key and hence, Client uses (L + 1)th secret key (which was not included in the evaluation keys) to decrypt the updated encryption of pad key sent by the Server. Thus, she uses the resulting pad key to undo the quantum one time pad on the sent output state.