Editing Prepare-and-Send Verifiable Quantum Fully Homomorphic Encryption (section)

==Protocol Description==

'''Stage 1''': Key generation and encryption </br>
Main function: TrapTP.KeyGen

'''Function 1''': TrapTP.KeyGen(<math>1^\kappa, 1^t, 1^p, 1^h</math>)</br>

* <math>k \xleftarrow[]{}</math> MAC.KeyGen<math>(1^\kappa)</math>
* <math>\pi \xleftarrow[r]{} S_{3m}</math>
* for <math>i = 0, ..., t:</math>
** <math>(sk_i, pk_i, ev_i) \xleftarrow[]{}</math> HE.KeyGen<math>(1^\kappa)</math>
* <math>sk \xleftarrow[]{} (\pi, k, sk_0, ..., sk_t, pk_0)</math>
* for <math>i = 0, ..., p:</math>
** <math>\mu_i^{P} \xleftarrow[]{}</math>  TrapTP.ENC<math>(sk, P|+\rangle)</math>
* for <math>i = 0, ..., t:</math>
** <math>\mu_i^{T} \xleftarrow[]{}</math>  TrapTP.ENC<math>(sk, T|+\rangle)</math>
* for <math>i = 0, ..., h:</math>
** <math>\mu_i^{H} \xleftarrow[]{}</math>  TrapTP.ENC<math>(sk, \frac{1}{\sqrt{2}}(H\otimes I)(|00\rangle + |11\rangle))</math>
* for <math>i = 0, ..., t:</math>
** <math>\pi_i \xleftarrow[r]{r} S_{3m}</math>
** <math>(g_i, \gamma_i^{in}, \gamma_i^{mid}, \gamma_i^{out}) \xleftarrow[]{}</math> TrapTP.GadgetGen<math>(sk_{i-1})</math>
** <math>\Gamma_i \xleftarrow[]{}</math> MAC.Sign(HE.ENC<math>_{pk_i}(g_i, \pi_i)) \otimes</math> TrapTP.ENC<math>((\pi_i, k, sk_0, ..., sk_t, pk_i), \gamma^{mid}_i \otimes</math> TrapTP.Enc<math>(sk, \gamma^{in}_i, \gamma^{out}_i)</math>
* <math>keys \xleftarrow[]{}</math> MAC.Sign<math>(evk_0, ..., evk_t, pk_0, ..., pk_t,</math> HE.Enc<math>_{pk_0}(\pi))</math>
* <math>\rho_{evk} \xleftarrow[]{} (keys, \mu^{P}_0, ..., \mu^{P}_p, \mu^{T}_0, ..., \mu^{T}_t, \mu^{H}_0, ..., \mu^{H}_h, \Gamma_1, ..., \Gamma_t)</math>
* return <math>(sk, \rho_{evk})</math>

</br>
'''Function 2''': TrapTP.GadgetGen(<math>sk_i</math>)
* <math>g_i \xleftarrow[]{} g(sk_i)</math>
* <math>(\gamma^{in}, \gamma^{mid}, \gamma^{out}) \xleftarrow[]{}</math> generate <math>|\Phi^+\rangle</math> states depending on <math>g_i</math>
* return (<math>g_i, \gamma^{in}, \gamma^{mid}, \gamma^{out}</math>)

</br>
'''Function 3''': TrapTP.Enc((<math>\pi, k, sk_0, ..., sk_t, pk</math>), <math>\sigma</math>)

* <math>\tilde{\sigma} \xleftarrow[]{} \Sigma_{x, z \in \{0,1\}^{3m}} </math> (TC.Enc<math>((\pi, x, z), \sigma) \otimes</math> MAC.Sign<math>_k(HE.Enc_{pk}(x,z)))</math> 
* return <math>\tilde{\sigma}</math>

</br>
'''Stage 2''': Evalutation </br>

</br>
'''Function 4''': TrapTP.EvalMeasure(<math>\tilde{\sigma}, \tilde{x}, \tilde{z}, \tilde{\pi}, pk, evk</math>)

* <math>a = (a_1, ..., a_{3m}) \xleftarrow[]{}</math> measure qubits of <math>\tilde{\sigma}</math> in the computational basis
* <math>(\tilde{a}, log_1) \xleftarrow[]{}</math> HE.Enc<math>_{pk}(a)</math>
* <math>(\tilde{b}, \tilde{flag}, log_2 \xleftarrow[]{} </math>HE.Eval<math>^{TC.VerDecMeasurement}_{evk}((\tilde{\pi}, \tilde{x}, \tilde{z}), \tilde{a}, HE.Enc_{pk}(+))</math>
* return (<math>\tilde{b}, \tilde{flag}, log_1, log_2</math>)

</br>
'''Function 5''': TrapTP.EvalX(<math>\tilde{\sigma}, \tilde{x}, \tilde{\pi}, pk, evk</math>)

* <math>(\tilde{x}, log_1) \xleftarrow[]{}</math> HE.Eval<math>_{evk}^{unpermute}(\tilde{\pi}, \tilde{x})</math>
* <math>(\tilde{x}, log_2) \xleftarrow[]{}</math> HE.Eval<math>_{evk}^{\otimes}(\tilde{x},</math> HE.Enc<math>_{pk}(1^m0^{2m}))</math>
* <math>(\tilde{x}, log_3) \xleftarrow[]{}</math> HE.Eval<math>^{permute}_{evk}(\tilde{\pi}, \tilde{x})</math>
* return (<math>\tilde{\sigma}, \tilde{x}, log_1, log_2, log_3</math>)

</br>
'''Function 6''': TrapTP.EvalCondX(<math>\tilde{b}, \tilde{\sigma}, \tilde{x}, \tilde{z}, \tilde{\pi}, pk, evk</math>)

* <math>(\tilde{x}, log_1) \xleftarrow[]{}</math> HE.Eval<math>_{evk}^{unpermute}(\tilde{\pi}, \tilde{x})</math>
* <math>\tilde{s} \xleftarrow[]{}</math> HE.Eval<math>^{y\xrightarrow[]{} y^m0^{2m}}_{evk}(\tilde{b})</math>
* <math>(\tilde{x}, log_2) \xleftarrow[]{}</math> HE.Eval<math>_{evk}^{\otimes}(\tilde{x}, \tilde{s})</math>
* <math>(\tilde{x}, log_3) \xleftarrow[]{}</math> HE.Eval<math>^{permute}_{evk}(\tilde{\pi}, \tilde{x})</math>
* return (<math>\tilde{\sigma}, \tilde{x}, \tilde{z}, log_1, log_2, log_3</math>)

</br>
'''Function 7''': TrapTP.EvalCNOT(<math>\tilde{\sigma}_1, \tilde{\sigma}_2, \tilde{x}_1, \tilde{x}_2, \tilde{z}_1, \tilde{z}_2, \tilde{\pi}, pk, evk</math>)

* <math>(\tilde{\sigma}_1, \tilde{\sigma}_2) \xleftarrow[]{}</math> apply <math>CNOT</math> on all physical qubit pairs of <math>\tilde{\sigma}_1, \tilde{\sigma}_2</math>
* <math>(\tilde{x}_1, \tilde{x}_2, \tilde{z}_1, \tilde{z}_2, log_1) \xleftarrow[]{}</math> HE.Eval<math>^{CNOT-key-update}_{evk}(\tilde{x}_1, \tilde{x}_2, \tilde{z}_1, \tilde{z}_2)</math>
* return <math>(\tilde{\sigma}_1, \tilde{\sigma}_2, \tilde{x}_1, \tilde{x}_2, \tilde{z}_1, \tilde{z}_2, log_1, log_2)</math>

</br>
'''Function 8''': TrapTP.EvalT(<math>\tilde{\sigma}, \tilde{x}, \tilde{z}, \tilde{\pi}, \mu_i^{T},\Gamma_i, pk_{i-1}, evk_{i-1}</math>)

* <math>(\tilde{\sigma}_1, \tilde{\sigma}_2, \tilde{x}_1, \tilde{z}_1, \tilde{x}_2, \tilde{z}_1, log_1) \xleftarrow[]{}</math> Trap.TP.EvalCNOT(<math>(\mu^T_i, \tilde{\sigma}, \tilde{x}, \tilde{z}, \tilde{\pi}, pk_{i-1}, evk_{i-1} </math>)
* <math>(\tilde{b}, log_2) \xleftarrow[]{}</math> TrapTP.EvalMeasure(<math>\tilde{\sigma}_2, \tilde{x}_2, \tilde{z}_2, \tilde{\pi}, pk_{i-1}, evk_{i-1}</math>
* <math>log_3 \xleftarrow[]{}</math> recrypt all classically encrypted information (except <math>\tilde{b}</math>) from key set <math>i-1</math> into key set <math>i</math>.
* <math>(\tilde{\sigma}, log_4) \xleftarrow[]{}</math> TrapTP.EvalCondP<math>(\tilde{b}, \tilde{\sigma}_1, \tilde{x}_1, \tilde{z}_1, \Gamma_i, \tilde{\pi}, pk_i, evk_i)</math>
* return <math>(\tilde{\sigma}, log_!, log_2, log_3, log_4)</math>

</br>
'''Function 9''': TrapTP.EvalCondP(<math>\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}</math>)

* <math>(\tilde{a}_1, \tilde{a}_2, log_1) \xleftarrow[]{}</math> evaluate Bell measurement between <math>\tilde{\sigma}</math> and <math>\tilde{\gamma}^{in}_i</math>
* <math>(\tilde{a}, log_2) \xleftarrow[]{}</math> evaluate Bell measurement in <math>\tilde{\Gamma_i^{mid}}</math> as dictated by the ciphertext <math>\tilde{b}</math> and the garden-hose protocol  for HE.Dec
*  <math>(\tilde{x}, \tilde{z}, log_3) \xleftarrow[]{}</math> HE.Eval<math>^{T-key-update}_{evk_i}(\tilde{x}, \tilde{z}, \tilde{a}_1, \tilde{a}_2, \tilde{a}, \tilde{g}_i)</math>
* return <math>(\tilde{\gamma_i^{out}}, \tilde{x}, \tilde{z}, log_1, log_2, log_3)</math>


'''Stage 3''': Verification Decryption </br>

</br>
'''Function 10''': TrapTP.VerDec(<math>sk, \tilde{\sigma}, \tilde{x[i]}_i, \tilde{z[i]}_i, log, c</math>)

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