Editing Prepare-and-Send Quantum Fully Homomorphic Encryption (section)

==Protocol Description==
===Stage 1 Client’s Preparation===
 
'''Key Generation (QFHE.KeyGen(1k,1L))'''
*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
#	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.
# She sets the public key to be the tuple <math>(pk_i)_{i = 0}^{L}</math>.
# She sets the secret key to be the tuple <math>(sk_i)_{i = 0}^{L}</math>.
# 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 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>
 
'''Encryption(QFHE.Enc())'''
*Input: Quantum Input state density matrix (<math>\rho</math>) (say composed of n single qubit states, <math>\sigma</math>)
*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>

#	For i=1 to n
## Client chooses pad keys a,b <math>\epsilon_R\{0,1\}</math>
## 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 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 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  (<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 (<math>\text{QFHE.GenGadget}_{pk_{i+1}}(sk_i)</math>)'''
# 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 <math>2m</math> pairs <math>\epsilon \{a_1, a_2,....,a_{4m}\}</math> using sk
## If <math>(sk=0)</math> then <math>\{(a_1,a_2),(a_2,a_3),...,(a_{4m-1},a_{4m})\}</math> 
## If <math>(sk=1)</math> then <math>\{(a_1,a_3),(a_2,a_4),...,(a_{4m-2},a_{4m})\}</math> 
# For j=1 to 2m, 
## Choose p[j] <math>\epsilon_R \{0,1\}</math>
## Perform Bell Measurement on <math>j^{th}</math> pair with an extra <math>(P^\dagger)^p</math> operation, get outcomes (x[j],z[j])
## Thus, new EPR pairs are
### If <math>(sk=0)</math> then <math>\{(b_1,b_2),(b_2,b_3),...,(b_{4m-1},b_{4m})\}</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===
'''Circuit's 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>
*'''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>
Let the Circuit be denoted by C and the gates be <math>c_i</math>
# 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. 
## 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>)
### 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 <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 <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 <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>
###'''Generate Measurement''' M<math>\leftarrow</math> QFHE.GenMeasurement(<math>\tilde {a}^{[m]},\Gamma_{pk_{j+1}}(sk_j),evk_j)</math>
###'''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>
### 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>
### 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 sends the updated encryption and QOTP output state to Client.

===Stage 3 Client’s Correction===
'''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>)
*'''Output:''' Final outcome of the computation C<math>\rho</math>C<math>^\dagger=\rho'</math>
# 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 pad key and operates <math>X^{a'^{[i]}}Z^{b'^{[i]}}</math> on single qubits i separately just like encryption. 
##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 <math>\rho'</math>, final outcome of the computation.