Prepare-and-Send Verifiable Quantum Fully Homomorphic Encryption

In this example protocol, Quantum Fully Homomorphic Encryption (link) protocol is implemented with the additional property of verification, where it is checked if the final ciphertext produces by the server matches the results of a particular computation. QFHE is a protocol where any arbitrary computations can be carried out by the server on the client's encrypted data while hiding all inputs and outputs of the client. In the classical version of this protocol, verification was carried by creating copies at every stage, which is not possible in the quantum version due to the no-cloning theorem(link). Hence in this protocol, verification is carried out by a technique where the server generates classical computational logs through which the underlying encryptions becomes authenticated. These computational logs are used to certify to the client that a particular homomorphic quantum computation was performed on a classical computer.

Tags: Two Party,Universal Task, Secure Delegated Quantum Computation, Quantum Offline Communication, Classical Offline Communication, Quantum Gadgets, Prepare and Send Quantum Fully Homomorphic Encryption, Classical Fully Homomorphic Encryption for Quantum Circuits.

Outline

This protocol consists mainly of four stages: Key Generation, Encryption, Homomorphic evaluation and Verified decryption. For verification, the major changes from the standard Prepare and Send Quantum Fully Homomorphic Encryption is in stage 2, evaluation where a computational log is provided as an extra output and in stage 4, Verified decryption which accepts computational log and performs the verification. The verification performed in this protocol is mainly classical in nature

• Key Generation and Encryption
  • This procedure requires the generation of single-qubit and two-qubit states from a small fixed set, performing Bell measurements and Pauli gates, and executing the encoding procedure of a quantum error-correcting code on which the trap code is based.
  • In this step, using the classical fully homomorphic encryption scheme, public key, the secret keys and the evaluation function key for the encryption are generated. A message authenticating system (MAC) is used to authenticate this process. Using MAC, a key is also generated.
  • Majority of the single-qubit and two qubit quantum states are encrypted using the global permutation $\pi$, but all the qubits in the error correcting gadget are encrypted using independent permutation. The encryption occurs through CSS where equal amounts of traps gates ($|0\rangle$ and $|+\rangle$) are added and permuted using the global permutation, after which the overall state is encrypted by using Quantum one time pad. The final state formed of the single-qubit or two qubit quantum used initially is known as the magic state.
  • The keys for the quantum one-time pad are selected during the encryption stage, For the $T$ gate, error correcting gadgets are prepared from garden-hose gadgets(Link here).
  • Then the evaluation key is formed, using the auxiliary states mentioned, which includes the magic states too.

• Evaluation: Evaluation of a circuit is done gate by gate. Throughout this procedure, apart from the outputs, a complete computational log is made of all randomness used, all computation steps, all intermediate results and all the classical FHE computations. To measure a qubit, we measure all ciphertext qubits and place the outcomes in the log.
  • Measurements: In computational basis measurement, logical measurement is performed by measurement of all physical qubits of the ciphertext and also checks the traps. This is followed by using the encryption function of classical homomorphic encryption on the result. In Hadamard basis measurement, because of the Hadamard gate property of $H|0\rangle =|+\rangle$ and $H|+\rangle =|0\rangle$, all computational traps are swapped with the Hadamard traps. . A transversal application of $H$ to all relevant physical qubits precedes the evaluation procedure for the computational basis measurement.
  • Pauli gates: Applying a logical Pauli is done by applying the same Pauli to all physical qubits. The application of Pauli gates ($X$ and/or $Z$) to a state encrypted with a quantum one-time pad can be achieved without touching the actual state, by updating the keys to QOTP in the appropriate way. The logical Pauli-X is performed by (homomorphically) flipping the X-key bits of the QOTP and Pauli-Y works in the same manner for Z-key bits. Hence, this is a classical task.
  • CNOT gate: The effect of applying CNOT to the encrypted qubits, without the quantum one-time padding is that logical CNOT is applied to the physical data qubits in the permutation and the remaining traps are unchanged due to its action. Hence in the quantum one-time pad, the secret key bits are homomorphically updated during evaluation while applying CNOT.
  • Phase gates: Performing this gate requires homomorphic evaluation of all the above gates: (classically controlled) Paulis, CNOTs, and measurements. Here the corresponding encrypted magic state is also used. The below circuit is used to apply this gate
  • Hadamard gate: The Hadamard gate can be applied using the same method used in the Phase gate.
  • T gate: Applying T requires a magic state and an encrypted garden-hose gadget (because the T-gate magic state circuit applies a P-gate conditioned on a measurement outcome). The evaluation of that circuit is complicated and hence that specific error correcting gadget is used.

• Verified decryption
  • Here the correctness and consistency of the classical FHE transcript, the measurement outcomes, and the claimed circuit are checked. The result of this computation is a set of keys for the trap code, which are correct provided that Eval was performed honestly. In this step, decryption takes place using these keys and the output is either plaintext or reject. In terms of quantum capabilities, decryption requires executing the decoding procedure of the error-correcting code, computational-basis and Hadamard-basis measurements, and Paulis.
  • This procedure consists of two parts. Several classical checks are performed at first, where MAC-verification of all classically authenticated messages takes places. It also includes checking if the gates listing in the computational log match the circuit description. The portion of the log which specifies the purely classical, FHE steps taking during classical homomorphic encryption are also checked. Next, all the unmeasured traps are checked and the remaining qubits are decoded. If the logs don't match or if any of the traps are triggered, then the entire process is rejected.

Properties

• Compactness: This protocol is compact if verified decryption is divisible into a classical verification procedure Verification (outputting only an accept/reject flag), followed by a quantum decryption procedure Decryption. The running time of Verification is allowed to depend on the circuit size, but the running time of Decryption is not when it is compact.
• Semantic Security: A QPT adversary with access to the ciphertext can be simulated by a simulator that only has access to an ideal functionality that simply applies the claimed circuit. (Explain when this protocol is semantically secure)
• Indistinguishability: For a defined security game, if the success probability for an QPT adversary is at-most ${\frac {1}{2}}+negl(\kappa )$, then this protocol is indistinguishable. The security game is based on the QPT adversary determining the outcome of a hidden coin flip.
• Fully Homomorphic: This protocol is fully homomorphic i.e. Server can operate any quantum circuit using this protocol.
• Privacy: this scheme is private if its ciphertexts are indistinguishable under chosen plaintext attack.
• Computational logs are generally classical in nature.

Notation

• $\kappa$: Security parameter.
• $t$: Upper bound on T gate.
• $p$: Upper bound on P gate.
• $h$: Upper bound on H gate.
• $k$: All keys
• $\pi$: Global permutation which are used to encrypt the states.
• MAC: Message authentication code, MAC = (Tag, Ver)
• $pk_{i},sk_{i},evk_{i}$: $i_{th}$ homomorphic key set generated from HE.KeyGen(). Public key for encryption, secret key for decryption, evaluation function key, respectively for given k, the security parameter.
• $v$:
• $\mu$:
• $m\times n$: Resource state size
• Failed to parse (unknown function "\ket"): {\displaystyle \ket{\psi_P}} : Failed to parse (unknown function "\ket"): {\displaystyle P(\ket{R}\otimes \ket{+}^{\otimes \frac{N}{3}} \otimes \ket{0}^{\otimes \frac{N}{3}})} , this is the $n$-qubit state left with the server which contains the trap qubits (Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ket{0}, \ket{+}} ) and resource state.
• Failed to parse (unknown function "\ket"): {\displaystyle \ket{R}: \frac{n}{3}} -qubit resource state
• $P:n$-qubit permutation, which keeps the order of qubits in Failed to parse (unknown function "\ket"): {\displaystyle \ket{R}}
• Failed to parse (unknown function "\ket"): {\displaystyle \ket{+}} : Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{\sqrt{2}} (\ket{0} +\ket{1})}
• q: $(x_{1},...,x_{n},z_{1},...,z_{n})\in \{0,1\}^{2n}$
• $\sigma _{q}:\bigotimes _{j=1}^{n}X_{j}^{x_{j}}Z_{j}^{z_{j}}$
• ${\tilde {\sigma }}$: ciphertext

Pseudo Code

Stage 1: Key generation and encryption

Function 1: TrapTP.KeyGen($1^{\kappa },1^{t},1^{p},1^{h}$)

• $k{\xleftarrow[{}]{}}$ MAC.KeyGen$(1^{\kappa })$
• $\pi {\xleftarrow[{r}]{}}S_{3m}$
• for $i=0,...,t:$
  • $(sk_{i},pk_{i},ev_{i}){\xleftarrow[{}]{}}$ HE.KeyGen$(1^{\kappa })$
• $sk{\xleftarrow[{}]{}}(\pi ,k,sk_{0},...,sk_{t},pk_{0})$
• for $i=0,...,p:$
  • $\mu _{i}^{P}{\xleftarrow[{}]{}}$ TrapTP.ENC$(sk,P|+\rangle )$
• for $i=0,...,t:$
  • $\mu _{i}^{T}{\xleftarrow[{}]{}}$ TrapTP.ENC$(sk,T|+\rangle )$
• for $i=0,...,h:$
  • $\mu _{i}^{H}{\xleftarrow[{}]{}}$ TrapTP.ENC$(sk,{\frac {1}{\sqrt {2}}}(H\otimes I)(|00\rangle +|11\rangle ))$
• for $i=0,...,t:$
  • $\pi _{i}{\xleftarrow[{r}]{r}}S_{3m}$
  • $(g_{i},\gamma _{i}^{in},\gamma _{i}^{mid},\gamma _{i}^{out}){\xleftarrow[{}]{}}$ TrapTP.GadgetGen$(sk_{i-1})$
  • $\Gamma _{i}{\xleftarrow[{}]{}}$ MAC.Sign(HE.ENC$_{pk_{i}}(g_{i},\pi _{i}))\otimes$ TrapTP.ENC$((\pi _{i},k,sk_{0},...,sk_{t},pk_{i}),\gamma _{i}^{mid}\otimes$ TrapTP.Enc$(sk,\gamma _{i}^{in},\gamma _{i}^{out}$
• $keys{\xleftarrow[{}]{}}$ MAC.Sign$(evk_{0},...,evk_{t},pk_{0},...,pk_{t},$ HE.Enc$_{pk_{0}}(\pi ))$
• $\rho _{evk}{\xleftarrow[{}]{}}(keys,\mu _{0}^{P},...,\mu _{p}^{P},\mu _{0}^{T},...,\mu _{t}^{T},\mu _{0}^{H},...,\mu _{h}^{H},\Gamma _{1},...,\Gamma _{t})$
• return $(sk,\rho _{evk})$

Function 2: TrapTP.GadgetGen($sk_{i}$)

• $g_{i}{\xleftarrow[{}]{}}g(sk_{i})$
• $(\gamma ^{in},\gamma ^{mid},\gamma ^{out}){\xleftarrow[{}]{}}$ generate $|\Phi ^{+}\rangle$ states depending on $g_{i}$
• return ($g_{i},\gamma ^{in},\gamma ^{mid},\gamma ^{out}$)

Function 3: TrapTP.Enc(($\pi ,k,sk_{0},...,sk_{t},pk$), $\sigma$)

• ${\tilde {\sigma }}{\xleftarrow[{}]{}}\Sigma _{x,z\in \{0,1\}^{3m}}$ (TC.Enc$((\pi ,x,z),\sigma )\otimes$ MAC.Sign$_{k}(HE.Enc_{pk}(x,z)))$
• return ${\tilde {\sigma }}$

Function 4: TrapTP.EvalMeasure(${\tilde {\sigma }},{\tilde {x}},{\tilde {z}},{\tilde {\pi }},pk,evk$)

• $a=(a_{1},...,a_{3m}){\xleftarrow[{}]{}}$ measure qubits of ${\tilde {\sigma }}$ in the computational basis
• $({\tilde {a}},log_{1}){\xleftarrow[{}]{}}$ HE.Enc$_{pk}(a)$
• $({\tilde {b}},{\tilde {flag}},log_{2}$ \xleftarrow[]{} HE.Eval$_{evk}^{TC.VerDecMeasurement}(({\tilde {\pi }},{\tilde {x}},{\tilde {z}}),{\tilde {a}},HE.Enc_{pk}(+))$
• return (${\tilde {b}},{\tilde {flag}},log_{1},log_{2}$)

Function 5: TrapTP.EvalX(${\tilde {\sigma }},{\tilde {x}},{\tilde {\pi }},pk,evk$)

• $({\tilde {x}},log_{1}){\xleftarrow[{}]{}}$ HE.Eval$_{evk}^{unpermute}({\tilde {\pi }},{\tilde {x}})$
• $({\tilde {x}},log_{2}){\xleftarrow[{}]{}}$ HE.Eval$_{evk}^{\otimes }({\tilde {x}},$ HE.Enc$_{pk}(1^{m}0^{2m}))$
• $({\tilde {x}},log_{3}){\xleftarrow[{}]{}}$ HE.Eval$_{evk}^{permute}({\tilde {\pi }},{\tilde {x}})$
• return (${\tilde {\sigma }},{\tilde {x}},log_{1},log_{2},log_{3}$)

Function 6: TrapTP.EvalCondX(${\tilde {b}},{\tilde {\sigma }},{\tilde {x}},{\tilde {z}},{\tilde {\pi }},pk,evk$)

• $({\tilde {x}},log_{1}){\xleftarrow[{}]{}}$ HE.Eval$_{evk}^{unpermute}({\tilde {\pi }},{\tilde {x}})$
• ${\tilde {s}}{\xleftarrow[{}]{}}$ HE.Eval$_{evk}^{y{\xrightarrow[{}]{}}y^{m}0^{2m}}({\tilde {b}})$
• $({\tilde {x}},log_{2}){\xleftarrow[{}]{}}$ HE.Eval$_{evk}^{\otimes }({\tilde {x}},{\tilde {s}})$
• $({\tilde {x}},log_{3}){\xleftarrow[{}]{}}$ HE.Eval$_{evk}^{permute}({\tilde {\pi }},{\tilde {x}})$
• return (${\tilde {\sigma }},{\tilde {x}},{\tilde {z}},log_{1},log_{2},log_{3}$)

Function 7: TrapTP.EvalCNOT(${\tilde {\sigma }}_{1},{\tilde {\sigma }}_{2},{\tilde {x}}_{1},{\tilde {x}}_{2},{\tilde {z}}_{1},{\tilde {z}}_{2},{\tilde {\pi }},pk,evk$)

• $({\tilde {\sigma }}_{1},{\tilde {\sigma }}_{2}){\xleftarrow[{}]{}}$ apply $CNOT$ on all physical qubit pairs of ${\tilde {\sigma }}_{1},{\tilde {\sigma }}_{2}$
• $({\tilde {x}}_{1},{\tilde {x}}_{2},{\tilde {z}}_{1},{\tilde {z}}_{2},log_{1}){\xleftarrow[{}]{}}$ HE.Eval$_{evk}^{CNOT-key-update}({\tilde {x}}_{1},{\tilde {x}}_{2},{\tilde {z}}_{1},{\tilde {z}}_{2})$
• return $({\tilde {\sigma }}_{1},{\tilde {\sigma }}_{2},{\tilde {x}}_{1},{\tilde {x}}_{2},{\tilde {z}}_{1},{\tilde {z}}_{2},log_{1},log_{2})$

Function 8: TrapTP.EvalT(${\tilde {\sigma }},{\tilde {x}},{\tilde {z}},{\tilde {\pi }},\mu _{i}^{T},\Gamma _{i},pk_{i-1},evk_{i-1}$)

• $({\tilde {\sigma }}_{1},{\tilde {\sigma }}_{2},{\tilde {x}}_{1},{\tilde {z}}_{1},{\tilde {x}}_{2},{\tilde {z}}_{1},log_{1}){\xleftarrow[{}]{}}$ Trap.TP.EvalCNOT($(\mu _{i}^{T},{\tilde {\sigma }},{\tilde {x}},{\tilde {z}},{\tilde {\pi }},pk_{i-1},evk_{i-1}$)
• $({\tilde {b}},log_{2}){\xleftarrow[{}]{}}$ TrapTP.EvalMeasure(${\tilde {\sigma }}_{2},{\tilde {x}}_{2},{\tilde {z}}_{2},{\tilde {\pi }},pk_{i-1},evk_{i-1}$
• $log_{3}{\xleftarrow[{}]{}}$ recrypt all classically encrypted information (except ${\tilde {b}}$) from key set $i-1$ into key set $i$.
• $({\tilde {\sigma }},log_{4}){\xleftarrow[{}]{}}$ TrapTP.EvalCondP$({\tilde {b}},{\tilde {\sigma }}_{1},{\tilde {x}}_{1},{\tilde {z}}_{1},\Gamma _{i},{\tilde {\pi }},pk_{i},evk_{i})$
• return $({\tilde {\sigma }},log_{!},log_{2},log_{3},log_{4})$

Function 9: TrapTP.EvalCondP(${\tilde {b}},{\tilde {\sigma }},{\tilde {x}},{\tilde {z}},\Gamma _{i}=({\tilde {g_{i}}},{\tilde {\pi }}_{i},{\tilde {\gamma _{i}^{in}}},{\tilde {\gamma _{i}^{mid}}},{\tilde {\gamma _{i}^{out}}}),{\tilde {\pi }},pk_{i},evk_{i}$)

• $({\tilde {a}}_{1},{\tilde {a}}_{2},log_{1}){\xleftarrow[{}]{}}$ evaluate Bell measurement between ${\tilde {\sigma }}$ and ${\tilde {\gamma }}_{i}^{in}$
• $({\tilde {a}},log_{2}){\xleftarrow[{}]{}}$ evaluate Bell measurement in ${\tilde {\Gamma _{i}^{mid}}}$ as dictated by the ciphertext ${\tilde {b}}$ and the garden-hose protocol for HE.Dec
• $({\tilde {x}},{\tilde {z}},log_{3}){\xleftarrow[{}]{}}$ HE.Eval$_{evk_{i}}^{T-key-update}({\tilde {x}},{\tilde {z}},{\tilde {a}}_{1},{\tilde {a}}_{2},{\tilde {a}},{\tilde {g}}_{i})$
• return $({\tilde {\gamma _{i}^{out}}},{\tilde {x}},{\tilde {z}},log_{1},log_{2},log_{3})$

Function 10: TrapTP.VerDec($sk,{\tilde {\sigma }},{\tilde {x[i]}}_{i},{\tilde {z[i]}}_{i},log,c$)

• Verify classically authenticated messages (in $log$) using (contained in $sk$). If one of these verifications rejects, reject.
• Check whether all claimed gates in log match the structure of c. If not, return ($\Omega ,|rej\rangle$).
• $flag$ ← TrapTP.CheckLog($log$) If flag = rej, return ($\Omega ,|rej\rangle$).
• Check whether the claimed final QOTP keys in the log match ${\tilde {x}}$ and ${\tilde {z}}$. If not, return ($\Omega ,|rej\rangle$).
• for all gates G of c do
  • if G is a measurement then
    • ${\tilde {x'}},{\tilde {z'}}{\xleftarrow[{}]{}}$ encrypted QOTP keys right before measurement (listed in $log$)
    • ${\tilde {w}}{\xleftarrow[{}]{}}$ encrypted measurement outcomes (listed in $log$)
    • ${\tilde {x'}},{\tilde {z'}},{\tilde {w}}{\xleftarrow[{}]{}}$ HE.Dec$_{{sk}_{t}}({\tilde {x'}},{\tilde {z'}},{\tilde {w}})$
    • Execute TC.VerDecMeasurement$((\pi ,x',z'),w,basis)$ where basis is the appropriate basis for the measurement, and store the (classical) outcome.
    • if a trap is triggered then
      • return ($\Omega ,|rej\rangle$)
• for all unmeasured qubits ${\tilde {\sigma _{i}}}$ in ${\tilde {\sigma }}$ do
  • $x[i],z[i]{\xleftarrow[{}]{}}$ HE.Dec$_{sk_{t}}({\tilde {x[i]}},{\tilde {z[i]}})$
  • $\sigma _{i}{\xleftarrow[{}]{}}$ TC.VerDec$_{(\pi ,x[i],z[i])}({\tilde {\sigma _{i}}}).$ If TC.VerDec rejects, return $(\Omega ,|rej\rangle )$
• $\sigma {\xleftarrow[{}]{}}$ the list of decrypted qubits (and measurement outcomes) that are part of the output of c
• return ($\sigma ,|acc\rangle$)

Further Information

*contributed by Rhea Parekh