Quantum Protocol Zoo

Editing Prepare-and-Send Quantum Fully Homomorphic Encryption

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then publish the changes below to finish undoing the edit.

Latest revision Your text
Line 12: Line 12:
==Outline==
==Outline==
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]] 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
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]] 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 (QFHE.KeyGen())'''  
*'''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 [[Glossary#EPR pairs|EPR pairs]] (maximally entangled qubits). The client starts with 4m such pairs. Performs pairwise [[Glosssary#Bell State Measurement|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 [[Glossary#Unitary Operations|Pauli X, Z]] corrections due to measurement. These corrections are determined by Client’s measurement outcomes according to [[one pad key]]. 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 [[Glossary#EPR pairs|EPR pairs]] (maximally entangled qubits). The client starts with 4m such pairs. Performs pairwise [[Glosssary#Bell State Measurement|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 [[Glossary#Unitary Operations|Pauli X, Z]] corrections due to measurement. These corrections are determined by Client’s measurement outcomes according to [[one pad key]]. 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 (QFHE.Enc())''' This step is used to encrypt the quantum input into a quantum cipher-text (secret text) 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.
*'''Encryption''' This step is used to encrypt the quantum input into a quantum cipher-text (secret text) 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 (QFHE.Eval())''' 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.
*'''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.
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 [[Glossary#Unitary Operations|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 [[Glossary#Unitary Operations|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 40: Line 40:
*Server should be able to store entangled states, perform all Clifford and T gates.
*Server should be able to store entangled states, perform all Clifford and T gates.


==Knowledge Graph==
[[File:Prepare-and-Send Quantum Fully Homomorphic Encryption.png|center|Prepare-and-Send Quantum Fully Homomorphic Encryption]]


{{graph}}
==Properties ==


==Properties ==
===Security Claim/ Theorems===
* ''Indistinguishability under Chosen Plaintext Attacks by an adversary with quantum computational powers(q-IND-CPA).'' If FHE is q-IND-CPA secure then this protocol is q-IND-CPA secure. It means that an adversary cannot distinguish between ciphertext from a message and a ciphertext from an arbitrary quantum state such as <math>|0\rangle \langle 0|</math>
* ''Indistinguishability under Chosen Plaintext Attacks by an adversary with quantum computational powers(q-IND-CPA).'' If FHE is q-IND-CPA secure then this protocol is q-IND-CPA secure. It means that an adversary cannot distinguish between ciphertext from a message and a ciphertext from an arbitrary quantum state such as |0ih0|
* ''Correctness.'' This protocol is perfectly correct such that,<br/>
* ''Correctness.'' This protocol is perfectly correct such that,<br/>
<math>Pr[QFHE.Dec_{s_k}(QFHE.Eval^C_{evk}(HE.Enc_{p_k}(x)))\neq C(x)] \le \eta(k)</math><br/>
Pr[QFHE.Decsk(QFHE.EvalevkC (HE.Encpk(x))) 6= C(x)] ≤ η(k)<br/>
, where <math>\eta_k</math> is a negligible function.Note that, negligible function $\eta(n)$ is a function such that for every positive integer d, <math>\eta(n) < 1/n^d</math>, for big enough n. This means that if the protocol is followed it results in the same output as when the circuit is operated on the input states directly with overwhelming probability.
, where ηk is a negligible function. This means that if the protocol is followed it results in the same output as when the circuit is operated on the input states directly with overwhelming probability.
* ''Compactness.'' If HE is compact then this protocol is compact. The complexity of applying QFHE.Dec on the results of QFHE.Eval is at most p(k), where p(k) is a polynomial dependent only on the security parameter k. This implies that decryption is independent of the size of the quantum circuit for evaluation.
* ''Compactness.'' If HE is compact then this protocol is compact. The complexity of applying QFHE.Dec on the results of QFHE.Eval is at most p(k), where p(k) is a polynomial dependent only on the security parameter k. This implies that decryption is independent of the size of the quantum circuit for evaluation.
* ''Circuit Privacy.'' This protocol is not circuit private as it does not guarantee that the client cannot gain information about the circuit evaluated i.e. the circuit is not private to one party and unknown to another. It can make the circuit private to the evaluator (Server) and hidden from the Client apart from the necessary leakage the output states gives if one uses circuit private HE for the protocol.  
* ''Circuit Privacy.'' This protocol is not circuit private as it does not guarantee that the client cannot gain information about the circuit evaluated i.e. the circuit is not private to one party and unknown to another. It can make the circuit private to the evaluator (Server) and hidden from the Client apart from the necessary leakage the output states gives if one uses circuit private HE for the protocol.  
Line 65: Line 65:
* p, location of inverse phase gate
* p, location of inverse phase gate
* x,z measurement outcome sets of Client for her Bell Pair measurements.
* x,z measurement outcome sets of Client for her Bell Pair measurements.
* <math>x',z'</math> measurement outcome sets of Server for his Gadget measurement.
* x’,z’ measurement outcome sets of Server for his Gadget measurement.
* <math>\tilde{x}^{[i]}</math>, resulting ciphertext one gets for an input <math>i^{th}</math> element of array x or <math>i^{th}</math> bit of key x after the Encrypting it with <math>i^{th}</math> of public key string, pk.
* x˜[i], resulting ciphertext one gets for an input ith element of array x or ith bit of key x after the Encrypting it with ith of public key string, pk.


==Protocol Description==
== Pseudocode==
===Stage 1 Client’s Preparation===
===Stage 1 Client’s Preparation===
   
   
'''Key Generation (QFHE.KeyGen(1k,1L))'''
'''Key Generation (QFHE.KeyGen(1k,1L))'''
*Input: No. of T gates (L), Security Parameter (k),
*Input: No. of T gates (L), Security Parameter (k),
*Output: L+1 evaluation keys (encrypted Gadgets, classical HE evaluation key), L+1 public keys, L+1 secret keys
*Output: L+1 evaluation keys (encrypted Gadgets, classical HE evaluation key), L+1 public keys, L+1 secret keys
# For i = 0 to L
# For i = 0 to L
## Client executes <math>(pk_i, sk_i, evk_i) \leftarrow \text{HE.KeyGen}(1^{\kappa})</math> to obtain <math>L+1</math> independent classical homomorphic key sets.
##Client executes (pki,ski,evki) ← HE.KeyGen(1κ) to obtain L + 1 independent classical homomorphic key sets.
# She sets the public key to be the tuple <math>(pk_i)_{i = 0}^{L}</math>.
# She sets the public key to be the tuple ( .
# She sets the secret key to be the tuple <math>(sk_i)_{i = 0}^{L}</math>.
# She sets the secret key to be the tuple ( .
# For i = 0 to L-1
# For i = 0 to L − 1
## Client runs the procedure <math>\text{QFHE.GenGadget}_{pk_{i+1}}(sk_i)</math> to create the gadget <math>\Gamma_{pk_{i+1}}(sk_i)</math>.  
##Client runs the procedure QFHE.GenGadgetpki+1(ski) to create the gadget Γpki+1(ski).
# Client sets the evaluation key to be the set of all gadgets created in the previous step (including their encrypted classical information), plus the tuple <math>(evk_i)_{i=0}^L</math>. The resulting evaluation key is the classical-quantum (CQ) state</br><math>\bigotimes_{i = 0}^{L-1}\Big(\Gamma _{pk_{i+1}}(sk_i)\otimes |evk_i\rangle \langle evk_i|)</math>
# Client sets the evaluation key to be the set of all gadgets created in the previous step (including their encrypted classical information), plus the tuple ( . The resulting evaluation key is the classical-quantum (CQ) state {missing math}
   
   
'''Encryption(QFHE.Enc())'''
'''Encryption(QFHE.Enc())'''
*Input: Quantum Input state density matrix (<math>\rho</math>) (say composed of n single qubit states, <math>\sigma</math>)
*Input: Quantum Input state density matrix (ρ) (say composed of n single qubit states, σ)
*Output: Encrypted pad keys:<math>\{\tilde{a}^{[0]}...\tilde{a}^{[n]}</math>,<math>\tilde{b}^{[i]}...\tilde{b}^{[n]}\}</math>; QOTP state: <math>X^{a^{[1]}}Z^{b^{[1]}}\otimes.....\otimes X^{a^{[n]}}Z^{b^{[n]}}\rho Z^{b^{[1]}}X^{a^{[1]}}\otimes.....\otimes X^{a^{[n]}}Z^{b^{[n]}}</math>
*Output: Encrypted pad keys: {a˜[0]...a˜[n], ˜b[i]...˜b[n]}; QOTP state: Xa[1]Zb[1]⊗.....⊗Xa[n]Zb[n]ρZb[1]Xa[1]⊗ ..... ⊗ Xa[n]Zb[n]
 
# For i=1 to n
# For i=1 to n
## Client chooses pad keys a,b <math>\epsilon_R\{0,1\}</math>
## Client chooses pad keys a,b  
## She quantum one time pads the single qubit by applying $X^aZ^b$ on the single qubit state. <math>X^aZ^b\sigma Z^bX^a\leftarrow\sigma</math>
## She quantum one time pads the single qubit by applying XaZb on the single qubit state. XaZbσZbXa ← σ
## She encrypts the pad keys using one bit for each of a and b from the public key string <math>pk_0</math> using HE.Enc. (<math>\tilde{a}^{[i]},\tilde{b}^{[i]}</math>)=(HE.Enc<math>_{pk_0^{[i]}}(a^{[i]}</math>),HE.Enc<math>_{pk_0^{[i]}}(b^{[i]}))\leftarrow</math> (a,b)
## She encrypts the pad keys using one bit for each of a and b from the public key string pk0 using HE.Enc. (˜  )=(HE.Enc ),HE.Enc  
## She apprehends encrypted pad keys to the one time padded quantum state to obtain CQ state,  
## She apprehends encrypted pad keys to the one time padded quantum state to obtain CQ state,
<math>\sum_{a,b\epsilon\{0,1\}}\frac{1}{4}\rho(HE.Enc_{pk_0^{[i]}}(a^{[i]}),HE.Enc_{pk_0^{[i]}}(b^{[i]}))\otimes X^aZ^b\sigma Z^bX^a</math>
# Client sends encryptions (˜a[i],˜b[i]) and the quantum one time padded (QOTP) state Xa[1]Zb[1] ⊗ ..... ⊗ Xa[n]Zb[n]ρZb[1]Xa[1] ⊗ ..... ⊗ Xa[n]Zb[n], for all i to the Server with the evaluation keys and public keys.
#Client sends encryptions (<math>\tilde{a}^{[i]},\tilde{b}^{[i]}</math>) and the quantum one time padded (QOTP) state<math> X^{a^{[1]}}Z^{b^{[1]}}\otimes.....\otimes X^{a^{[n]}}Z^{b^{[n]}}\rho Z^{b^{[1]}}X^{a^{[1]}}\otimes.....\otimes X^{a^{[n]}}Z^{b^{[n]}} \forall i</math>,  to the Server with the evaluation keys and public keys.
'''Gadget Construction (QFHE.GenGadgetpki+1(ski))'''
'''Gadget Construction (<math>\text{QFHE.GenGadget}_{pk_{i+1}}(sk_i)</math>)'''
# Generate 4m EPR pairs (  
# Generate <math>4m</math> EPR pairs (<math>|\phi\rangle=\frac{1}{\sqrt{2}}(00+11))</math>, <math>\{(a_1,b_1),...,(a_{4m},b_{4m})\}</math>
# Choose 2m pairs using sk
# Choose <math>2m</math> pairs <math>\epsilon \{a_1, a_2,....,a_{4m}\}</math> using sk
## If (sk = 0) then {(a1,a2),(a2,a3),...,(a4m−1,a4m)} ii. If (sk = 1) then {(a1,a3),(a2,a4),...,(a4m−2,a4m)}
## If <math>(sk=0)</math> then <math>\{(a_1,a_2),(a_2,a_3),...,(a_{4m-1},a_{4m})\}</math>
# For j=1 to 2m,
## If <math>(sk=1)</math> then <math>\{(a_1,a_3),(a_2,a_4),...,(a_{4m-2},a_{4m})\}</math>
## Choose p[j]  
# For j=1 to 2m,  
## Perform Bell Measurement on jth pair with an extra (P†)p operation, get outcomes (x[j],z[j])
## Choose p[j] <math>\epsilon_R \{0,1\}</math>
## Thus, new EPR pairs are{missing math}<br/>If (sk = 0) then {(b1,b2),(b2,b3),...,(b4m−1,b4m)}<br/>If (sk = 1) then {(b1,b3),(b2,b4),...,(b4m−2,b4m)}<br/>Denote the 2m entangled pairs be denoted by {(s1,t1),(s2,t2),...,(s2m,t2m)}, such that<br/>
## Perform Bell Measurement on <math>j^{th}</math> pair with an extra <math>(P^\dagger)^p</math> operation, get outcomes (x[j],z[j])
###The classical information of gadget be g(sk)= ({(s1,t1),(s2,t2),...,(s2m,t2m),p,sk}.<br/>
## Thus, new EPR pairs are
###The quantum state of gadget can be written as {missing math}  
### If <math>(sk=0)</math> then <math>\{(b_1,b_2),(b_2,b_3),...,(b_{4m-1},b_{4m})\}</math>
# Encrypt (x[j],z[j]), p[j] for all j and sk using pki+1. Resulting Gadget is the classical-quantum (CQ) state,{missing math}
### If <math>(sk=1)</math> then <math>\{(b_1,b_3),(b_2,b_4),...,(b_{4m-2},b_{4m})\}</math>
## Denote the <math>2m</math> entangled pairs be denoted by <math>\{(s_1,t_1),(s_2,t_2),...,(s_{2m},t_{2m})\}</math>, such that
## The classical information of gadget be g(sk)<math>=(\{(s_1,t_1),(s_2,t_2),...,(s_{2m},t_{2m}),p,sk\}</math>.
## The quantum state of gadget can be written as <math>\gamma_{x,z}(g(sk))=\pi_{j=1}^mX^{x[i]}Z^{z[i]}(P^\dagger){p[i]}|\phi\rangle\langle\phi|_{s_jt_j}(P^\dagger){p[i]}Z^{z[i]}X^{x[i]}</math>
# Encrypt (x[j],z[j]), p[j] for all j and sk using <math>pk_{i+1}</math>. Resulting Gadget is the classical-quantum (CQ) state,
<math>\Gamma_{pk_{i+1}}(sk_i)=\rho(HE.Enc_{pk_{i+1}}(g(sk))\otimes \frac{1}{2^{2m}}\sum_{x,z\epsilon\{0,1\}^m}\rho(HE.Enc_{pk_{i+1}}(x,z)\otimes \gamma_{x,z}(g(sk))</math>


=== Stage 2 Server’s Computation===
=== Stage 2 Server’s Computation===
'''Circuit's Evaluation (QFHE.Eval())'''
'''Circuit Evaluation (QFHE.Eval())'''
*'''Input:''' public key tuple <math>(pk_i)_{i = 0}^{L}</math>, Evaluation key tuple, Encrypted Pad key (<math>\{\tilde{a}^{[0]}...\tilde{a}^{[n]}</math>, <math>\tilde{b}^{[i]}...\tilde{b}^{[n]}\}</math>), QOTP Input State (<math> X^{a^{[1]}}Z^{b^{[1]}}\otimes.....\otimes X^{a^{[n]}}Z^{b^{[n]}}\rho Z^{b^{[1]}}X^{a^{[1]}}\otimes.....\otimes X^{a^{[n]}}Z^{b^{[n]}}</math>)</br>
*Input: public key tuple ( , Evaluation key tuple, Encrypted Pad key ({a˜[0]...a˜[n], ˜b[i]...˜b[n]}), QOTP Input State (Xa[1]Zb[1] ⊗ ..... ⊗ Xa[n]Zb[n]ρZb[1]Xa[1] ⊗ ..... ⊗ Xa[n]Zb[n])
*'''Output:''' QOTP Circuit Output State (<math> X^{a'^{[1]}}Z^{b'^{[1]}}\otimes.....\otimes X^{a'^{[k]}}Z^{b'^{[k]}}\rho' Z^{b'^{[1]}}X^{a'^{[1]}}\otimes.....\otimes X^{a'^{[k]}}Z^{b'^{[k]}}</math>), Corresponding Encrypted Pad key (<math>\tilde{a'},\tilde{b'}</math>)=(HE.Eval<math>_{evk_L}^\text{C}(\tilde{a}</math>),HE.Eval<math>_{evk_L}^\text{C}(\tilde{b}</math>))</br></br>
*Output: QOTP Circuit Output State (Xa0[1]Zb0[1]⊗.....⊗Xa0[k]Zb0[k]ρ0Zb0[1]Xa0[1]⊗.....⊗Xa0[k]Zb0[k]), Corresponding Encrypted Pad key (a˜0,b˜0)=(HE.EvalCevkL(a˜),HE.EvalCevkL(˜b))
Let the Circuit be denoted by C and the gates be <math>c_i</math>
Let the Circuit be denoted by C and the gates be ci
# For all i, <math>c_i</math> gate is applied on qubit m and the <math>m_{th}</math> bits of pad key <math>(\tilde {a}^{[m]},\tilde{b}^{[m]})</math> are updated to <math>(\tilde {a}'^{[m]},\tilde{b}'^{[m]})</math> as follows.  
# For all i, ci gate is applied on qubit m and the mth bits of pad key (˜a[m],˜b[m]) are updated to
## If <math>c_i=\{P,H,CNOT\}</math>, a Clifford gate then <math>c_iX^{a^{[m]}}Z^{b^{[m]}}\psi=X^{a'^{[m]}}Z^{b'^{[m]}}c_i\psi</math>)
(a˜0[m],˜b0[m]) as follows.
### if <math>c_i=</math>H then: <math>(\tilde {a}^{[m]},\tilde{b}^{[m]})\rightarrow (\tilde{b}^{[m]},\tilde{a}^{[m]})</math> (Hadamard tranforms X gate into Z and Z into X)
## If ci = {P,H,CNOT}, a Clifford gate then (ciXa[m]Zb[m]ψ = Xa0[m]Zb0[m]ciψ)
### if <math>c_i=</math>P then: <math>(\tilde {a}^{[m]},\tilde{b}^{[m]})\rightarrow (\tilde{a}^{[m]},\tilde{a}^{[m]}\oplus\tilde{b}^{[m]})</math>
### if ci =H then{missing math} (Hadamard tranforms X gate into Z and Z into X)
### if <math>c_i=</math>CNOT with m as target bit and n as control bit then: <math>(\tilde {a}^{[m]},\tilde{b}^{[m]};\tilde {a}^{[n]},\tilde{b}^{[n]})\rightarrow (\tilde {a}^{[m]},\tilde{b}^{[m]}\oplus \tilde {b}^{[n]};\tilde{a}^{[m]}\oplus \tilde {a}^{[n]},\tilde{b}^{[n]})</math>
### if ci =P then<br/>{missing math}  
## If <math>c_i=T_j</math> gate then: <math> (T_jX^{a^{[m]}}Z^{b^{[m]}}\psi=P^{a^{[m]}}X^{a^{[m]}}Z^{b^{[m]}}T_j\psi)</math>
###if ci =CNOT with m as target bit and n as control bit then (CNOT)<br/>(a˜[m],˜b[m];˜a[n],˜b[n]) → (a˜[m],˜b[m] ⊕˜b[n];˜a[m] ⊕a˜[n],˜b[n])
###'''Generate Measurement''' M<math>\leftarrow</math> QFHE.GenMeasurement(<math>\tilde {a}^{[m]},\Gamma_{pk_{j+1}}(sk_j),evk_j)</math>
## If ci = Tj gate then (TjXa[m]Zb[m]ψ = Pa[m]Xa[m]Zb[m]Tjψ)
###'''Gadget Correction'''<math>(X^{a'^{[m]}}Z^{b'^{[m]}}T_j)\psi\leftarrow</math> QFHE.Measurement(M, <math>P^{a^{[m]}}X^{a^{[m]}}Z^{b^{[m]}}T_j\psi)</math>
### Generate Measurement<br/>M← QFHE.GenMeasurement(˜a[m],Γpkj+1(skj),evkj)<br/>
### Server gets measurement outcome x',z'
### Gadget Correction<br/>(Xa0[m]Zb0[m]Tj)ψ ← QFHE.Measurement(M, Pa[m]Xa[m]Zb[m]Tjψ);<br/> Server gets measurement outcome x’,z’
###'''Recryption''' Server recrypts one-pad key using pk<math>_{k+1}</math> (<math>\tilde {a''}^{[m]},\tilde{b''}^{[m]})\leftarrow</math> QFHE.Rec<math>_{pk_{k+1}}(\tilde {a}^{[m]},\tilde{b}^{[m]})</math>
### Recryption Server recrypts one-pad key using pkk+1<br/>QFHE.Recpkk+1(a˜[m],˜b[m]).<br/>
### Server updates the recrypted key using x,z and x',z'. (<math>\tilde {a'}^{[m]},\tilde{b'}^{[m]})\leftarrow (\tilde {a''}^{[m]},\tilde{b''}^{[m]}</math>)
##Server updates the recrypted key using x,z and x’,z’.
## Server sends the updated encryption and QOTP output state to Client.
## Server sends the updated encryption and QOTP output state to Client.
 
===Stage 3 Client’s Correction===
===Stage 3 Client’s Correction===
'''Decryption (QFHE.Dec())
'''Decryption (QFHE.Dec())
*'''Input:''' QOTP Circuit Output State (<math> X^{a'^{[1]}}Z^{b'^{[1]}}\otimes.....\otimes X^{a'^{[k]}}Z^{b'^{[k]}}\rho' Z^{b'^{[1]}}X^{a'^{[1]}}\otimes.....\otimes X^{a'^{[k]}}Z^{b'^{[k]}}</math>), Corresponding Encrypted Pad key (<math>\tilde{a'},\tilde{b'}</math>)
*Input: QOTP Circuit Output State (Xa0[1]Zb0[1] ⊗ ..... ⊗ Xa0[k]Zb0[k]ρ0Zb0[1]Xa0[1] ⊗ ..... ⊗Xa0[k]Zb0[k]), Corresponding Encrypted Pad key (a˜0,b˜0)
*'''Output:''' Final outcome of the computation C<math>\rho</math>C<math>^\dagger=\rho'</math>
*Output: Final outcome of the computation CρC† = ρ0 (a) Client uses skL to restore the pad key from sent encryption. (a0[i],b0[i])=(HE.Dec [i](a0[i]),HE.Dec [i](b0[i]))
# Client uses <math>sk_L</math> to restore the pad key from sent encryption: (<math>{a'}^{[i]},{b'}^{[i]}</math>)=(HE.Dec<math>_{sk_L^{[i]}}(a'^{[i]}</math>),HE.Dec<math>_{pk_L^{[i]}}(b'^{[i]}))</math>
# Client uses skL to restore the pad key from sen encryption
# Client uses pad key and operates <math>X^{a'^{[i]}}Z^{b'^{[i]}}</math> on single qubits i separately just like encryption.  
# Client uses pad key and operates Xa Zb on single qubits i separately just like encryption.<br/>Let single qubit representation of the output state be Xa0[i]Zb0[i]σ0Zb0[i]Xa0[i], then operation of Pauli X,Z gates as above yields σ0
##Let single qubit representation of the output state be <math>X^{a'^{[i]}}Z^{b'^{[i]}}\sigma' Z^{b'^{[i]}}X^{a'^{[i]}}</math>, then operation of Pauli X,Z gates as above yields <math>\sigma'</math>
# Client repeats this for all single qubits and hence gets the quantum state ρ0, final outcome of the computation.
# Client repeats this for all single qubits and hence gets the quantum state <math>\rho'</math>, final outcome of the computation.


==Further Information==
==Further Information==


<div style='text-align: right;'>''*contributed by Shraddha Singh''</div>
<div style='text-align: right;'>''*contributed by Shraddha Singh''</div>
Please note that all contributions to Quantum Protocol Zoo may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see Quantum Protocol Zoo:Copyrights for details). Do not submit copyrighted work without permission!

To protect the wiki against automated edit spam, we kindly ask you to solve the following CAPTCHA:

Cancel Editing help (opens in new window)

Template used on this page:

Retrieved from "https://wiki.veriqloud.fr/index.php?title=Prepare-and-Send_Quantum_Fully_Homomorphic_Encryption"