Classical Fully Homomorphic Encryption for Quantum Circuits: Difference between revisions

Classical Fully Homomorphic Encryption for Quantum Circuits (edit)

Revision as of 13:31, 20 November 2018

689 bytes added , 20 November 2018

m

→‎Stage 2 Server’s Computation

Shraddha

Write, autoreview, editor, reviewer

3,129

edits

@@ Line 68: / Line 68: @@
 ### if <math>c_i=</math>P then <div class="floatright">//Pauli Gate</div></br><math>(\tilde {a}^{[l]},\tilde{b}^{[l]})\rightarrow (\tilde{a}^{[l]},\tilde{a}^{[l]}\oplus\tilde{b}^{[l]})</math>
 ### if <math>c_i=</math>CNOT with m as target bit and n as control bit then <div class="floatright">//CNOT</div></br>(<math>\tilde {a}^{[l]},\tilde{b}^{[l]};\tilde {a}^{[n]},\tilde{b}^{[n]})\rightarrow (\tilde {a}^{[l]},\tilde{b}^{[l]}\oplus \tilde {b}^{[n]};\tilde{a}^{[l]}\oplus \tilde {a}^{[n]},\tilde{b}^{[n]})</math>
-##	 If <math>c_i=T</math> gate then <div class="floatright">//Toffoli Gate on $l_{th}, n_{th}, o_{th}$ key bits</div>
+##	 If <math>c_i=T</math> gate then <div class="floatright">//Toffoli Gate on <math>l_{th}, n_{th}, o_{th}</math> 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><math>TX^{a^{[l]}}Z^{b^{[l]}}X^{a^{[n]}}Z^{b^{[n]}}X^{a^{[o]}}Z^{b^{[o]}}|\psi\rangle</math></br><math>=TX^{a^{[l]}}Z^{b^{[l]}}X^{a^{[n]}}Z^{b^{[n]}}X^{a^{[o]}}Z^{b^{[o]}}T\dagger T|\psi\rangle</math></br><math>=CNOT_{l,o}^{a^{[n]}}CNOT_{n,o}^{a^{[l]}}CZ_{l,n}^{b^{[o]}}X^{a^{[l]}}Z^{b^{[l]}}T|\psi\rangle</math></br><math>=CNOT_{l,o}^{a^{[n]}}CNOT_{n,o}^{a^{[l]}}H_nCNOT_{l,n}^{b^{[o]}}H_{n}X^{a^{[l]}}Z^{b^{[l]}}T|\psi\rangle</math></br><math>=C_{ab}P_{ab}T|\psi\rangle</math>, where <math>C\epsilon \{\textnormal{CNOT,H}\}</math> and <math>P\epsilon\{X,Z\}</math>
+###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><math>TX^{a^{[l]}}Z^{b^{[l]}}X^{a^{[n]}}Z^{b^{[n]}}X^{a^{[o]}}Z^{b^{[o]}}|\psi\rangle</math></br><math>=TX^{a^{[l]}}Z^{b^{[l]}}X^{a^{[n]}}Z^{b^{[n]}}X^{a^{[o]}}Z^{b^{[o]}}T\dagger T|\psi\rangle</math></br><math>=CNOT_{l,o}^{a^{[n]}}CNOT_{n,o}^{a^{[l]}}CZ_{l,n}^{b^{[o]}}X^{a^{[l]}}Z^{b^{[l]}}T|\psi\rangle</math></br><math>=CNOT_{l,o}^{a^{[n]}}CNOT_{n,o}^{a^{[l]}}H_nCNOT_{l,n}^{b^{[o]}}H_{n}X^{a^{[l]}}Z^{b^{[l]}}T|\psi\rangle</math></br><math>=C_{ab}P_{ab}T|\psi\rangle</math>, where <math>C\epsilon \{\text{CNOT,H}\}</math> and <math>P\epsilon\{X,Z\}</math>
 ###The Pauli key encryptions are homomorphically updated  according to <math>P_{ab}</math>.
 ### Three encrypted CNOTs are used to correct <math>C^{ab}</math> as follows.
-####	The server applies encrypted CNOT operation to the two qubit state ZzXx |ψi using the ciphertext ˆc =HE.Convert(c).
+####The server applies encrypted CNOT operation to the two qubit state <math>Z^zX^x|\psi\rangle</math> using the secret text <math>\hat{c} = </math>HE.Convert<math>(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 following superposition sampled over random distribution D for the TCF function pairs (<math>f_0=</math>AltHE.Enc<math>_{pk}(),f_1</math>) based on the condition</br> <math>f_0\oplus_H f_1=\hat{c}\[\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}
+#### Servers generates three register for quantum input, function input, function output and entangles them as follows:</br><math>\[\sum_{a,b,\mu\in\{0,1\},r}\alpha_{ab}\sqrt{D(\mu,r)}|a\rangle|b\rangle|\mu,r\rangle|f_a(r)\rangle \]</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 a secret text <math>y = </math>AltHE.Enc<math>_{pk}(\mu_0,r_0)</math>, where <math>\mu_0\oplus\mu_1=s</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.
+####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><math>(Z^{d\cdot ((\mu_0,r_0)\oplus (\mu_1,r_1))}\otimes X^{\mu_0})\textrm{CNOT}_{1,2}^s|\psi\rangle</math> </br>where <math>\text{AltHE.Enc}_{pk}(\mu_0;r_0) = \text{AltHE.Enc}_{pk}(\mu_1;r_1) \oplus_H \hat{c}</math> and <math>\oplus_H</math> is the homomorphic XOR operation.
-####	The server uses pki+1 to compute HE.Encpki+1(ca,b,pki) and HE.Encpki+1(c,y,dˆ	).
+####The server uses <math>pk_{i+1}</math> to compute HE.Enc<math>_{pk_{i+1}}(c_{a,b,pk_i})</math> and HE.Enc<math>_{pk_{i+1}}(\hat{c},y,d)</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) .
+####The server computes the encryption of <math>a,b</math> under <math>pk_{i+1}</math> by homomorphically running the decryption circuit on inputs <math>\mathrm{HE.Enc}_{pk_{i+1}}(sk_i)</math> and HE.Enc<math>_{pk_{i+1}}(c_{a,b,pk_i})</math>.
-####	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).
+####The server homomorphically computes <math>(\mu_0,r_0)</math> and <math>(\mu_1,r_1)</math>, using the secret texts encrypting <math>t_{sk_i},sk_i,\hat{c},y,d</math> (all encrypted with HE under public key $pk_{i+1}$). The server then uses this result, along with the secret texts encrypting <math>a,b,d</math>, to homomorphically compute <math>\tilde{b} = b + (d\cdot ((\mu_0,r_0)\oplus (\mu_1,r_1)),0)</math> and <math>\tilde{a} = a + (0,\mu_0)</math>.
 #	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.