Teleportation-based quantum homomorphic encryption scheme with quasi-compactness and perfect security

Abstract

Quantum homomorphic encryption (QHE) is an important cryptographic technology for delegated quantum computation. It enables remote server to perform quantum computation on encrypted data, and the specific algorithm performed by Server is unnecessarily known by Client. Quantum fully homomorphic encryption (QFHE) is a QHE that satisfies both compactness and F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {F}}$$\end{document}-homomorphism (homomorphic for any quantum circuits). However, Yu et al. (Phys Rev A 90:050303, 2014) proved a negative result: Assume interaction is not allowed, it is impossible to construct perfectly secure QFHE scheme. So this article focuses on non-interactive and perfectly secure QHE scheme with loose requirement, e.g., quasi-compactness. This article defines encrypted gate, which is denoted by EG[U]:|α⟩→(a,b),Enca,b(U|α⟩)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$EG[U]:|\alpha \rangle \rightarrow \left( (a,b),Enc_{a,b}(U|\alpha \rangle )\right) $$\end{document}. We present a gate-teleportation-based two-party computation scheme for EG[U], where one party gives arbitrary quantum state |α⟩\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|\alpha \rangle $$\end{document} as input and obtains the encrypted U-computing result Enca,b(U|α⟩)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Enc_{a,b}(U|\alpha \rangle )$$\end{document}, and the other party obtains the random bits a, b. Based on EG[Px](x∈{0,1})\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$EG[P^x](x\in \{0,1\})$$\end{document}, we propose a method to remove the P-error generated in the homomorphic evaluation of T/T†\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T/T^\dagger $$\end{document}-gate. Using this method, we design two non-interactive and perfectly secure QHE schemes named GT and VGT. Both of them are F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {F}}$$\end{document}-homomorphic and quasi-compact (the decryption complexity depends on the T/T†\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T/T^\dagger $$\end{document}-gate complexity). Assume F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {F}}$$\end{document}-homomorphism, non-interaction and perfect security are necessary properties, the quasi-compactness is proved to be bounded by Ω(M)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varOmega (M)$$\end{document}, where M is the total number of T/T†\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T/T^\dagger $$\end{document}-gates in the evaluated circuit. We prove VGT is M-quasi-compact and reaches the optimal bound. According to our QHE schemes, the decryption would be inefficient when the evaluated circuit contains exponential number of T/T†\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T/T^\dagger $$\end{document}-gates. Thus, our schemes are suitable for homomorphic evaluation of any quantum circuit with low T/T†\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T/T^\dagger $$\end{document}-gate complexity, such as any polynomial-size quantum circuit or any quantum circuit with polynomial number of T/T†\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T/T^\dagger $$\end{document}-gates.