Write, autoreview, editor, reviewer
3,125
edits
Classical Fully Homomorphic Encryption for Quantum Circuits: Difference between revisions
Classical Fully Homomorphic Encryption for Quantum Circuits (edit)
Revision as of 08:05, 11 July 2019
, 11 July 2019no edit summary
No edit summary |
|||
| Line 1: | Line 1: | ||
The [https://arxiv.org/abs/1708.02130 example protocol] achieves the functionality of [[Secure Client- Server Delegated Quantum Computation|Delegated Quantum Computation]] by a method which involves fully [[Secure Client- Server Delegated Quantum Computation#Protocols | The [https://arxiv.org/abs/1708.02130 example protocol] achieves the functionality of [[Secure Client- Server Delegated Quantum Computation|Delegated Quantum Computation]] by a method which involves fully [[Secure Client- Server Delegated Quantum Computation#Protocols|classical offline]] and no [[Secure Client- Server Delegated Quantum Computation#Protocols|quantum communication]]. It uses only classical [[Glossary#Quantum Capable Homomorphic Encryption|Homomorphic Encryption]] (HE) scheme to evaluate quantum circuits for classical input/output. It allows a fully classical Client to hide her data such that Server can carry out any arbitrary quantum computation on the encrypted data without having any knowledge about Client’s inputs. It hides the output and input of the computation while Server is allowed to choose the [[Glossary#Unitary Operations|unitary operation]] (any quantum gate) for required computation. Quantum offline communication would be required if Client’s input and output is quantum.</br></br> | ||
'''Tags:''' [[:Category:Two Party Protocols|Two Party]], [[:Category:Quantum Functionality|Quantum Functionality]], [[:Category:Universal Task|Universal Task]], [[Secure Client- Server Delegated Quantum Computation]], [[Prepare and Send Quantum Fully Homomorphic Encryption|Prepare and Send Quantum FHE]], Classical Offline Communication, [[ | '''Tags:''' [[:Category:Two Party Protocols|Two Party]], [[:Category:Quantum Functionality|Quantum Functionality]], [[:Category:Universal Task|Universal Task]], [[Secure Client- Server Delegated Quantum Computation]], [[Prepare and Send Quantum Fully Homomorphic Encryption|Prepare and Send Quantum FHE]], Classical Offline Communication, [[Glossary#Superposition|Superposition]], Trapdoor Claw-Free Functions, [https://en.wikipedia.org/wiki/Learning_with_errors Learning With Errors], Encrypted CNOT Operation. | ||
[[Category:Two Party Protocols]][[Category:Quantum Functionality]][[Category:Universal Task]] | [[Category:Two Party Protocols]][[Category:Quantum Functionality]][[Category:Universal Task]] | ||
==Assumptions== | ==Assumptions== | ||
* This protocol is secure against honest but curious adversary setting. | * This protocol is secure against honest but curious adversary setting. | ||
* HE is a classical leveled fully homomorphic encryption scheme which is | * HE is a classical leveled fully homomorphic encryption scheme which is [[Glossary#Quantum Capable Homomorphic Encryption|quantum capable]] for given depth of one layer of circuit, <math>L_c</math> (See Notations below). | ||
* A [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#bqp BQP] Server (a quantum computer) can generate a superposition of inputs for the encryption function over some distribution given the public key used for encryption. The protocol takes [https://en.wikipedia.org/wiki/Learning_with_errors learning with errors] assumption. | * A [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#bqp BQP] Server (a quantum computer) can generate a superposition of inputs for the encryption function over some distribution given the public key used for encryption. The protocol takes [https://en.wikipedia.org/wiki/Learning_with_errors learning with errors] assumption. | ||
== Outline== | == Outline== | ||
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 | 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> | ||
The preparation stage incorporates, | The preparation stage incorporates, | ||
* '''Key Generation:''' Client generates L+1 classical homomorphic key sets consisting of public key, evaluation key, secret key, trapdoor information (a piece of information required to invert the function used for encrypted CNOT operation, as explained in Circuit Evaluation) 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. | * '''Key Generation:''' Client generates <math>L+1</math> classical homomorphic key sets consisting of public key, evaluation key, secret key, trapdoor information (a piece of information required to invert the function used for encrypted CNOT operation, as explained in Circuit Evaluation) 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 classical one time pad to hide her input and encrypts the pad key with the first public key (not used to encrypt any trapdoor-secret key pair) using HE.Enc() (classical HE step). She then sends the hidden classical input with encrypted pad key and classical evaluation key to the Server over classical channel. This step marks the end of preparation stage.</br> | * '''Encryption:''' Client uses classical one time pad to hide her input and encrypts the pad key with the first public key (not used to encrypt any trapdoor-secret key pair) using HE.Enc() (classical HE step). She then sends the hidden classical input with encrypted pad key and classical evaluation key to the Server over classical channel. This step marks the end of preparation stage.</br> | ||
Further, the computation stage incorporates, | Further, the computation stage incorporates, | ||
* '''Circuit Evaluation:''' Server starts with the classical one time padded states from the Client and generates the required quantum states. For each gate of the circuit that Server applies, he updates the encrypted Pauli encryption according to rules given in Pseudo code below. In case of Toffoli gate operation, an additional step is incorporated where he corrects the extra Clifford gate error performing encrypted CNOT operation and then Hadamard operation on the target qubit. This step uses evaluation key and can be explained as follows.</br> | * '''Circuit Evaluation:''' Server starts with the classical one time padded states from the Client and generates the required quantum states. For each gate of the circuit that Server applies, he updates the encrypted Pauli encryption according to rules given in Pseudo code below. In case of Toffoli gate operation, an additional step is incorporated where he corrects the extra Clifford gate error performing encrypted CNOT operation and then Hadamard operation on the target qubit. This step uses evaluation key and can be explained as follows.</br> | ||
'''Encrypted CNOT operation''' All errors imposed by Toffoli gates can be represented using encrypted CNOT operation, a Hadamard operation and a set of Pauli gates (X, Z). All errors imposed by Clifford gates can be represented by a combination of Pauli gates. A mathematical representation of this step can be found in the [[Supplementary Information]]. | '''Encrypted CNOT operation''' All errors imposed by Toffoli gates can be represented using encrypted CNOT operation, a Hadamard operation and a set of Pauli gates (X, Z). All errors imposed by Clifford gates can be represented by a combination of Pauli gates. A mathematical representation of this step can be found in the [[Supplementary Information]]. | ||
#'''TCF:''' 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 a hard problem to find this corresponding random claw without its trapdoor information (example, a piece of information required to invert the function). For this protocol, the HE Encryption function (HE.Enc()) is taken as one of the functions. A second function whose distribution is shifted from the previous function by a natural (homomorphic) XOR operation (a requirement for the [[ | #'''TCF:''' 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 a hard problem to find this corresponding random claw without its trapdoor information (example, a piece of information required to invert the function). For this protocol, the HE Encryption function (HE.Enc()) is taken as one of the functions. A second function whose distribution is shifted from the previous function by a natural (homomorphic) XOR operation (a requirement for the [[Glossary#Quantum Capable Homomorphic Encryption|classical HE]] scheme used) of encrypted key bit used for that encryption function. This means, the functions have a common range such that for every image (output), the pre-images (input) for each of the functions stated above would also differ by a XOR operation of actual (not encrypted) key bit. Thus, any element in the said range set would have one pre-image in the domain set of each function, together called random claw pair. If one performs a XOR operation on the pair, the result is pad key bit. This is implied from the properties of homomorphic XOR. In simple words, the above paragraph implies that if two functions are separated by encrypted pad key via a homomorphic XOR operation, their inputs for a common output (random claw pair) would be separated by the (not encrypted) pad key bit. Thus, any pre-image pair (random claw) thus, obtained, hides the pad key (to be used later for Encrypted CNOT operation). | ||
#'''Server's preparation''' Thus, Server creates a superposition of inputs for the functions over some distribution. Next, he creates a superposition of quantum states generated from Client's input. After applying the gates on qubits, for correction of CNOT errors, Server creates three registers. First has the superposition of quantum states generated from Client's input, second has the superposition on a distribution chosen for inputs of the function while third register has the output of one of the two functions illustrated above, where the function (one of the two) is chosen according to the first qubit of the first register and its quantum input is taken from the second register. 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. It is still hidden from the Server as he does not know trapdoor information to be able to know the random claw pair and he cannot compute it from the measured output as it is a hard problem. | #'''Server's preparation''' Thus, Server creates a superposition of inputs for the functions over some distribution. Next, he creates a superposition of quantum states generated from Client's input. After applying the gates on qubits, for correction of CNOT errors, Server creates three registers. First has the superposition of quantum states generated from Client's input, second has the superposition on a distribution chosen for inputs of the function while third register has the output of one of the two functions illustrated above, where the function (one of the two) is chosen according to the first qubit of the first register and its quantum input is taken from the second register. 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. It is still hidden from the Server as he does not know trapdoor information to be able to know the random claw pair and he cannot compute it from the measured output as it is a hard problem. | ||
#'''Server's Toffoli gate operation''' After some calculations it can be shown that if Server performs Hadamard operation on the second register and then measures it, the first register is reduced to corrected quantum state with some extra Pauli corrections. These final Pauli corrections require trapdoor information and measurement outcome of the second register. To perform the above operation one needs the secret text 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, this protocol uses AltHE (an alternate HE) which can operate XOR for encrypted CNOT operation while he uses HE for updation of Pauli keys. In order to do this, HE provides a conversion of secret text under HE to secret text under AltHE and vice versa. Thus, after encrypted CNOT operation, encrypted pad key bit and other measurement outcomes are recrypted using public key provided in the evaluation key for that step, under HE. Thus, the trapdoor information and pad key bit are encrypted under same public key. Now, using the measurement outcome and the encrypted trapdoor information with recrypted pad key, Server obtains Pauli corrections. The Server encrypts Pauli corrections under public key for corresponding layer and hence updates the recrypted pad key<br/> | #'''Server's Toffoli gate operation''' After some calculations it can be shown that if Server performs [[Glossary#Unitary Operations|Hadamard operation]] on the second register and then measures it, the first register is reduced to corrected quantum state with some extra [[Glossary#Unitary Operations|Pauli corrections]]. These final Pauli corrections require trapdoor information and measurement outcome of the second register. To perform the above operation one needs the secret text 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, this protocol uses AltHE (an alternate HE) which can operate XOR for encrypted CNOT operation while he uses HE for updation of Pauli keys. In order to do this, HE provides a conversion of secret text under HE to secret text under AltHE and vice versa. Thus, after encrypted CNOT operation, encrypted pad key bit and other measurement outcomes are recrypted using public key provided in the evaluation key for that step, under HE. Thus, the trapdoor information and pad key bit are encrypted under same public key. Now, using the measurement outcome and the encrypted trapdoor information with recrypted pad key, Server obtains Pauli corrections. The Server encrypts Pauli corrections under public key for corresponding layer and hence updates the recrypted pad key<br/> | ||
#'''Server's Clifford gate operation''' Server obtains with Pauli corrections according to rules described in the Pseudo code and updates the recrypted pad key as before.</br> | #'''Server's Clifford gate operation''' Server obtains with Pauli corrections according to rules described in the Pseudo code and updates the recrypted pad key as before.</br> | ||
* '''Decryption''' Server repeats the same procedure for each layer and at the end of last layer, sends the updated recryption of pad key and classical measurement output of the first register (containing the corrected quantum state encrypted by pad key) to Client. Client converts the pad key to another secret text using AltHE. The sent pad key is recrypted with public key of the last (<math>L_{th}</math>) evaluation key used. This is the <math>(L + 1)_{th}</math> public key. Hence, Client uses <math>(L + 1)_{th}</math> secret key (which was not included in the evaluation keys) to decrypt the updated encryption of pad key sent by the Server. She (Client) uses the resulting pad key to undo the one time pad on the sent output. | * '''Decryption''' Server repeats the same procedure for each layer and at the end of last layer, sends the updated recryption of pad key and classical measurement output of the first register (containing the corrected quantum state encrypted by pad key) to Client. Client converts the pad key to another secret text using AltHE. The sent pad key is recrypted with public key of the last (<math>L_{th}</math>) evaluation key used. This is the <math>(L + 1)_{th}</math> public key. Hence, Client uses <math>(L + 1)_{th}</math> secret key (which was not included in the evaluation keys) to decrypt the updated encryption of pad key sent by the Server. She (Client) uses the resulting pad key to undo the one time pad on the sent output. | ||