# Quantum Fully Homomorphic Encryption by Integrating Pauli One-time Pad with Quaternions

Guangsheng Ma1,2 and Hongbo Li1,3

1Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China
2School of Mathematics and Physics, North China Electric Power University, Beijing, China
3University of Chinese Academy of Sciences, Beijing, China

### Abstract

Quantum fully homomorphic encryption (QFHE) allows to evaluate quantum circuits on encrypted data. We present a novel QFHE scheme, which extends Pauli one-time pad encryption by relying on the quaternion representation of SU(2). With the scheme, evaluating 1-qubit gates is more efficient, and evaluating general quantum circuits is polynomially improved in asymptotic complexity.
Technically, a new encrypted multi-bit control technique is proposed, which allows to perform any 1-qubit gate whose parameters are given in the encrypted form. With this technique, we establish a conversion between the new encryption and previous Pauli one-time pad encryption, bridging our QFHE scheme with previous ones. Also, this technique is useful for private quantum circuit evaluation.
The security of the scheme relies on the hardness of the underlying quantum capable FHE scheme, and the latter sets its security on the learning with errors problem and the circular security assumption.

### ► References

[1] Zvika Brakerski. Quantum FHE (almost) as secure as classical''. In Annual International Cryptology Conference. Pages 67–95. Springer (2018). url: doi.org/​10.1007/​978-3-319-96878-0_3.
https:/​/​doi.org/​10.1007/​978-3-319-96878-0_3

[2] Anne Broadbent and Stacey Jeffery. Quantum homomorphic encryption for circuits of low T-gate complexity''. In Annual Cryptology Conference. Pages 609–629. Springer (2015). url: doi.org/​10.1007/​978-3-662-48000-7_30.
https:/​/​doi.org/​10.1007/​978-3-662-48000-7_30

[3] Andrew M. Childs. Secure assisted quantum computation''. Quantum Information & Computation 5, 456–466 (2005). url: doi.org/​10.26421/​QIC5.6.
https:/​/​doi.org/​10.26421/​QIC5.6

[4] Yfke Dulek, Christian Schaffner, and Florian Speelman. Quantum homomorphic encryption for polynomial-sized circuits''. In Annual International Cryptology Conference. Pages 3–32. Springer (2016). url: doi.org/​10.1007/​978-3-662-53015-3_1.
https:/​/​doi.org/​10.1007/​978-3-662-53015-3_1

[5] Urmila Mahadev. Classical homomorphic encryption for quantum circuits''. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). Pages 332–338. IEEE (2018). url: doi.org/​10.1109/​FOCS.2018.00039.
https:/​/​doi.org/​10.1109/​FOCS.2018.00039

[6] Yingkai Ouyang, Si-Hui Tan, and Joseph F Fitzsimons. Quantum homomorphic encryption from quantum codes''. Physical Review A 98, 042334 (2018). url: doi.org/​10.1103/​PhysRevA.98.042334.
https:/​/​doi.org/​10.1103/​PhysRevA.98.042334

[7] Li Yu, Carlos A Pérez-Delgado, and Joseph F Fitzsimons. Limitations on information-theoretically-secure quantum homomorphic encryption''. Physical Review A 90, 050303 (2014). url: doi.org/​10.1103/​PhysRevA.90.050303.
https:/​/​doi.org/​10.1103/​PhysRevA.90.050303

[8] Andris Ambainis, Michele Mosca, Alain Tapp, and Ronald De Wolf. Private quantum channels''. In Proceedings 41st Annual Symposium on Foundations of Computer Science. Pages 547–553. IEEE (2000). url: doi.org/​10.1109/​SFCS.2000.892142.
https:/​/​doi.org/​10.1109/​SFCS.2000.892142

[9] Brent A. Mode. Efficient quantum approximation : examining the efficiency of select universal gate sets in approximating 1-qubit quantum gates''. url: ir.library.louisville.edu/​cgi/​viewcontent.cgi?article=1210&context=honors.
https:/​/​ir.library.louisville.edu/​cgi/​viewcontent.cgi?article=1210&context=honors

[10] Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic encryption for arithmetic of approximate numbers''. In International Conference on the Theory and Application of Cryptology and Information Security. Pages 409–437. Springer (2017). url: doi.org/​10.1007/​978-3-319-70694-8_15.
https:/​/​doi.org/​10.1007/​978-3-319-70694-8_15

[11] Payman Mohassel and Saeed Sadeghian. How to hide circuits in MPC an efficient framework for private function evaluation''. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Pages 557–574. Springer (2013). url: doi.org/​10.1007/​978-3-642-38348-9_33.
https:/​/​doi.org/​10.1007/​978-3-642-38348-9_33

[12] Payman Mohassel, Saeed Sadeghian, and Nigel P. Smart. Actively secure private function evaluation''. In International Conference on the Theory and Application of Cryptology and Information Security. Pages 486–505. Springer (2014). url: doi.org/​10.1007/​978-3-662-45608-8_26.
https:/​/​doi.org/​10.1007/​978-3-662-45608-8_26

[13] Orestis Chardouvelis, Nico Döttling, and Giulio Malavolta. Rate-1 quantum fully homomorphic encryption''. In Theory of Cryptography Conference. Pages 149–176. Springer (2021). url: doi.org/​10.1007/​978-3-030-90459-3_6.
https:/​/​doi.org/​10.1007/​978-3-030-90459-3_6

[14] Christopher M. Dawson and Michael A. Nielsen. The Solovay-Kitaev algorithm'' (2005). url: doi.org/​10.48550/​arXiv.quant-ph/​0505030.
https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​0505030
arXiv:quant-ph/0505030

[15] Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. Practical approximation of single-qubit unitaries by single-qubit quantum Clifford and T circuits''. IEEE Transactions on Computers 65, 161–172 (2015). url: doi.org/​10.1109/​TC.2015.2409842.
https:/​/​doi.org/​10.1109/​TC.2015.2409842

[16] Harsha Prahladh. Hellinger  distance''. url: http:/​/​www.tcs.tifr.res.in/​%7Eprahladh/​teaching/​2011-12/​comm/​lectures/​l12.pdf.

[17] Mark M. Wilde. Quantum information theory''. Cambridge University Press. (2013). url: doi.org/​10.1017/​CBO9781139525343.
https:/​/​doi.org/​10.1017/​CBO9781139525343

[18] Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information''. Cambridge University Press. (2000). url: doi.org/​10.1017/​CBO9780511976667.
https:/​/​doi.org/​10.1017/​CBO9780511976667

[19] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography''. Journal of the ACM (JACM) 56, 1–40 (2009). url: doi.org/​10.1145/​1568318.1568324.
https:/​/​doi.org/​10.1145/​1568318.1568324

[20] Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model''. Journal of the ACM (JACM) 50, 506–519 (2003). url: doi.org/​10.1145/​792538.792543.
https:/​/​doi.org/​10.1145/​792538.792543

[21] Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien Stehlé. Classical hardness of learning with errors''. In Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (STOC). Pages 575–584. (2013). url: doi.org/​10.1145/​2488608.2488680.
https:/​/​doi.org/​10.1145/​2488608.2488680

[22] Chris Peikert. Public-key cryptosystems from the worst-case shortest vector problem''. In Proceedings of the forty-first annual ACM symposium on Theory of Computing (STOC). Pages 333–342. (2009). url: doi.org/​10.1145/​1536414.1536461.
https:/​/​doi.org/​10.1145/​1536414.1536461

[23] Chris Peikert, Oded Regev, and Noah Stephens-Davidowitz. Pseudorandomness of ring-LWE for any ring and modulus''. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC). Pages 461–473. (2017). url: doi.org/​10.1145/​3055399.3055489.
https:/​/​doi.org/​10.1145/​3055399.3055489

[24] Daniele Micciancio and Chris Peikert. Trapdoors for lattices: Simpler, tighter, faster, smaller''. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Pages 700–718. Springer (2012). url: doi.org/​10.1007/​978-3-642-29011-4_41.
https:/​/​doi.org/​10.1007/​978-3-642-29011-4_41

[25] Craig Gentry. A fully homomorphic encryption scheme''. PhD thesis. Stanford university. (2009).

[26] Craig Gentry. Fully homomorphic encryption using ideal lattices''. In Proceedings of the forty-first annual ACM symposium on Theory of Computing (STOC). Pages 169–178. (2009). url: doi.org/​10.1145/​1536414.1536440.
https:/​/​doi.org/​10.1145/​1536414.1536440

[27] S. P. Walborn, P. H. Souto Ribeiro, L. Davidovich, F. Mintert, and A. Buchleitner. Experimental determination of entanglement with a single measurement''. Nature 440, 1022–1024 (2006). url: doi.org/​10.1038/​nature04627.
https:/​/​doi.org/​10.1038/​nature04627

[28] Dorit Aharonov. A simple proof that Toffoli and Hadamard are quantum universal''. arXiv: quant-ph/​0301040 (2003). url: doi.org/​10.48550/​arXiv.quant-ph/​0301040.
https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​0301040
arXiv:quant-ph/0301040

[29] A. Yu Kitaev. Quantum computations: algorithms and error correction''. Russian Mathematical Surveys 52, 1191 (1997). url: doi.org/​10.1070/​RM1997v052n06ABEH002155.
https:/​/​doi.org/​10.1070/​RM1997v052n06ABEH002155

[30] Yunseong Nam, Yuan Su, and Dmitri Maslov. Approximate quantum Fourier transform with O$(n log (n))$ T gates''. NPJ Quantum Information 6, 1–6 (2020). url: doi.org/​10.1038/​s41534-020-0257-5.
https:/​/​doi.org/​10.1038/​s41534-020-0257-5

[31] Jung Hee Cheon, Dongwoo Kim, Duhyeong Kim, Hun Hee Lee, and Keewoo Lee. Numerical method for comparison on homomorphically encrypted numbers''. In International Conference on the Theory and Application of Cryptology and Information Security. Pages 415–445. Springer (2019). url: doi.org/​10.1007/​978-3-030-34621-8_15.
https:/​/​doi.org/​10.1007/​978-3-030-34621-8_15

[32] Wikipedia. Taylor's theorem in complex analysis''. url: en.wikipedia.org/​w/​index.php?title=Taylor%27s_theorem&oldid=1123522853. (accessed: 22.04.2021).
https:/​/​en.wikipedia.org/​w/​index.php?title=Taylor%27s_theorem&oldid=1123522853

### Cited by

On Crossref's cited-by service no data on citing works was found (last attempt 2023-02-07 14:48:47). On SAO/NASA ADS no data on citing works was found (last attempt 2023-02-07 14:48:47).