Classical Fully Homomorphic Encryption for Quantum Circuits: Difference between revisions

From Quantum Protocol Zoo
Jump to navigation Jump to search
mNo edit summary
No edit summary
 
(154 intermediate revisions by 3 users not shown)
Line 1: Line 1:
The example protocol [https://arxiv.org/abs/1708.02130 Mahadev (2017)] achieves the functionality of [[Secure Delegated Quantum Computation]] by a method which involves fully [[Secure Delegated Quantum Computation#Protocols#Classical Offline Communication-No Quantum Communication|classical offline]] and no [[Secure Delegated Quantum Computation#Protocols#Classical Offline Communication-No Quantum Communication|quantum communication]]. It uses only classical [[Supplementary Information#Quantum Cryptography Techniques#Quantum Capable Homomorphic Encryption|Homomorphic Encryption]] (HE) scheme to evaluate quantum circuits for classical input/input. 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 unitary operation (any quantum gate) for required computation. Quantum offline communication would be required if Client’s input and output is quantum.</br></br>
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 Delegated Quantum Computation|Secure Delegated Quantum Computation]], [[Prepare and Send Quantum Fully Homomorphic Encryption|Prepare and Send Quantum FHE]], Classical Offline Communication, [[Supplementary Information#Superposition|Superposition]], [[Supplementary Information#Trapdoor Claw-Free Functions|Trapdoor Claw-Free Functions (TCF)]], [[Supplementary Information#Learning With Errors|Learning With Errors]], [[Supplementary Information#Encrypted CNOT Operation|Encrypted CNOT Operation]].
'''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 [[Supplementary Information#Quantum Cryptography Techniques#Quantum Capable Homomorphic Encryption|quantum capable]] for given depth of the circuit (<math>L_c</math>).
* 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 [[Supplementary Information#Complexity|BQP]] Server can generate a superposition of inputs for the encryption function over some distribution given the public key used for encryption. The protocol takes 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 ciphertext using encryption key, Homomorphic Evauation performs operations (imlpements 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. Following the stages of Delegated Quantum Computation, in preparation stage, Client encrypts (hides) her inputs from the Server who, in the computation stage, performs quantum computation by a completely classical evaluation step where applying Clifford gates remains a simple step as it leaves the state with only Pauli corrections which are easy to handle by QOTP, but when applying Toffoli Gates, it leaves the state with some Pauli corrections and Clifford gate corrections depending on the one pad key used for (QOTP) by Client. QOTP cannot deal with Clifford gate errors and hence it needs to be corrected before the operation of next gate. These Clifford gate corrections are a combination of CNOT corrections dependent on pad key and Hadamard correction independent of pad key. Applying Hadamard requires no extra information but CNOT gate errors require revelation of one pad keys. FHE deals with this problem via Encrypted CNOT operation using TCF which only needs client to prepare one-time padded superposition states. Sever thus, updates the Pauli keys accordingly and at the end of computation, sends encrypted output to the Client with updated Pauli keys. Client decrypts sent states and gets correct output in Output Correction stage. Following is an outline of the steps involved in the scheme, assuming depth of circuit (see notations used) equal to L.
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. 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>
* '''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.
The preparation stage incorporates,
* '''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.
* '''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.
* '''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/>
* '''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>
'''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/>
Further, the computation stage incorporates,
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.
* '''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>
* '''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.
'''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 [[Classical Fully Homomorphic Encryption for Quantum Circuits #Pseudo Code|Pseudo Code]] below.  
== Notations ==
#'''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).
* k, security parameter
#'''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.  
* Lc, depth of the circuit/ no. of layers
#'''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/>
* x˜ encryption of x
#'''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>
* Lc, depth of a layer of circuit where each layer contains clifford gates and Toffoli gates
* '''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.
* L, depth of the circuit (no. of layers in the circuit)
* {pki,ski,evki,tski}, ith homomorphic key set generated from HE.KeyGen(). Public key for encryption, secret key for decryption, evaluation function key, trapdoor information required for randomness recovery from ciphertexts.
* y, measurement outcome of third register
* (µ0,r0)(µ1,r1) random claw for TCF pair, for given y
* d, measurement outcome of the second register
== Hardware Requirements ==


== Properties ==
== Properties ==
Line 34: Line 28:
*''Circuit Privacy'' This protocol is not circuit private as both Client and Server know the quantum circuit used for performing the computation.
*''Circuit Privacy'' This protocol is not circuit private as both Client and Server know the quantum circuit used for performing the computation.
*''Full Homomorphism'' This protocol is fully homomorphic i.e. Server can operate any quantum circuit using this protocol.
*''Full Homomorphism'' This protocol is fully homomorphic i.e. Server can operate any quantum circuit using this protocol.
*''Circular Security'' This orotocol has a stronger notion of circular security where not only the secret key but also the trapdoor functions are encrypted when provided to the Server.
*''Circular Security'' This protocol has a stronger notion of circular security where not only the secret key but also the trapdoor functions are encrypted when provided to the Server.
== Notation ==
*<math>m</math>: classical data of client's required quantum input states
*<math>\lambda</math>: security parameter
* <math>k</math>: security parameter
* <math>\tilde{x}</math>: encrypted pad key
*<math>s</math>: concatenated pad key elements
*<math>c=HE.Enc_{pk}(s)</math> Encryption of s using public key <math>pk</math> via classical HE encryption step.
*<math>\hat{c}</math>: converted c using classical HE in order to use it with <math>AltHE</math>
* <math>\tilde{x}^{[l]}</math>: <math>l^{th}</math> bit of encrypted pad key
* <math>L_c</math>: depth of a layer of circuit where each layer contains Clifford gates and Toffoli gates
* <math>L</math>: depth of the circuit (no. of layers in the circuit)
* <math>\{pk_i, sk_i, evk_i, t_{sk_i}\}</math>: <math>i_{th}</math> homomorphic key set generated from HE.KeyGen(). Public key for encryption, secret key for decryption, evaluation function key, trapdoor information required for randomness recovery from secret texts.
* <math>y</math>: measurement outcome of third register
* <math>(\mu_0,r_0) (\mu_1,r_1)</math>: random claw for pair, for given y
* <math>d</math>: measurement outcome of the second register


== Pseudo-Code==  
== Requirements ==
*'''Network Stage:''' [[:Category:Quantum Memory Network Stage|Quantum Memory]] [[Category:Quantum Memory Network Stage]]
*'''Required Network Parameters:'''
**'''<math>\epsilon_j</math>''', which measures the error due to noisy operations.
**Number of communication rounds
**Circuit depth
**Number of physical qubits used
*The concerned protocol requires classical HE scheme.
*Classical offline communication links
*Communication can be performed over a classical network with only one quantum node (in case of classical input and output).
*The functions <math>f_0, f_1</math> used must be trapdoor claw-free(TCF) such that one it is not possible to find a triple <math>(\mu_0,\mu_1,y)</math> such that <math>f_0(\mu_0)=f_1(\mu_1)=y</math>
 
==Knowledge Graph==
 
{{graph}}
 
==Protocol Description==  
*Boxed texts are not part of the code but contain proofs used in various steps, illustrated for a better understanding of the protocol.
==='''Stage 1''' Client’s Preparation===
==='''Stage 1''' Client’s Preparation===
   
   
*'''Input:''' k, L, Lc, classical message m, ( and Quantum Input |ψi in case of quantum inputs)
*Input: <math>k, L, L_c</math>, classical message <math>m</math>
*'''Output:''' Homomorphic key sets (pki,evki,ski,tski), encrypted pad key ˜a,˜b (and Quantum One time Padded Output State XaZb |ψi in case of quantum output)
*Output: Homomorphic key sets <math>(pk_i,evk_i,sk_i, t_{sk_i})</math>, encrypted pad key <math>\tilde{z}, \tilde{x}</math>, One time Padded message (<math>l</math>)
''Key Generation (FHE.KeyGen(,1L))''
**'''Key Generation (FHE.KeyGen(<math>1^{\lambda}, 1^L</math>))'''
# For 1 i L + 1,
# For <math>1\leq i\leq L + 1</math>,  
# Client generates homomorphic key set, (pki,evki,ski,tski) =HE.Keygen(1 The public key pk is pk1 and the secret key sk is skL+1.
# Client generates homomorphic key set, <math>(pk_i,evk_i,sk_i, t_{sk_i}) = </math>HE.Keygen(<math>1^{\lambda}, 1^{L_c}</math>).</br>The public key <math>pk</math> is <math>pk_1</math> and the secret key <math>sk</math> is <math>sk_{L+1}</math>. </br>The evaluation key <math>evk_i</math> consists of <math>(pk_{i+1},</math>HE.Enc<math>_{pk_{i+1}}(sk_{i})</math>, HE.Enc<math>_{pk_{i+1}}(t_{sk_i})</math>) for <math>1\leq i\leq L</math>.
The evaluation key evk consists of (evk1,...,evkL+1) as well as (pki+1,HE.Encpki+1(ski), HE.Encpki+1(tski)) for 1 i L.
**'''Encryption (FHE.Enc<math>_{pk}(m)</math>))'''
''Encryption (FHE.Encpk(m))''
#Client chooses pad key for each message bit <math>z,x\in\{0,1\}^{\lambda}</math>.
# Client chooses pad key for each message bit a,b ∈ {0,1}λ.
#She one time pads the message m, <math>l= x\oplus m</math> <div class="floatright">//z is used for quantum input <math>Z^zX^x|\psi\rangle</math> where <math>|\psi\rangle</math> is quantum input.</div>
# She then encrypts this pad key and sends it to the Server with the evaluation keys. HE.Encpk1(a,b)),
#She then encrypts the pad key. HE.Enc<math>_{pk_1}(z,x)</math>
# She sends encrypted classical message XaZb |li which can be represented as the classical string a⊕m. In case of quantum output Client uses pad key to hide her quantum state using QOTP (XaZb |ψi) and then sends this hidden state to the Server alongwith the encrypted pad key.
# She sends the encrypted message and pad key to the Server with the evaluation keys.


=== '''Stage 2''' Server’s Computation ===
=== '''Stage 2''' Server’s Computation ===
   
   
Input: evaluation key (evki), encrypted pad key ˜a,˜b concatenation (c), one time padded message l (and Quantum One time Padded Output State in case of quantum output)
*Input: <math>\mathrm{evk}_i</math>, pad key elements concatenation (<math>s</math>), encryption of s under HE (<math>c=\mathrm{HE.Enc}_{pk}(s)</math>), one time padded message (<math>l</math>)
Output: updated encryption of pad key ˜a,˜b (and Quantum One time Padded Output State
*Output: Updated encryption of pad key <math>\tilde{z},\tilde{x}</math> and final classical outcome after performing the circuit.
Xa˜Z˜bC |ψi in case of quantum output, where C is the quantum circuit)
**'''Circuit Evaluation (FHE.Eval())'''
''Circuit Evaluation (FHE.Eval())''
#Server creates a quantum superposition state for encrypted input <math>l</math>: <math>Z^zX^x|\psi\rangle</math>, where </br><math>|\psi\rangle=\sum_{a,b\epsilon\{0,1\}}\alpha_{ab}|a,b\rangle</math> represents the two qubits superposition state for classical message m,</br> <math>Z^zX^x</math> represents quantum one time pad. </br>
* Let the Circuit be denoted by C and the gates be ci
# For all i, Server applies gate <math>c_i</math> on qubit l and the <math>l_{th}</math> bits of pad key <math>(\tilde {x}^{[l]},\tilde{z}^{[l]})</math> are updated to <math>(\tilde {x}'^{[l]},\tilde{z}'^{[l]})</math> as follows.
# Server creates a superposition state for the encrypted classical message and Pauli one time pads it using encrypted pad key. He applies the circuit on it as follows:
## If <math>c_i=\{P,H,CNOT\}</math>, a Clifford gate then <div class="floatright">//(<math>c_iZ^{z^{[l]}}X^{x^{[l]}}|\psi\rangle=Z^{z'^{[l]}}X^{x'^{[l]}}c_i|\psi\rangle</math>)</div>
# For all i, ci gate is applied on qubit l and the lth bits of pad key (˜a[l],˜b[l]) are updated to (a˜0[l],˜b0[l]) as follows.
### if <math>c_i=</math>H then<div class="floatright">//Hadamard Gate</div></br><math>(\tilde {x}^{[l]},\tilde{z}^{[l]})\rightarrow (\tilde{z}^{[l]},\tilde{x}^{[l]})</math><div class="floatright">//Hadamard tranforms X gate into Z and Z into X</div>
## If ci = {P,H,CNOT}, a Clifford gate then //(ciXa[l]Zb[l]ψ = Xa0[l]Zb0[l]ciψ)
### if <math>c_i=</math>P then <div class="floatright">//Pauli Gate</div></br><math>(\tilde {x}^{[l]},\tilde{z}^{[l]})\rightarrow (\tilde{x}^{[l]},\tilde{x}^{[l]}\oplus\tilde{z}^{[l]})</math>
### if ci =H then //Hadamard Gate<br/>(a˜[l],˜b[l]) → (˜b[l],[l]) (Hadamard tranforms X gate into Z and Z into X)
### if <math>c_i=CNOT_{l,n}</math> with m as target bit and n as control bit then <div class="floatright">//CNOT</div></br>(<math>\tilde {x}^{[l]},\tilde{z}^{[l]};\tilde {x}^{[n]},\tilde{z}^{[n]})\rightarrow (\tilde {x}^{[l]},\tilde{z}^{[l]}\oplus \tilde {z}^{[n]};\tilde{x}^{[l]}\oplus \tilde {x}^{[n]},\tilde{z}^{[n]})</math>
###    if ci =P then //Pauli Gate<br/>(a˜[l],˜b[l]) → (a˜[l],a˜[l] ⊕˜b[l])
## If <math>c_i=T</math> gate then <div class="floatright">//Toffoli Gate on <math>l_{th}, n_{th}, o_{th}</math> key bits</br>
### if ci =CNOT with m as target bit and n as control bit then (CNOT)<br/>([l],˜b[l];˜a[n],˜b[n]) ([l],˜b[l] ⊕˜b[n];˜a[l] ⊕ a˜[n],˜b[n])
<div style="background-color: gray; border: solid thin black;title=Functionality Description;">The Toffoli gate application can be deduced as follows:</br><math>TZ^{z^{[l]}}X^{x^{[l]}}Z^{z^{[n]}}X^{x^{[n]}}Z^{z^{[o]}}X^{x^{[o]}}|\psi\rangle</math></br><math>=TZ^{z^{[l]}}X^{x^{[l]}}Z^{z^{[n]}}X^{x^{[n]}}Z^{z^{[o]}}X^{x^{[o]}}T\dagger T|\psi\rangle</math></br><math>=CNOT_{l,o}^{x^{[n]}}CNOT_{n,o}^{x^{[l]}}CZ_{l,n}^{z^{[o]}}Z^{z^{[l]}}X^{x^{[l]}}T|\psi\rangle</math></br><math>=CNOT_{l,o}^{x^{[n]}}CNOT_{n,o}^{x^{[l]}}H_nCNOT_{l,n}^{z^{[o]}}H_{n}Z^{z^{[l]}}X^{x^{[l]}}T|\psi\rangle</math></br><math>=C_{zx}P_{zx}T|\psi\rangle</math>, where <math>C\epsilon \{\text{CNOT,H}\}</math> and <math>P\epsilon\{X,Z\}</math>
## If ci = T gate then //Toffoli Gate on lth,nth,oth key bits
</div>
### The Toffoli gate is applied to the Pauli one time padded state and the state is reduced to combination of Clifford C and Pauli P corrections as follows:<br/>TXa[l]Zb[l]Xa[n]Zb[n]Xa[o]Zb[o] |ψi<br/>=TXa[l]Zb[l]Xa[n]Zb[n]Xa[o]Zb[o]T † T |ψi<br/>= CNOTl,oa[n]CNOTn,oa[l]CZl,nb[o]Xa[l]Zb[l]T |ψi<br/>= CNOTl,oa[n]CNOTn,oa[l]HnCNOTl,nb[o]HnXa[l]Zb[l]T |ψi<br/>= CabPabT |ψi, where C{CNOT,H} and<br/>
:::#The Pauli key encryptions are homomorphically updated  according to <math>P_{zx}</math>.</br> (<math>\tilde {x}^{[l]},\tilde{z}^{[l]};\tilde {x}^{[n]},\tilde{z}^{[n]};\tilde {x}^{[o]},\tilde{z}^{[o]})\rightarrow (\tilde {x}^{[l]},\tilde{z}^{[l]};0,0;0,0)</math>
### The Pauli key encryptions are homomorphically updated according to P_ab
:::# Three encrypted CNOTs are used to correct <math>C^{zx}</math> as follows under <math>\mathrm{AltHE}</math>.</br></br>
### Three encrypted CNOTs are used to correct Cab as follows.
***'''Server's Preparation:'''
#### The server applies encrypted CNOT operation to the two qubit state ZzXx |ψi using the ciphertext ˆc =HE.Convert(c).
::::#Server converts <math>\hat{c} = \mathrm{HE.Convert(c)}</math>.
#### Server generates following superposition sampled over random distribution D for the TCF function pairs (f0 =AltHE.Encpk(),f1) based on the condition f0 ⊕H f1 = cˆ{euqation missing}
::::#Server generates superposition on distribution D: <math>\sum_{\mu\in\{0,1\},r}\sqrt{D(\mu,r)}|\mu,r\rangle</math>
#### Servers generates three register for quantum input, function input, function output and entangles them as follows{equation missing}  
::::#Server entangles above superposition and <math>|\psi\rangle</math> with a third register:<math>\sum_{a,b,\mu\in\{0,1\},r}\alpha_{ab}\sqrt{D(\mu,r)}|a,b\rangle|\mu,r\rangle|f_a(r)\rangle</math>, such that </br><math>f_0=\mathrm{AltHE.Enc}_{pk}()</math>;</br><math>f_1(\mu_1,r_1)=f_0 (\mu_0,r_0)\oplus_H \hat{c}=\mathrm{AltHE.Enc}_{pk}(\mu_0,r_0)\oplus_H \mathrm{AltHE.Enc}_{pk}(s)</math> </br><math>\therefore \mu_0\oplus\mu_1=s</math>
#### Server measures the last register to get a ciphertext y =AltHE.Encpk(µ0,r0), where µ0 ⊕ µ1 = s.
::::#Server measures the last register to get <math>y =\mathrm{AltHE.Enc}(\mu_0,r_0)=\mathrm{AltHE.Enc}_{pk}(\mu_1,r_1)\oplus_H AltHE.Enc_{pk}(s)</math>.</br> The resulting superposition state is:<math>\sum_{a,b\in\{0,1\}}\alpha_{ab}\sqrt{D(\mu_0,r_0)}|a,b\rangle|\mu_a,r_a\rangle|\mathrm{AltHE.Enc}(\mu_0,r_0)\rangle=\sum_{a,b\in\{0,1\}}\alpha_{ab}\sqrt{D(\mu_0,r_0)}|a,b\rangle|\mu_a,r_a\rangle|y\rangle</math>
#### Server performs Hadamard on second register and measures it to get a string d such that first register of input quantum state is reduced to: the following ideal state:<br/> (Zd·((µ0,r0)⊕(µ1,r1)) ⊗ Xµ0)CNOT (1)<br/>where AltHE.Encpk(µ0;r0) = AltHE.Encpk(µ1;r1) ⊕H cˆ and ⊕H is the homomorphic XOR operation.
***'''Encrypted CNOT operation:'''<div style="background-color: gray; border: solid thin black;title=Functionality Description;"><math>\sum_{a,b\in\{0,1\}}\alpha_{ab}CNOT_{a,b}^s|a,b\rangle</math></br><math>=\sum_{a,b\in\{0,1\}}\alpha_{ab}|a,b\oplus a\cdot s\rangle</math></br><math>=\sum_{a,b\in\{0,1\}}\alpha_{ab}|a,b\oplus a\cdot(\mu_0\oplus\mu_1)\rangle</math></br><math>=\sum_{b\in\{0,1\}}\alpha_{0b}|0,b\oplus \mu_0\oplus\mu_0\rangle+\alpha_{1b}|1,b\oplus \mu_0\oplus\mu_1\rangle</math>,  <math>\because q\oplus q=0</math></br><math>=\sum_{b\in\{0,1\}}\alpha_{0b}|0\rangle\otimes X^{\mu_0}|b\oplus \mu_0\rangle+\alpha_{1b}|1\rangle \otimes X^{\mu_0}|b\oplus \mu_1\rangle</math>, <math>\because |q\oplus y\rangle=X^y|q\rangle</math></br><math>=\sum_{a,b\in\{0,1\}}\alpha_{ab}|a\rangle\otimes X^{\mu_0}|b\oplus \mu_a\rangle</math></br><math>=\sum_{a,b\in\{0,1\}}\alpha_{ab}(I\otimes X^{\mu_0})|a,b\oplus \mu_a\rangle</math></br> </div>
#### The server uses pki+1 to compute HE.Encpki+1(ca,b,pki) and HE.Encpki+1(c,y,dˆ ).
::::#Server XORs the second qubit of first register with <math>\mu_a</math> to get:</br><math>\sum_{a,b\in\{0,1\}}\alpha_{ab}\sqrt{D(\mu_0,r_0)}(I\otimes X^{\mu_0})CNOT_{a,b}^s|a,b\rangle\otimes|\mu_a,r_a\rangle|y\rangle</math>
#### The server computes the encryption of a,b under pki+1 by homomorphically running the decryption circuit on inputs HE.Encpki+1(ski) and HE.Encpki+1(ca,b,pki) .
::::#Server performs Hadamard on second register. The resulting superposition state is:</br><math>\sum_{a,b\in\{0,1\}}\alpha_{ab}\sqrt{D(\mu_0,r_0)}(I\otimes X^{\mu_0})CNOT_{ab}^s|a,b\rangle\otimes H^k|\mu_a,r_a\rangle|y\rangle</math></br><math>=\sum_{a,b\in\{0,1\}}\alpha_{ab}\sqrt{D(\mu_0,r_0)}(I\otimes X^{\mu_0})CNOT_{ab}^s|a,b\rangle\otimes\bigg(\sum_{e\in\{0,1\}^k}(-1)^{e\cdot(\mu_a,r_a) }|e\rangle\bigg)|y\rangle</math>, <math>\because H^k|q\rangle=\sum_{e\in\{0,1\}^k}(-1)^{e\cdot q}|e\rangle</math>, where q has k qubits</br>
#### The server homomorphically computes (µ0,r0) and (µ1,r1), using the ciphertexts encrypting tski,ski,c,y,dˆ (all encrypted with HE under public key pki+1). The server then uses this result, along with the ciphertexts encrypting a,b,d, to homomorphically compute ˜b = b + (d · ((µ0,r0) ⊕ (µ1,r1)),0) and ˜a = a + (0,µ0).
::::#Server measures the second register to get d. The resulting superposition is:</br><math>=\sum_{a,b\in\{0,1\}}\alpha_{ab}\sqrt{D(\mu_0,r_0)}(I\otimes X^{\mu_0})CNOT_{ab}^s|a,b\rangle\otimes(-1)^{d\cdot(\mu_a,r_a)}|d\rangle|y\rangle</math></br>
# Server sends updated encryptions of Pauli corrections ˜a,˜b and the classical outcome after measurement of the output state (or Quantum one time padded state in case of quantum output) to Client.
<div style="background-color: gray; border: solid thin black;title=Functionality Description;">
The first register could be equivalently written as:</br><math>(-1)^{d\cdot(\mu_0,r_0)}|0,b\rangle+(-1)^{d\cdot(\mu_1,r_1)}|1,b\rangle</math></br><math>=(-1)^{d\cdot (\mu_0,r_0)}((-1)^{d\cdot((\mu_0,r_0)\oplus(\mu_0,r_0))}|0,b\rangle+(-1)^{d\cdot((\mu_0,r_0)\oplus(\mu_1,r_1))}|1,b\rangle)</math></br><math>=(-1)^{d\cdot (\mu_0,r_0)}((-1)^{0\cdot(d\cdot((\mu_0,r_0)\oplus(\mu_1,r_1))})|0,b\rangle+(-1)^{1\cdot(d\cdot((\mu_0,r_0)\oplus(\mu_1,r_1)))}|1,b\rangle)</math></br><math>=(-1)^{d\cdot (\mu_0,r_0)}((-1)^{a\cdot(d\cdot((\mu_0,r_0)\oplus(\mu_1,r_1))})|a,b\rangle</math></br><math>=(-1)^{d\cdot (\mu_0,r_0)}(Z^{d\cdot((\mu_0,r_0)\oplus(\mu_1,r_1))}|a,b\rangle)</math>, <math>\because Z|q\rangle=(-1)^q|q\rangle</math></br>Thus, the resulting state (upto a global phase) is: </br><math>\approx(Z^{d\cdot((\mu_0,r_0)\oplus(\mu_1,r_1))}\otimes X^{\mu_0})CNOT_{12}^s\sum_{a,b\in\{0,1\}}\alpha_{ab}|a,b\rangle</math></br>
Final superposition at the end of encrypted CNOT operation is:</br> <math>(Z^{d\cdot ((\mu_0,r_0)\oplus (\mu_1,r_1))}\otimes X^{\mu_0})\mathrm{CNOT}_{1,2}^s|\psi_{12}\rangle</math> </br>where <math>(\mu_0,r_0)=(\mu_1,r_1)\oplus_H s</math>, as <math>\oplus_H</math> is the homomorphic XOR operation.
</div>
::::#The server uses <math>pk_{i+1}</math> to recrypt 'c' (previously encrypted using <math>pk_{i}</math>) and encrypt other variables under HE: <math>\mathrm{HE.Enc}_{pk_{i+1}}(c)</math>, <math>\mathrm{HE.Enc}_{pk_{i+1}}(\hat{c},y,d)</math>.
::::#The server computes the encryption of <math>z,x</math> (stored in <math>\tilde{z},\tilde{x}</math>) under <math>pk_{i+1}</math> by performing decryption circuit on <math>\mathrm{HE.Enc}_{pk_{i+1}}(c)</math> using <math>\mathrm{HE.Enc}_{pk_{i+1}}(sk_i)</math> (provided by the evaluation key). Here, c, as stated before is the concatenation of encryption of x, z under <math>pk_{i}</math>, provided by the Client.
::::#The server (homomorphically) computes <math>(\mu_0,r_0)</math> and <math>(\mu_1,r_1)</math>, using <math>\mathrm{HE.Enc}_{pk_{i+1}}(t_{sk_i},sk_i)</math>, provided by the evaluation key <math>\mathrm{evk}_i</math> encrypted under <math>pk_{i+1}</math>, and <math>\mathrm{HE.Enc}_{pk_{i+1}}(\hat{c},y,d)</math>, from the previous step.
::::#The server then uses this results of the last three steps, to (homomorphically) update Pauli encryptions for encrypted <math>CNOT^s_{l,n}</math>: </br>(<math>\tilde {x}^{[l]},\tilde{z}^{[l]};\tilde {x}^{[n]},\tilde{z}^{[n]})\rightarrow (\tilde {x}^{[l]},\tilde{z}^{[l]}+d\cdot ((\mu_0,r_0)\oplus (\mu_1,r_1);\tilde {x}^{[n]}+\mu_0,\tilde{z}^{[n]})</math></br>
3. Server sends updated encryptions of Pauli corrections <math>\tilde{x},\tilde{z}</math> and the classical outcome after measurement of the output state to Client.


=== '''Stage 3''' Client’s Output Correction ===
=== '''Stage 3''' Client’s Output Correction ===
   
   
*'''Input:''' Classical output state, l {0,1}λ (or Quantum One time padded state in case of Quantum output), encrypted Pauli corrections ˜a,˜b
*Input: Classical output state (<math>l\in\{0,1\}^{\lambda}</math>), encrypted Pauli corrections (<math>\tilde{z},\tilde{x}</math>)
*'''Output:''' Decrypted classical message x ⊕ m (or final quantum output of computation ZzXx |ψi)
*Output: Decrypted classical message (<math>l\oplus x</math>)
''Decryption (FHE.Decsk)''
**'''Decryption (FHE.Dec<math>_{sk}</math>)'''
# Client decrypts ˜a,˜b using skL+1 to obtain a,b.
# Client decrypts <math>\tilde{z},\tilde{x}</math> using <math>sk_{L+1}</math> to obtain <math>z,x</math>.  
# She then uses the decrypted Pauli corrections to get the output XaZb |li, which can be represented as a ⊕ l.<br/>She operates XaZb on quantum output to get C|ψi, in case of quantum output.
# She then uses the decrypted Pauli corrections to get the correct output <math>l\oplus x</math>.</br>
 
==Further Information==
In case of Quantum Input, the client additionally sends quantum one tie padded input state. In case of quantum output the Server instead of classical outcome sends the final quantum one time padded output state (operated by the required circuit). Client gets the output by using the updated encryption sent by the server to perform Pauli corrections on the output state. This protocol is first and only protocol currently, to use a classical functionality to solve a quantum task. It provides computationally security. Verification of this protocol is still an open question.
 
<div style='text-align: right;'>''*contributed by Shraddha Singh''</div>

Latest revision as of 15:35, 16 October 2019

The example protocol achieves the functionality of Delegated Quantum Computation by a method which involves fully classical offline and no quantum communication. It uses only classical 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 unitary operation (any quantum gate) for required computation. Quantum offline communication would be required if Client’s input and output is quantum.

Tags: Two Party, Quantum Functionality, Universal Task, Secure Client- Server Delegated Quantum Computation, Prepare and Send Quantum FHE, Classical Offline Communication, Superposition, Trapdoor Claw-Free Functions, Learning With Errors, Encrypted CNOT Operation.

Assumptions[edit]

  • This protocol is secure against honest but curious adversary setting.
  • HE is a classical leveled fully homomorphic encryption scheme which is quantum capable for given depth of one layer of circuit, (See Notations below).
  • A 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 learning with errors assumption.

Outline[edit]

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) 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 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 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. 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.
The preparation stage incorporates,

  • Key Generation: Client generates 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.

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.

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 Pseudo Code below.

  1. 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 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).
  2. 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.
  3. 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
  4. 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.
  • 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 () evaluation key used. This is the public key. Hence, Client uses 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.

Properties[edit]

  • Quantum Capable A classical HE is quantum capable i.e. can perform quantum computation efficiently if there exists AltHE which can execute natural XOR operations.
  • Indistinguishability under Chosen Plaintext Attacks by adversary(IND-CPA) The presented classical FHE scheme is CPA secure i.e. it is not possible for any polynomial time adversary to distinguish between the encrypted classical message bits 0 and 1, by learning with errors.
  • Compactness This protocol is compact i.e. decryption does not depend on the complexity of the quantum circuit.
  • Correctness Correctness is implied from the correctness of encrypted CNOT operation.
  • Circuit Privacy This protocol is not circuit private as both Client and Server know the quantum circuit used for performing the computation.
  • Full Homomorphism This protocol is fully homomorphic i.e. Server can operate any quantum circuit using this protocol.
  • Circular Security This protocol has a stronger notion of circular security where not only the secret key but also the trapdoor functions are encrypted when provided to the Server.

Notation[edit]

  • : classical data of client's required quantum input states
  • : security parameter
  • : security parameter
  • : encrypted pad key
  • : concatenated pad key elements
  • Encryption of s using public key via classical HE encryption step.
  • : converted c using classical HE in order to use it with
  • : bit of encrypted pad key
  • : depth of a layer of circuit where each layer contains Clifford gates and Toffoli gates
  • : depth of the circuit (no. of layers in the circuit)
  • : homomorphic key set generated from HE.KeyGen(). Public key for encryption, secret key for decryption, evaluation function key, trapdoor information required for randomness recovery from secret texts.
  • : measurement outcome of third register
  • : random claw for pair, for given y
  • : measurement outcome of the second register

Requirements[edit]

  • Network Stage: Quantum Memory
  • Required Network Parameters:
    • , which measures the error due to noisy operations.
    • Number of communication rounds
    • Circuit depth
    • Number of physical qubits used
  • The concerned protocol requires classical HE scheme.
  • Classical offline communication links
  • Communication can be performed over a classical network with only one quantum node (in case of classical input and output).
  • The functions used must be trapdoor claw-free(TCF) such that one it is not possible to find a triple such that

Knowledge Graph[edit]

Protocol Description[edit]

  • Boxed texts are not part of the code but contain proofs used in various steps, illustrated for a better understanding of the protocol.

Stage 1 Client’s Preparation[edit]

  • Input: , classical message
  • Output: Homomorphic key sets , encrypted pad key , One time Padded message ()
    • Key Generation (FHE.KeyGen())
  1. For ,
  2. Client generates homomorphic key set, HE.Keygen().
    The public key is and the secret key is .
    The evaluation key consists of HE.Enc, HE.Enc) for .
    • Encryption (FHE.Enc))
  1. Client chooses pad key for each message bit .
  2. She one time pads the message m,
    //z is used for quantum input where is quantum input.
  3. She then encrypts the pad key. HE.Enc
  4. She sends the encrypted message and pad key to the Server with the evaluation keys.

Stage 2 Server’s Computation[edit]

  • Input: , pad key elements concatenation (), encryption of s under HE (), one time padded message ()
  • Output: Updated encryption of pad key and final classical outcome after performing the circuit.
    • Circuit Evaluation (FHE.Eval())
  1. Server creates a quantum superposition state for encrypted input : , where
    represents the two qubits superposition state for classical message m,
    represents quantum one time pad.
  2. For all i, Server applies gate on qubit l and the bits of pad key are updated to as follows.
    1. If , a Clifford gate then
      //()
      1. if H then
        //Hadamard Gate

        //Hadamard tranforms X gate into Z and Z into X
      2. if P then
        //Pauli Gate

      3. if with m as target bit and n as control bit then
        //CNOT

        (
    2. If gate then
      //Toffoli Gate on key bits
The Toffoli gate application can be deduced as follows:




, where and
  1. The Pauli key encryptions are homomorphically updated according to .
    (
  2. Three encrypted CNOTs are used to correct as follows under .

      • Server's Preparation:
  1. Server converts .
  2. Server generates superposition on distribution D:
  3. Server entangles above superposition and with a third register:, such that
    ;

  4. Server measures the last register to get .
    The resulting superposition state is:
      • Encrypted CNOT operation:



        ,
        ,


  1. Server XORs the second qubit of first register with to get:
  2. Server performs Hadamard on second register. The resulting superposition state is:

    , , where q has k qubits
  3. Server measures the second register to get d. The resulting superposition is:

The first register could be equivalently written as:




,
Thus, the resulting state (upto a global phase) is:

Final superposition at the end of encrypted CNOT operation is:

where , as is the homomorphic XOR operation.

  1. The server uses to recrypt 'c' (previously encrypted using ) and encrypt other variables under HE: , .
  2. The server computes the encryption of (stored in ) under by performing decryption circuit on using (provided by the evaluation key). Here, c, as stated before is the concatenation of encryption of x, z under , provided by the Client.
  3. The server (homomorphically) computes and , using , provided by the evaluation key encrypted under , and , from the previous step.
  4. The server then uses this results of the last three steps, to (homomorphically) update Pauli encryptions for encrypted :
    (

3. Server sends updated encryptions of Pauli corrections and the classical outcome after measurement of the output state to Client.

Stage 3 Client’s Output Correction[edit]

  • Input: Classical output state (), encrypted Pauli corrections ()
  • Output: Decrypted classical message ()
    • Decryption (FHE.Dec)
  1. Client decrypts using to obtain .
  2. She then uses the decrypted Pauli corrections to get the correct output .

Further Information[edit]

In case of Quantum Input, the client additionally sends quantum one tie padded input state. In case of quantum output the Server instead of classical outcome sends the final quantum one time padded output state (operated by the required circuit). Client gets the output by using the updated encryption sent by the server to perform Pauli corrections on the output state. This protocol is first and only protocol currently, to use a classical functionality to solve a quantum task. It provides computationally security. Verification of this protocol is still an open question.

*contributed by Shraddha Singh