Editing Classical Fully Homomorphic Encryption for Quantum Circuits (section)

==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===
 
*Input: <math>k, L, L_c</math>, classical message <math>m</math>
*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(<math>1^{\lambda}, 1^L</math>))'''
#	For <math>1\leq i\leq L + 1</math>, 
#	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>.
**'''Encryption (FHE.Enc<math>_{pk}(m)</math>))'''
#Client chooses pad key for each message bit <math>z,x\in\{0,1\}^{\lambda}</math>.
#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 the pad key. HE.Enc<math>_{pk_1}(z,x)</math>
# She sends the encrypted message and pad key to the Server with the evaluation keys.

=== '''Stage 2''' Server’s Computation ===
 
*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 <math>\tilde{z},\tilde{x}</math> and final classical outcome after performing the circuit.
**'''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>
# 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. 
##	 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>
###	 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 <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 <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 <math>c_i=T</math> gate then <div class="floatright">//Toffoli Gate on <math>l_{th}, n_{th}, o_{th}</math> key bits</br>
<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>
</div>
:::#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>
:::# Three encrypted CNOTs are used to correct <math>C^{zx}</math> as follows under <math>\mathrm{AltHE}</math>.</br></br>
***'''Server's Preparation:'''
::::#Server converts <math>\hat{c} = \mathrm{HE.Convert(c)}</math>.
::::#Server generates superposition on distribution D: <math>\sum_{\mu\in\{0,1\},r}\sqrt{D(\mu,r)}|\mu,r\rangle</math>
::::#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 <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>
***'''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>
::::#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>
::::#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>
::::#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>
<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 ===
 
*Input:  Classical output state (<math>l\in\{0,1\}^{\lambda}</math>), encrypted Pauli corrections  (<math>\tilde{z},\tilde{x}</math>)
*Output:  Decrypted classical message (<math>l\oplus x</math>)
**'''Decryption (FHE.Dec<math>_{sk}</math>)'''
#	 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 correct output  <math>l\oplus x</math>.</br>