Write, autoreview, editor, reviewer
3,129
edits
Prepare-and-Send Quantum Fully Homomorphic Encryption: Difference between revisions
Prepare-and-Send Quantum Fully Homomorphic Encryption (edit)
Revision as of 07:42, 11 July 2019
, 11 July 2019no edit summary
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
This [https://arxiv.org/abs/1603.09717 example protocol] achieves the functionality of [[Secure Client- Server Delegated Computation]] by a method which involves quantum offline and classical offline communication, called Quantum Fully Homomorphic Encryption (QFHE). It allows the Client to encrypt quantum data in such a way that Server can carry out any arbitrary quantum computations on the encrypted data without having to interact with the encrypting party. It hides the output and input of the computation while Server is allowed to choose the unitary operation for required computation. Thus, the circuit is known to the Server while efforts can be made to hide it from the encrypting party i.e. Client. Based on the existence of classical [https://en.wikipedia.org/wiki/Homomorphic_encryption Homomorphic Encryption] (HE) scheme, it comes with properties of [[Secure Client- Server Delegated Computation#Properties|correctness]], [[Secure Client- Server Delegated Computation#Properties|compactness]] and [[Secure Client- Server Delegated Computation#Properties|full homomorphism]]. QFHE can be used to keep the circuit private to the Server and hidden from the Client unlike UBQC where the circuit is private to the Client and hidden from the Server.</br></br> | This [https://arxiv.org/abs/1603.09717 example protocol] achieves the functionality of [[Secure Client- Server Delegated Computation]] by a method which involves quantum offline and classical offline communication, called Quantum Fully Homomorphic Encryption (QFHE). It allows the Client to encrypt quantum data in such a way that Server can carry out any arbitrary quantum computations on the encrypted data without having to interact with the encrypting party. It hides the output and input of the computation while Server is allowed to choose the unitary operation for required computation. Thus, the circuit is known to the Server while efforts can be made to hide it from the encrypting party i.e. Client. Based on the existence of classical [https://en.wikipedia.org/wiki/Homomorphic_encryption Homomorphic Encryption] (HE) scheme, it comes with properties of [[Secure Client- Server Delegated Computation#Properties|correctness]], [[Secure Client- Server Delegated Computation#Properties|compactness]] and [[Secure Client- Server Delegated Computation#Properties|full homomorphism]]. QFHE can be used to keep the circuit private to the Server and hidden from the Client unlike UBQC where the circuit is private to the Client and hidden from the Server.</br></br> | ||
'''Tags:''' [[:Category:Two | '''Tags:''' [[:Category:Two Party Protocols|Two Party]],[[:Category:Universal Task|Universal Task]], [[:Category:Quantum Functionality|Quantum Functionality]], [[Secure Delegated Quantum Computation|Secure Delegated Quantum Computation]], Quantum Offline Communication, Classical Offline Communication, [[Supplementary Information#Entanglement|Entanglement]], [[Quantum Gadgets]], Garden Hose Model, [[Prepare and Send Verifiable Quantum Fully Homomorphic Encryption]], [[Classical Fully Homomorphic Encryption for Quantum Circuits]]. | ||
[[Category:Two-Party Protocols]][[Category: Universal Task]][[Category:Quantum Functionality]] | [[Category:Two-Party Protocols]][[Category: Universal Task]][[Category:Quantum Functionality]] | ||
==Assumptions== | ==Assumptions== | ||
| Line 11: | Line 11: | ||
==Outline== | ==Outline== | ||
Homomorphic Encryption [[ | Homomorphic Encryption [[Glossary#Quantum Capable Homomorphic Encryption|(HE)]] schemes can be divided into four stages: Key Generation generates keys for encryption, decryption, and evaluation of the circuit, Encryption encodes the input into a ciphertext using encryption key, Homomorphic Evaluation performs operations (implements the circuit) on the encrypted input using evaluation key and Decryption transforms result of the ciphertext to actual outcome of the circuit using decryption key. This protocol requires Client to prepare and send the quantum states to Server, hence the name, ''Prepare and Send QFHE''. A QFHE scheme is fundamentally different from classical FHE in the aspect that an evaluation key is allowed to be a quantum state in the former case. Also, in the last step decryption for FHE is carried out subsystem by subsystem. This cannot be correct for QFHE as quantum states can be entangled, hence decryption should be carried out on the system as a whole. The QFHE version of encryption is based on quantum one-time pad [Quantum One Time Pad] i.e. randomly applying a Pauli Gate (X, Y, Z, I) in order to hide the input. A Fully Homomorphic Encryption can implement Universal Gates (a set of gates which can implement any quantum circuit). Most of the gates in this set work well with QOTP while for T gates one needs an additional gadget, in order to implement any arbitrary circuit and make the scheme Fully Homomorphic. This adds an additional step called ”Gadget Construction” during Key Generation Stage in this protocol | ||
*'''Key Generation''' | |||
This step generates homomorphic key sets consisting of the classical public key for encryption, a classical private key for decryption and a quantum evaluation key for operation on the encrypted input state. If the circuit involves L T gates, Client needs L+1 such key sets for L gadgets and one input state. The Client uses the classical HE Key Generation (HE.KeyGen) to get classical key sets. She stores all the public keys and secret keys in two separate sets (tuples). Quantum evaluation keys consist of the classical evaluation keys and L gadgets. Once constructed, the gadget is also encrypted using all public keys except the first one by the Client. As construction of gadgets takes secret keys (first L) as inputs, the public key used for its encryption should not belong to the same homomorphic key set used to construct the gadget. A classical description of the gadget, useful for evaluation is also encrypted and included in the gadget. Construction and encryption of gadgets is described in the last step.<br/> | This step generates homomorphic key sets consisting of the classical public key for encryption, a classical private key for decryption and a quantum evaluation key for operation on the encrypted input state. If the circuit involves L T gates, Client needs L+1 such key sets for L gadgets and one input state. The Client uses the classical HE Key Generation (HE.KeyGen) to get classical key sets. She stores all the public keys and secret keys in two separate sets (tuples). Quantum evaluation keys consist of the classical evaluation keys and L gadgets. Once constructed, the gadget is also encrypted using all public keys except the first one by the Client. As construction of gadgets takes secret keys (first L) as inputs, the public key used for its encryption should not belong to the same homomorphic key set used to construct the gadget. A classical description of the gadget, useful for evaluation is also encrypted and included in the gadget. Construction and encryption of gadgets is described in the last step.<br/> | ||
*'''Gadget Construction''' This step involves the construction of gadgets to correct any additional phase gate error on the input due to T gates in the circuit. If there are L T gates in the Circuit, one needs L Gadgets constructed using L private keys and then encrypted using L public keys. The public key used for encryption should not belong to the same homomorphic key set of the private key used for construction. A gadget consists of 2m EPR pairs (maximally entangled qubits). The client starts with 4m such pairs. Performs pairwise Bell measurement on one-half of the EPR pairs. Pairs for Bell measurement are chosen according to the private decryption key used for the particular gadget. This leaves the other half of the EPR pairs entangled in the same pairs as chosen by Client to perform bell measurement. E.g. if (a,b) and (c,d) denote two EPR pairs and one performs bell measurement on a and c, then b and d become maximally entangled with some extra Pauli X, Z corrections due to measurement (refer to a one-pad key in supplementary draft). These corrections are determined by Client’s measurement outcomes. The resulting gadget thus has 2m EPR pairs, some of which have an inverse phase gate. Classical information of a gadget includes private key used, Client’s measurement outcomes and locations of inverse phase gates. This data is encrypted with the public key. Hence, L such gadgets consisting of encrypted classical information and 2m EPR pairs quantum one-time padded by the Pauli X, Z gates, are sent to the server.<br/> | **'''Gadget Construction''' This step involves the construction of gadgets to correct any additional phase gate error on the input due to T gates in the circuit. If there are L T gates in the Circuit, one needs L Gadgets constructed using L private keys and then encrypted using L public keys. The public key used for encryption should not belong to the same homomorphic key set of the private key used for construction. A gadget consists of 2m EPR pairs (maximally entangled qubits). The client starts with 4m such pairs. Performs pairwise Bell measurement on one-half of the EPR pairs. Pairs for Bell measurement are chosen according to the private decryption key used for the particular gadget. This leaves the other half of the EPR pairs entangled in the same pairs as chosen by Client to perform bell measurement. E.g. if (a,b) and (c,d) denote two EPR pairs and one performs bell measurement on a and c, then b and d become maximally entangled with some extra Pauli X, Z corrections due to measurement (refer to a one-pad key in supplementary draft). These corrections are determined by Client’s measurement outcomes. The resulting gadget thus has 2m EPR pairs, some of which have an inverse phase gate. Classical information of a gadget includes private key used, Client’s measurement outcomes and locations of inverse phase gates. This data is encrypted with the public key. Hence, L such gadgets consisting of encrypted classical information and 2m EPR pairs quantum one-time padded by the Pauli X, Z gates, are sent to the server.<br/> | ||
Finally, Client stores all the gadgets with the classical evaluation key of the corresponding secret key (generated from HE.KeyGen) used to construct the gadget, as the set of quantum evaluation keys. Note that, the gadgets are quantum states and classical evaluation keys are random numbers, the resulting quantum evaluation key is what we call a classical-quantum (CQ) state. | Finally, Client stores all the gadgets with the classical evaluation key of the corresponding secret key (generated from HE.KeyGen) used to construct the gadget, as the set of quantum evaluation keys. Note that, the gadgets are quantum states and classical evaluation keys are random numbers, the resulting quantum evaluation key is what we call a classical-quantum (CQ) state. | ||
*'''Encryption''' This step is used to encrypt the quantum input into a quantum ciphertext using the first public key which has not been used for gadget construction. Every input qubit state is quantum one time padded by the Client, using two classical random bits, one of which decided the operation of Pauli-X and the other operation of Pauli-Z gate on the qubit state. She also encrypts the classical random bits (called pad key) with the same public key using classical HE (HE.Enc) and hence stores it with the corresponding encrypted qubit state as a classical-quantum state. She then sends this CQ state, encrypted pad key, public key tuple, and evaluation key tuple to Server. | |||
This step is used to encrypt the quantum input into a quantum ciphertext using the first public key which has not been used for gadget construction. Every input qubit state is quantum one time padded by the Client, using two classical random bits, one of which decided the operation of Pauli-X and the other operation of Pauli-Z gate on the qubit state. She also encrypts the classical random bits (called pad key) with the same public key using classical HE (HE.Enc) and hence stores it with the corresponding encrypted qubit state as a classical-quantum state. She then sends this CQ state, encrypted pad key, public key tuple, and evaluation key tuple to Server. | *'''Circuit Evaluation''' This step operates the circuit on the encrypted input state and updates the encrypted classical information using the evaluation key. As stated earlier, any circuit can be implemented using a set of Universal Gates. This set consists of Clifford Gates and T gates. | ||
This step operates the circuit on the encrypted input state and updates the encrypted classical information using the evaluation key. As stated earlier, any circuit can be implemented using a set of Universal Gates. This set consists of Clifford Gates and T gates. | |||
The Clifford group gates may affect a single qubit or multiple qubits but they follow a simple set of rules for updation of the encrypted classical information (pad key), given in the pseudocode. The server operates the circuit and with each gate in the circuit, it updates the encrypted classical description.<br/> | The Clifford group gates may affect a single qubit or multiple qubits but they follow a simple set of rules for updation of the encrypted classical information (pad key), given in the pseudocode. The server operates the circuit and with each gate in the circuit, it updates the encrypted classical description.<br/> | ||
On the other hand, T gates affect only single qubits but one needs to make use of the gadgets constructed during key generation. The issue with T gates is that it adds an additional Phase gate (P) depending on the classical random bit used for QOTP in the previous step. As P gates do not commute like Pauli-X and Pauli-Z, so they need to be corrected before applying the next gate by the Server. This would reveal the pad key used for QOTP to the Server. Hence, to avoid this, the Client constructed gadgets, which apply an Inverse Phase operator or Identity on a qubit after every T-Gate, depending on the encrypted bit without leaking any information about the pad key. Thus, after applying a T gate on a qubit, P error is removed using a gadget as follows. | On the other hand, T gates affect only single qubits but one needs to make use of the gadgets constructed during key generation. The issue with T gates is that it adds an additional Phase gate (P) depending on the classical random bit used for QOTP in the previous step. As P gates do not commute like Pauli-X and Pauli-Z, so they need to be corrected before applying the next gate by the Server. This would reveal the pad key used for QOTP to the Server. Hence, to avoid this, the Client constructed gadgets, which apply an Inverse Phase operator or Identity on a qubit after every T-Gate, depending on the encrypted bit without leaking any information about the pad key. Thus, after applying a T gate on a qubit, P error is removed using a gadget as follows. | ||
| Line 27: | Line 25: | ||
*'''Recryption (QFHE.Rec())''' Server recrypts pad key of the qubit with the same public key that encrypts the corrected output state i.e. the one used for the corresponding gadget. Then, he updates the encrypted pad key according to the T Gate (similar to what is done for the Clifford Gate), Client’s encrypted measurement outcomes and Server’s (his) measurement outcomes. | *'''Recryption (QFHE.Rec())''' Server recrypts pad key of the qubit with the same public key that encrypts the corrected output state i.e. the one used for the corresponding gadget. Then, he updates the encrypted pad key according to the T Gate (similar to what is done for the Clifford Gate), Client’s encrypted measurement outcomes and Server’s (his) measurement outcomes. | ||
The server performs all the Clifford and T gates in the circuit following the respective procedure given above. Finally, he is left with the one time padded quantum output of the computation together with the required classical pad key encrypted with the public key of the gadget used for the last T gate, Lth public key. The server sends both the quantum state and classical encryptions to the Client. | The server performs all the Clifford and T gates in the circuit following the respective procedure given above. Finally, he is left with the one time padded quantum output of the computation together with the required classical pad key encrypted with the public key of the gadget used for the last T gate, Lth public key. The server sends both the quantum state and classical encryptions to the Client. | ||
'''Decryption''' The Client uses skL, which was not used to create any gadget (Gadgets used 0-(L-1) secret keys only) and decrypts sent encryptions to obtain the pad key. The pad key thus obtained determines the Pauli operations on the sent quantum state to obtain the final and correct outcome of the computation. The client performs the required operations on individual qubits of the quantum state and gets the output of his computation. | |||
The Client uses skL, which was not used to create any gadget (Gadgets used 0-(L-1) secret keys only) and decrypts sent encryptions to obtain the pad key. The pad key thus obtained determines the Pauli operations on the sent quantum state to obtain the final and correct outcome of the computation. The client performs the required operations on individual qubits of the quantum state and gets the output of his computation. | |||
== Notation == | == Notation == | ||