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 16:14, 22 November 2018
, 22 November 2018→Stage 2 Server’s Computation
| Line 60: | Line 60: | ||
=== '''Stage 2''' Server’s Computation === | === '''Stage 2''' Server’s Computation === | ||
*Input: <math> | *Input: <math>\mathrm{evk}_i</math>, encrypted pad key elements concatenation <math>s</math> <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 Quantum One time Padded Output State <math>X^{\tilde {x}}Z^{\tilde{z}}C|\psi\rangle</math> in case of quantum output, where C is the quantum circuit) | *Output: Updated encryption of pad key <math>\tilde{z},\tilde{x}</math> (and Quantum One time Padded Output State <math>X^{\tilde {x}}Z^{\tilde{z}}C|\psi\rangle</math> in case of quantum output, where C is the quantum circuit) | ||
**'''Circuit Evaluation (FHE.Eval())''' | **'''Circuit Evaluation (FHE.Eval())''' | ||
| Line 72: | Line 72: | ||
###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>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 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>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>. | ###The Pauli key encryptions are homomorphically updated according to <math>P_{zx}</math>. | ||
### Three encrypted CNOTs are used to correct <math>C^{zx}</math> as follows | ### Three encrypted CNOTs are used to correct <math>C^{zx}</math> as follows under <math>\mathrm{AltHE.Enc}</math>. | ||
####Server converts <math>\hat{c} = </math>\mathrm{HE.Convert}<math>(c)</math>. | |||
####Server generates following superposition sampled over random distribution D\sqrt{D(\mu,r)}|\mu,r\rangle</math> | ####Server generates following superposition sampled over random distribution D\sqrt{D(\mu,r)}|\mu,r\rangle</math> | ||
#### Servers | #### Servers entangles above superposition and <math>\psi</math> with a third register for function output as follows:</br><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 <math>\mathrm{AltHE.Enc}_{pk}(s)</math> | ||
####Server measures the last register to get | ####Server measures the last register to get <math>y =\mathrm{AltHE.Enc}(\mu_0,r_0)=<math>\mathrm{AltHE.Enc}_{pk}(\mu_1,r_1)\oplus_H AltHE.Enc_{pk}(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><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 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>(\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 HE.Enc | ####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 HE.Enc | ####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 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 <math>pk_{i+1}</math>). The server then uses this result, along with the secret texts encrypting <math>x,z,d</math>, to homomorphically compute <math>\tilde{z} = z + (d\cdot ((\mu_0,r_0)\oplus (\mu_1,r_1)),0)</math> and <math>\tilde{x} = x + (0,\mu_0)</math>. | ####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 <math>pk_{i+1}</math>). The server then uses this result, along with the secret texts encrypting <math>x,z,d</math>, to homomorphically compute <math>\tilde{z} = z + (d\cdot ((\mu_0,r_0)\oplus (\mu_1,r_1)),0)</math> and <math>\tilde{x} = x + (0,\mu_0)</math>. | ||
#Server sends updated encryptions of Pauli corrections <math>\tilde{x},\tilde{z}</math> and the classical outcome after measurement of the output state (or Quantum one time padded state in case of quantum output) to Client. | #Server sends updated encryptions of Pauli corrections <math>\tilde{x},\tilde{z}</math> and the classical outcome after measurement of the output state (or Quantum one time padded state in case of quantum output) to Client. | ||