Editing Prepare-and-Send Quantum Fully Homomorphic Encryption
Jump to navigation
Jump to search
The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then publish the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 40: | Line 40: | ||
*Server should be able to store entangled states, perform all Clifford and T gates. | *Server should be able to store entangled states, perform all Clifford and T gates. | ||
[[File:Prepare-and-Send Quantum Fully Homomorphic Encryption.png|center|Prepare-and-Send Quantum Fully Homomorphic Encryption]] | |||
==Properties == | ==Properties == | ||
Line 65: | Line 63: | ||
* p, location of inverse phase gate | * p, location of inverse phase gate | ||
* x,z measurement outcome sets of Client for her Bell Pair measurements. | * x,z measurement outcome sets of Client for her Bell Pair measurements. | ||
* <math> | * <math>x’,z’</math> measurement outcome sets of Server for his Gadget measurement. | ||
* <math>\tilde{x}^{[i]}</math>, resulting ciphertext one gets for an input <math>i^{th}</math> element of array x or <math>i^{th}</math> bit of key x after the Encrypting it with <math>i^{th}</math> of public key string, pk. | * <math>\tilde{x}^{[i]}</math>, resulting ciphertext one gets for an input <math>i^{th}</math> element of array x or <math>i^{th}</math> bit of key x after the Encrypting it with <math>i^{th}</math> of public key string, pk. | ||
== | == Pseudocode== | ||
===Stage 1 Client’s Preparation=== | ===Stage 1 Client’s Preparation=== | ||
'''Key Generation (QFHE.KeyGen(1k,1L))''' | '''Key Generation (QFHE.KeyGen(1k,1L))''' | ||
*Input: No. of T gates (L), Security Parameter (k), | *Input: No. of T gates (L), Security Parameter (k), | ||
*Output: L+1 evaluation keys (encrypted Gadgets, classical HE evaluation key), L+1 public keys, L+1 secret keys | *Output: L+1 evaluation keys (encrypted Gadgets, classical HE evaluation key), L+1 public keys, L+1 secret keys | ||
# For i = 0 to L | # For i = 0 to L | ||
## Client executes | ##Client executes (pki,ski,evki) ← HE.KeyGen(1κ) to obtain L + 1 independent classical homomorphic key sets. | ||
# She sets the public key to be the tuple | # She sets the public key to be the tuple ( . | ||
# She sets the secret key to be the tuple | # She sets the secret key to be the tuple ( . | ||
# For i = 0 to L | # For i = 0 to L − 1 | ||
## Client runs the procedure | ##Client runs the procedure QFHE.GenGadgetpki+1(ski) to create the gadget Γpki+1(ski). | ||
# Client sets the evaluation key to be the set of all gadgets created in the previous step (including their encrypted classical information), plus the tuple | # Client sets the evaluation key to be the set of all gadgets created in the previous step (including their encrypted classical information), plus the tuple ( . The resulting evaluation key is the classical-quantum (CQ) state {missing math} | ||
'''Encryption(QFHE.Enc())''' | '''Encryption(QFHE.Enc())''' | ||
*Input: Quantum Input state density matrix ( | *Input: Quantum Input state density matrix (ρ) (say composed of n single qubit states, σ) | ||
*Output: Encrypted pad keys: | *Output: Encrypted pad keys: {a˜[0]...a˜[n], ˜b[i]...˜b[n]}; QOTP state: Xa[1]Zb[1]⊗.....⊗Xa[n]Zb[n]ρZb[1]Xa[1]⊗ ..... ⊗ Xa[n]Zb[n] | ||
# For i=1 to n | # For i=1 to n | ||
## Client chooses pad keys a,b | ## Client chooses pad keys a,b | ||
## She quantum one time pads the single qubit by applying | ## She quantum one time pads the single qubit by applying XaZb on the single qubit state. XaZbσZbXa ← σ | ||
## She encrypts the pad keys using one bit for each of a and b from the public key string | ## She encrypts the pad keys using one bit for each of a and b from the public key string pk0 using HE.Enc. (˜ )=(HE.Enc ),HE.Enc | ||
## She apprehends encrypted pad keys to the one time padded quantum state to obtain CQ state, | ## She apprehends encrypted pad keys to the one time padded quantum state to obtain CQ state, | ||
# Client sends encryptions (˜a[i],˜b[i]) and the quantum one time padded (QOTP) state Xa[1]Zb[1] ⊗ ..... ⊗ Xa[n]Zb[n]ρZb[1]Xa[1] ⊗ ..... ⊗ Xa[n]Zb[n], for all i to the Server with the evaluation keys and public keys. | |||
#Client sends encryptions | '''Gadget Construction (QFHE.GenGadgetpki+1(ski))''' | ||
'''Gadget Construction ( | # Generate 4m EPR pairs ( | ||
# Generate | # Choose 2m pairs using sk | ||
# Choose | ## If (sk = 0) then {(a1,a2),(a2,a3),...,(a4m−1,a4m)} ii. If (sk = 1) then {(a1,a3),(a2,a4),...,(a4m−2,a4m)} | ||
## If | # For j=1 to 2m, | ||
## Choose p[j] | |||
# For j=1 to 2m, | ## Perform Bell Measurement on jth pair with an extra (P†)p operation, get outcomes (x[j],z[j]) | ||
## Choose p[j] | ## Thus, new EPR pairs are{missing math}<br/>If (sk = 0) then {(b1,b2),(b2,b3),...,(b4m−1,b4m)}<br/>If (sk = 1) then {(b1,b3),(b2,b4),...,(b4m−2,b4m)}<br/>Denote the 2m entangled pairs be denoted by {(s1,t1),(s2,t2),...,(s2m,t2m)}, such that<br/> | ||
## Perform Bell Measurement on | ###The classical information of gadget be g(sk)= ({(s1,t1),(s2,t2),...,(s2m,t2m),p,sk}.<br/> | ||
## Thus, new EPR pairs are | ###The quantum state of gadget can be written as {missing math} | ||
# Encrypt (x[j],z[j]), p[j] for all j and sk using pki+1. Resulting Gadget is the classical-quantum (CQ) state,{missing math} | |||
## The classical information of gadget be g(sk) | |||
## The quantum state of gadget can be written as | |||
# Encrypt (x[j],z[j]), p[j] for all j and sk using | |||
=== Stage 2 Server’s Computation=== | === Stage 2 Server’s Computation=== | ||
'''Circuit | '''Circuit Evaluation (QFHE.Eval())''' | ||
* | *Input: public key tuple ( , Evaluation key tuple, Encrypted Pad key ({a˜[0]...a˜[n], ˜b[i]...˜b[n]}), QOTP Input State (Xa[1]Zb[1] ⊗ ..... ⊗ Xa[n]Zb[n]ρZb[1]Xa[1] ⊗ ..... ⊗ Xa[n]Zb[n]) | ||
* | *Output: QOTP Circuit Output State (Xa0[1]Zb0[1]⊗.....⊗Xa0[k]Zb0[k]ρ0Zb0[1]Xa0[1]⊗.....⊗Xa0[k]Zb0[k]), Corresponding Encrypted Pad key (a˜0,b˜0)=(HE.EvalCevkL(a˜),HE.EvalCevkL(˜b)) | ||
Let the Circuit be denoted by C and the gates be | Let the Circuit be denoted by C and the gates be ci | ||
# For all i, | # For all i, ci gate is applied on qubit m and the mth bits of pad key (˜a[m],˜b[m]) are updated to | ||
## If | (a˜0[m],˜b0[m]) as follows. | ||
### if | ## If ci = {P,H,CNOT}, a Clifford gate then (ciXa[m]Zb[m]ψ = Xa0[m]Zb0[m]ciψ) | ||
### if | ### if ci =H then{missing math} (Hadamard tranforms X gate into Z and Z into X) | ||
### if | ### if ci =P then<br/>{missing math} | ||
## If | ###if ci =CNOT with m as target bit and n as control bit then (CNOT)<br/>(a˜[m],˜b[m];˜a[n],˜b[n]) → (a˜[m],˜b[m] ⊕˜b[n];˜a[m] ⊕a˜[n],˜b[n]) | ||
### | ## If ci = Tj gate then (TjXa[m]Zb[m]ψ = Pa[m]Xa[m]Zb[m]Tjψ) | ||
### | ### Generate Measurement<br/>M← QFHE.GenMeasurement(˜a[m],Γpkj+1(skj),evkj)<br/> | ||
### Gadget Correction<br/>(Xa0[m]Zb0[m]Tj)ψ ← QFHE.Measurement(M, Pa[m]Xa[m]Zb[m]Tjψ);<br/> Server gets measurement outcome x’,z’ | |||
### | ### Recryption Server recrypts one-pad key using pkk+1<br/>QFHE.Recpkk+1(a˜[m],˜b[m]).<br/> | ||
##Server updates the recrypted key using x,z and x’,z’. | |||
## Server sends the updated encryption and QOTP output state to Client. | ## Server sends the updated encryption and QOTP output state to Client. | ||
===Stage 3 Client’s Correction=== | ===Stage 3 Client’s Correction=== | ||
'''Decryption (QFHE.Dec()) | '''Decryption (QFHE.Dec()) | ||
* | *Input: QOTP Circuit Output State (Xa0[1]Zb0[1] ⊗ ..... ⊗ Xa0[k]Zb0[k]ρ0Zb0[1]Xa0[1] ⊗ ..... ⊗Xa0[k]Zb0[k]), Corresponding Encrypted Pad key (a˜0,b˜0) | ||
* | *Output: Final outcome of the computation CρC† = ρ0 (a) Client uses skL to restore the pad key from sent encryption. (a0[i],b0[i])=(HE.Dec [i](a0[i]),HE.Dec [i](b0[i])) | ||
# Client uses skL to restore the pad key from sen encryption | |||
# Client uses pad key and operates | # Client uses pad key and operates Xa Zb on single qubits i separately just like encryption.<br/>Let single qubit representation of the output state be Xa0[i]Zb0[i]σ0Zb0[i]Xa0[i], then operation of Pauli X,Z gates as above yields σ0 | ||
# Client repeats this for all single qubits and hence gets the quantum state ρ0, final outcome of the computation. | |||
# Client repeats this for all single qubits and hence gets the quantum state | |||
==Further Information== | ==Further Information== | ||
<div style='text-align: right;'>''*contributed by Shraddha Singh''</div> | <div style='text-align: right;'>''*contributed by Shraddha Singh''</div> |