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 00:10, 26 November 2018
, 26 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=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=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</div></br> <div style="background-color: white; border: solid thin black;title=Functionality Description;"> | ## 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></div> | <div style="background-color: white; 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> | ###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>. | ### Three encrypted CNOTs are used to correct <math>C^{zx}</math> as follows under <math>\mathrm{AltHE}</math>. | ||
| Line 86: | Line 88: | ||
####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> | ####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: white; border: solid thin black;title=Functionality Description;"> | <div style="background-color: white; 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 | 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 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>. | ||
####The server computes the encryption of <math>x,z</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 <math>\mathrm{HE.Enc}_{pk_{i+1}}(c_{x,z,pk_i})</math>. | ####The server computes the encryption of <math>x,z</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 <math>\mathrm{HE.Enc}_{pk_{i+1}}(c_{x,z,pk_i})</math>. | ||