Teleportation-based quantum homomorphic encryption scheme with quasi-compactness and perfect security
This addresses the challenge of secure and efficient encrypted quantum computation for applications like cloud quantum computing, though it is incremental as it builds on existing teleportation-based methods.
The paper tackles the problem of designing quantum homomorphic encryption (QHE) schemes that are perfectly secure and non-interactive, proposing two schemes (GT and VGT) that achieve quasi-compactness with decryption complexity bounded by O(M), where M is the number of T/T†-gates in the circuit, making them suitable for circuits with low T/T†-gate complexity.
This article defines encrypted gate, which is denoted by $EG[U]:|α\rangle\rightarrow\left((a,b),Enc_{a,b}(U|α\rangle)\right)$. We present a gate-teleportation-based two-party computation scheme for $EG[U]$, where one party gives arbitrary quantum state $|α\rangle$ as input and obtains the encrypted $U$-computing result $Enc_{a,b}(U|α\rangle)$, and the other party obtains the random bits $a,b$. Based on $EG[P^x](x\in\{0,1\})$, we propose a method to remove the $P$-error generated in the homomorphic evaluation of $T/T^\dagger$-gate. Using this method, we design two non-interactive and perfectly secure QHE schemes named \texttt{GT} and \texttt{VGT}. Both of them are $\mathcal{F}$-homomorphic and quasi-compact (the decryption complexity depends on the $T/T^\dagger$-gate complexity). Assume $\mathcal{F}$-homomorphism, non-interaction and perfect security are necessary property, the quasi-compactness is proved to be bounded by $O(M)$, where $M$ is the total number of $T/T^\dagger$-gates in the evaluated circuit. \texttt{VGT} is proved to be optimal and has $M$-quasi-compactness. According to our QHE schemes, the decryption would be inefficient if the evaluated circuit contains exponential number of $T/T^\dagger$-gates. Thus our schemes are suitable for homomorphic evaluation of any quantum circuit with low $T/T^\dagger$-gate complexity, such as any polynomial-size quantum circuit or any quantum circuit with polynomial number of $T/T^\dagger$-gates.