Write, autoreview, editor, reviewer
3,129
edits
Classical Fully Homomorphic Encryption for Quantum Circuits: Difference between revisions
Jump to navigation
Jump to search
m
Classical Fully Homomorphic Encryption for Quantum Circuits (edit)
Revision as of 18:00, 22 November 2018
, 22 November 2018→Stage 2 Server’s Computation
| Line 69: | Line 69: | ||
### 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=</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=</math>CNOT 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=</math>CNOT 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</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></br> 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> | ||
###The Pauli key encryptions are homomorphically updated according to <math>P_{zx}</math>.</br> <math>\tilde{x} = x + x^{[l]}</math>, <math>\tilde{z} = z + z^{[l]}</math>. | ###The Pauli key encryptions are homomorphically updated according to <math>P_{zx}</math>.</br> <math>\tilde{x} = x + x^{[l]}</math>, <math>\tilde{z} = z + z^{[l]}</math>. | ||
### Three encrypted CNOTs are used to correct <math>C^{zx}</math> as follows under <math>\mathrm{AltHE}</math>. | ### Three encrypted CNOTs are used to correct <math>C^{zx}</math> as follows under <math>\mathrm{AltHE}</math>. | ||
***'''Server's Preparation:''' | |||
####Server converts <math>\hat{c} = \mathrm{HE.Convert(c)}</math>. | ####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 generates superposition on distribution D: <math>\sum_{\mu\in\{0,1\},r}\sqrt{D(\mu,r)}|\mu,r\rangle</math> | ||
#### Servers 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> | #### Servers 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> | ||
####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,\mu\in\{0,1\},r}\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,\mu\in\{0,1\},r}\alpha_{ab}\sqrt{D(\mu_0,r_0)}|a,b\rangle|\mu_a,r_a\rangle|y\rangle</math>, where <math>\beta</math> is the normalization constant. | ####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,\mu\in\{0,1\},r}\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,\mu\in\{0,1\},r}\alpha_{ab}\sqrt{D(\mu_0,r_0)}|a,b\rangle|\mu_a,r_a\rangle|y\rangle</math>, where <math>\beta</math> is the normalization constant. | ||
***'''Encrypted CNOT operation:''' <math>\sum_{a,b\in\{0,1\}}\alpha_{ab}CNOT^s|a\rangle|b\rangle</math>\otimes|\mu_a,r_a\rangle</br><math>=\alpha_{ab}|a\rangle|b\oplus a.s\rangle</math></br><math>=\alpha_{ab}|a\rangle|b\oplus a.(\mu_0+\mu_1)\rangle</math></br><math>=\alpha_{ab}|0\rangle|b\oplus 0\rangle+\alpha_{ab}|1\rangle|b\oplus \mu_0+\mu_1\rangle</math></br><math>=\alpha_{ab}|0\rangle|b\oplus \mu_0+\mu_1\rangle+\alpha_{ab}|1\rangle|b\oplus \mu_0+\mu_1\rangle</math>, <math>\because q\oplus q=0</math></br><math>=\alpha_{0b}|0\rangle X^{\mu_0}|b\oplus \mu_0\rangle+\alpha_{1b}|1\rangle X^{\mu_0}|b\oplus \mu_1\rangle</math>, <math>\because |w\oplus y\rangle=X^y|b\rangle</math></br><math>=\alpha_{ab}|a\rangle X^{\mu_0}|b\oplus \mu_a\rangle</math></br> | |||
####Server performs Hadamard on second register and measures it to get a string d. The resulting superposition state is:</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>(\mu_0,r_0)=(\mu_1,r_1)\oplus_H s</math>, as <math>\oplus_H</math> is the homomorphic XOR operation. | ####Server performs Hadamard on second register and measures it to get a string d. The resulting superposition state is:</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>(\mu_0,r_0)=(\mu_1,r_1)\oplus_H s</math>, as <math>\oplus_H</math> is the homomorphic XOR operation. | ||
####The server uses <math>pk_{i+1}</math> to compute HE.Enc<math>_{pk_{i+1}}(c_{x,z,pk_i})</math> and <math>\mathrm{HE.Enc}_{pk_{i+1}}(\hat{c},y,d)</math>. | ####The server uses <math>pk_{i+1}</math> to compute HE.Enc<math>_{pk_{i+1}}(c_{x,z,pk_i})</math> and <math>\mathrm{HE.Enc}_{pk_{i+1}}(\hat{c},y,d)</math>. | ||