Computers, Materials & Continua DOI:10.32604/cmc.2022.029125 | |

Article |

A Secure Multiparty Quantum Homomorphic Encryption Scheme

1Information Security Center, State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing, 100876, China

2School of Information Science and Technology, North China University of Technology, Beijing, 100144, China

3Advanced Cryptography and System Security Key Laboratory of Sichuan Province, Sichuan, 610025, China

4Quantum Technology Lab & Applied Mechanics Group, University of Milan, Milan, 20133, Italy

5Department of Computer Science, Faculty of Engineering and Physical Sciences, University of Surrey, Guildford, Surrey, GU2 7XH, United Kingdom

6Huawei Technologies Co. Ltd, Shenzhen, 518129, China

*Corresponding Author: Xiu-Bo Chen. Email: flyover100@163.com

Received: 25 February 2022; Accepted: 22 April 2022

Abstract: The significant advantage of the quantum homomorphic encryption scheme is to ensure the perfect security of quantum private data. In this paper, a novel secure multiparty quantum homomorphic encryption scheme is proposed, which can complete arbitrary quantum computation on the private data of multiple clients without decryption by an almost dishonest server. Firstly, each client obtains a secure encryption key through the measurement device independent quantum key distribution protocol and encrypts the private data by using the encryption operator and key. Secondly, with the help of the almost dishonest server, the non-maximally entangled states are pre-shared between the client and the server to correct errors in the homomorphic evaluation of T gates, so as to realize universal quantum circuit evaluation on encrypted data. Thirdly, from the perspective of the application scenario of secure multi-party computation, this work is based on the probabilistic quantum homomorphic encryption scheme, allowing multiple parties to delegate the server to perform the secure homomorphic evaluation. The operation and the permission to access the data performed by the client and the server are clearly pointed out. Finally, a concrete security analysis shows that the proposed multiparty quantum homomorphic encryption scheme can securely resist outside and inside attacks.

Keywords: Quantum homomorphic encryption; secure multiparty computation; almost dishonest server; security

Classical homomorphic encryption (HE) is focused on the related notion of homomorphism in the field of abstract algebra. Its central idea is to take advantage of homomorphism as a preserving function to ensure the security of private data. Under this premise, the operations on the ciphertext are outsourced to a server with powerful computing capabilities. The idea of homomorphic encryption first emerged in 1978 when the professional term was called privacy homomorphism that was proposed by Rivest et al. [1] at that time. Since then, an open question in the international cryptographic circle is how to construct a fully homomorphic encryption scheme capable of arbitrary function transformation of the ciphertext. Until 2009, The first fully homomorphic encryption (FHE) algorithm came into view which was presented by Gentry [2]. It inspired the rapid development of the FHE scheme in the following decades. According to the FHE schemes based on difficult problems, it is mainly divided into the problem of approximate greatest common divisor over the integers [3–5] and learning with errors problem based on lattices [6–8].

The development and progress of quantum computers provide access to accelerate the calculation based on the properties of quantum mechanics. The application of quantum computation in quantum communication network [9,10] and quantum blockchain [11–13] will be practical and feasible in the future, and in the meantime, the concept of quantum homomorphic encryption (QHE) has also been proposed. Similar to the homomorphic characteristics used in classical HE, QHE also completes homomorphic quantum computations without decryption by the server. The ciphertext after the homomorphic quantum computation is the same as a valid ciphertext after performing the same quantum computation on the original plaintext. The difference is that all the above processes are completed in the background of quantum data and quantum computation. In the beginning, a large amount of research work [14–16] addressed the task of secure implementation of delegated quantum computation on the encrypted data, but the interaction requirements of the above schemes lead to the workload of the client is proportional to the size of the homomorphic evaluation circuit. The non-interactive schemes have been given in [17,18], but neither of them is suitable for universal quantum computation. The QHE scheme described in [17] realized a restricted class of quantum computation on the encoded input quantum state through the boson-sampling model under the premise of satisfying some information-theoretic security. Reference [18] used the group theoretical insights to make the scheme support quantum computing tasks including and extending beyond the boson-sampling model with improved security. In 2014, Yu et al. [19] proved that achieving a certain balance between security and compactness in a quantum fully homomorphic encryption (QFHE) scheme would be the optimal trivial scheme. In other words, if a QFHE scheme with information-theoretic security is to meet the non-interactivity and realize universal quantum computation, it will inevitably lead to exponential storage overhead. This allows more research to dive into the study of whether a QFHE scheme can be achieved under the condition of relaxing some properties and requirements. In 2015, Broadbent et al. [20] weakened the security level to computational security and gave the definitions of QHE and QFHE. They proposed two QHE schemes, which were suitable for the homomorphic evaluation of the quantum circuit containing a finite number of T gates. Subsequently, Dulek et al. [21] improved the quantum circuit to the size of any polynomial level and presented a QFHE scheme under the computational security by using auxiliary quantum gadgets. In 2018, Ouyang et al. [22] used quantum codes to encode plaintext and evaluation circuits in parallel under the entropy security model to realize universal quantum computation. In the same year, Mahadev [23] utilized the classical leveled FHE scheme to encapsulate the key and constructed a quantum leveled FHE under the assumption of cyclic security.

At the same time, the functionality and application scenarios of the QHE scheme have also been extensively studied. In 2017, Alagic et al. [24] proposed a verifiable leveled QHE scheme by using classical computing logs, proving that homomorphic evaluation results of the QHE scheme can be verified in a non-interactive way. In 2019, Chen et al. [25] combined the characteristics of the QHE algorithm with the quantum secret sharing scheme to achieve a flexible and variable number of honest evaluators to perform homomorphic evaluation operations in sequence. Later, Liang [26] corrected errors occurring in the homomorphic quantum computation of T gates based on the quantum technology of gate teleportation and proposed a QHE scheme that allows quantum circuits with arbitrary polynomial size. Reference [27,28] completed the Grover retrieval scheme on secret superposition state based on QHE in 2020. Besides, there are some experimental studies [29–31] on QHE schemes.

At present, the existing schemes [20,21,24,26,27] apply the maximally entangled state to remove the P error, that is, an arbitrary quantum calculation can be achieved through the maximally entangled channel. However, the quantum system is generally open in the real physical environment. When coupled with the realistic environment, the maximally entangled state is affected by the ambient noise, resulting in the problem of degenerating into a non-maximally entangled state. Therefore, our scheme uses non-maximally entangled states as quantum resources to assist solve the error problem in the evaluation of T gate. While ensuring the correct execution of the scheme, it reduces the requirements for quantum channels in the previous QHE scheme. In order to improve the universality of the QHE scheme, we will study the QHE scheme with multiple clients and extend its application scenarios to secure multi-party computation. In this paper, we propose a novel secure multi-party QHE scheme by introducing pre-shared non-maximally entangled states that are relatively well prepared between the client and the server as an auxiliary resource. The error correction of the T gate evaluation is completed and the universal quantum circuit evaluation on the quantum ciphertext can be achieved. It is possible for multiple clients to send computation requests to an almost dishonest server in parallel, and guarantee the perfect security of private data.

We will give the symbols and concepts that are essential for the construction of the scheme. For a more detailed introduction to quantum computation, refer to Nielsen et al. [32].

Our work will employ the universal quantum circuit model, denoted as

The entanglement appearance between quantum states is a property of the quantum composite system described in quantum mechanics. Bell state, as the representative of the two-qubit entangled state, is in the maximally entangled state, also known as the EPR (Einstein-Podolsky-Rosen) pair. It consists of four entangled states as follows,

We define

A density matrix

This property is allowed to construct a quantum one-time pad (QOTP) and qubits are encrypted in a quantum cryptography scheme. The Pauli key used only once will be randomly generated. Only with the correct key can the quantum ciphertext be decrypted to obtain valid information. So, even if an attacker intercepts the complete quantum ciphertext, it is meaningless to ensure the security of privacy information.

2.2 Quantum Homomorphic Encryption

Quantum homomorphic encryption refers to that the client encrypts the quantum state and sends it to the server. After the server is delegated to perform quantum evaluation operations on the quantum ciphertext, the calculation result is returned to the client for decryption. And the intended result of the quantum evaluation operations on the original quantum state is finally obtained. The concepts introduced in this section include QHE, correctness, compactness, and QFHE. For a more in-depth understanding of the above definitions, refer to Broadbent et al. [20].

Definition 1 (Quantum homomorphic encryption). We now provide the definition of the QHE scheme in the asymmetric key setting. It consists of the following algorithms: key generation, encryption, evaluation, and decryption.

(i) Key Generation.

(ii) Encryption.

(iii) Homomorphic Evaluation.

(iv) Decryption.

Definition 2 (Correctness). A QHE scheme is correct if for any quantum circuit

where

Definition 3 (Compactness). For any quantum circuit

Definition 4 (Quantum fully homomorphic encryption). If a QHE scheme is correct and compact for all quantum circuits formed by a set of universal quantum gates, the scheme is a QFHE scheme.

3 Secure Multiparty Quantum Homomorphic Encryption Scheme

In this section, we first introduce the probabilistic QHE scheme that uses the non-maximally entangled state to accomplish T gate evaluation. Based on Zhang et al.’s result [33], the main idea of the scheme is described in Section 3.1 which is helpful for our proposal. Then, in Section 3.2, we propose our secure multiparty quantum homomorphic encryption (MQHE) scheme in detail, combined with the evaluation method of T gate, to realize the universal quantum circuit evaluation for multiple clients.

3.1 T gate Evaluation in Quantum Homomorphic Encryption

As a non-Clifford gate, T gate does not have the property of commuting with the Pauli group. When it is applied to the encrypted quantum state, we will get

At first, the client prepares a quantum state

Similarly, if

Then the first and third particles in the

Without loss of generality, we take the

At last, the auxiliary particle

3.2 Multiparty Quantum Homomorphic Encryption Scheme

In this subsection, we propose a secure MQHE scheme, which allows multiple clients to complete the evaluation of the universal quantum circuit on encrypted private data in parallel with the assistance of the almost dishonest server. In particular, the quantum circuit includes Clifford gates and a finite number of non-Clifford gates. The almost dishonest server in our scheme is the one with great computing capability, which will loyally perform quantum computations. It will not cooperate with clients to launch a collusion attack but will take the initiative to steal clients’ private data. At the same time, a trusted key center is introduced and responsible for the execution of the key generation algorithm, and updating the encryption key to obtain the decryption key.

Next, we will specifically describe our MQHE scheme. Assume that there are

The complete process of our scheme is illustrated by step as follows.

S1. Key generation.

S2. Encryption.

S3. Homomorphic evaluation.

S4. Decryption.

(a) If

(b) If

(c) If

(d) If

(e) If

In the end,

Through the description of the above scheme, we propose a novel MQHE scheme, which enables any number of clients to request homomorphic quantum computations from the almost dishonest but computationally capable server in parallel. The server implements homomorphic evaluation of the universal quantum circuit including a limited number of T gate while ensuring the perfect security of private data. In short, our scheme completes the secure homomorphic evaluation of multi-party quantum private data in a non-interactive way and guarantees key security through the trusted key center. From the perspective of simplifying the experimental implementation, we choose the pre-shared non-maximally entangled state to solve the difficult problems and guarantee the correctness of the proposed scheme.

This section will discuss the security of our MQHE scheme in different aspects, mainly from the outside attack and inside attack. An outside attack means that an external eavesdropper attempts to grab the private data. An inside attack means that an attack initiated by the client, server, and key center.

On the one hand, this scheme uses the MDI-QKD protocol to ensure the security of the key for possible security loopholes when the server performs measurement during the key distribution process. On the other hand, the QOTP technology is utilized to encrypt private data, thereby minimizing the risk of data leakage to guarantee the security of private data. According to the four stages of the QHE scheme, we specifically analyze and prove that our scheme can resist outside attacks.

Initially, the security of the key generation stage is analyzed. In our scheme, the distribution of quantum keys adopts the MDI-QKD protocol. It can resist the attack of the external eavesdropper Eve that has been rigorously proved in [34]. The device independence means that the security of the protocol does not depend on the actual measurement device, which is consistent with the security assumption that the server is almost dishonest in the proposed scheme. When the server sends the results of Bell state measurement to

Then, in the encryption stage, each client has only access to their original private data and uses the secure key as the Pauli key to encrypt the private data in combination with the QOTP method. It is an asymmetric encryption method that uses random keys makes the encrypted quantum ciphertext in a totally mixed state. The effective information cannot be obtained by Eve without the correct key so that the security of private data is guaranteed in the transmission process. Now, we prove the aforesaid conclusion.

Proof. Define

It can be seen that the quantum plaintext is mapped to the same output density matrix

Finally, in the decryption stage, the trusted key center renews the decryption key according to the secure encryption key obtained in S1, the quantum gate used in the quantum circuit in S2, and the key update rule given in S4. The decryption key is sent to

Through the discussion in this section, our MQHE scheme can securely against outside attacks, thereby protecting any information about private data and keys from being leaked.

Clients, servers, and trusted key centers are the main participants in the scheme. If an inside attack is launched, it may pose a serious security threat to the cryptographic scheme. Without loss of generality, suppose there exists a dishonest client

As an almost dishonest third-party server, there is data exchange with the client, and it can faithfully complete the homomorphic evaluation of the universal quantum circuit without colluding with the malicious client. Unfortunately, the server will evade eavesdropping detection and try to grab the private data. In our scheme, both the encrypted data and the evaluated data are in a completely mixed state and have information-theoretic security. If the server eavesdrops on the quantum channel in the transmission, it will be treated as an outside attacker and unable to extract meaningful information by the means of the outside attack. In QOTP, all keys are randomized and used only once. The security of the key distribution is guaranteed by the MDI-QKD protocol. The replication and retransmission of the quantum state by a malicious server will introduce errors with a certain probability and may be monitored in the post-processing step of the key. In other words, the server cannot infer the value of the key.

The trusted key center, Charlie, introduced in our scheme, is responsible for cooperating with each client to realize the secure distribution of the encryption key, and updating the correct decryption key depending on the quantum circuit and key update rules. Charlie will honestly abide by the requirements of the MQHE scheme, and will not disclose the encryption and decryption keys to anyone other than

In summary, it is demonstrated that the proposed MQHE scheme is good at security in terms of private data and keys, and has outstanding performance in resisting outside and inside attacks.

This paper presents a secure MQHE scheme. On the one hand, the non-maximally entangled state is used to tackle the computational issues of T gate evaluation that relaxes the technical requirements for implementation of the universal quantum circuit evaluation. On the other hand, drawing on the idea of secure multi-party quantum computation, we expand the application scenario of the QHE scheme and propose a workable scheme that multiple clients request a homomorphic evaluation from the third-party server in parallel, reflecting the significant advantages of QHE in protecting private data. In addition, the trusted key center is employed to ensure the security of key distribution and the encryption and decryption keys, so that the scheme performs well in terms of correctness and security. What’s more, we hope that the constructed scheme can inspire the application of the QHE scheme in secure multi-party computation scenarios, making it possible to transmit large-scale quantum information safely and efficiently.

Funding Statement: This work was supported by the Open Fund of Advanced Cryptography and System Security Key Laboratory of Sichuan Province (Grant No. SKLACSS-202101), NSFC (Grant Nos. 62176273, 61962009), the Foundation of Guizhou Provincial Key Laboratory of Public Big Data (No. 2019BDKFJJ010, 2019BDKFJJ014), the Fundamental Re-search Funds for Beijing Municipal Commission of Education, Beijing Urban Governance Re-search Base of North China University of Technology, the Natural Science Foundation of Inner Mongolia (2021MS06006), Baotou Kundulun District Science and technology plan project (YF2020013), and Inner Mongolia discipline inspection and supervision big data laboratory open project fund (IMDBD2020020).

Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.

1. R. L. Rivest, L. Adleman and M. L. Dertouzos, “On data banks and privacy homomorphisms,” Foundations of Secure Computation, vol. 4, no. 11, pp. 169–180, 1978. [Google Scholar]

2. C. Gentry, “A fully homomorphic encryption scheme, Ph.D. thesis, Stanford University, American,” 2009. [Google Scholar]

3. M. Van Dijk, C. Gentry, S. S.Halevi and V. Vaikuntanathan, “Fully homomorphic encryption over the integers,” in Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques, Berlin, Heidelberg, Springer, pp. 24–43, 2010. [Google Scholar]

4. J. S. Coron, A. Mandal, D. Naccache and M. Tibouchi, “Fully homomorphic encryption over the integers with shorter public keys,” in Annual Cryptology Conf., Berlin, Heidelberg, Springer, pp. 487–504, 2011. [Google Scholar]

5. J. S. Coron, T. Lepoint and M. Tibouchi, “Scale-invariant fully homomorphic encryption over the integers,” in Int. Workshop on Public Key Cryptography, Berlin, Heidelberg, Springer, pp. 311–328, 2014. [Google Scholar]

6. Z. Brakerski and V. Vaikuntanathan, “Efficient fully homomorphic encryption from (standard) LWE,” SIAM Journal on Computing, vol. 43, no. 2, pp. 831–871, 2014. [Google Scholar]

7. Z. Brakerski, C. Gentry and V. Vaikuntanathan, “(Leveled) fully homomorphic encryption without bootstrapping,” ACM Transactions on Computation Theory (TOCT), vol. 6, no. 3, pp. 1–36, 2014. [Google Scholar]

8. Z. Brakerski, “Fully homomorphic encryption without modulus switching from classical GapSVP,” in Annual Cryptology Conf., Berlin, Heidelberg, Springer, pp. 868–886, 2012. [Google Scholar]

9. G. Xu, K. Xiao, Z. P. Li, X. X. Niu and M. Ryan, “Controlled secure direct communication protocol via the three-qubit partially entangled set of states,” Computers, Materials & Continua, vol. 58, no. 3, pp. 809–827, 2019. [Google Scholar]

10. S. Y. Chen, G. Xu, X. B. Chen, H. Ahmad and Y. L. Chen, “Measurement-based quantum repeater network coding,” Intelligent Automation & Soft Computing, vol. 30, no. 1, pp. 273–284, 2021. [Google Scholar]

11. H. L. Chen, G. Xu, Y. L. Chen, X. B. Chen, Y. X. Yang et al., “Cipherchain: A secure and efficient ciphertext blockchain via mPECK,” Journal of Quantum Computing, vol. 2, no. 1, pp. 57–83, 2020. [Google Scholar]

12. J. S. Zhang, G. Xu, X. B. Chen, H. Ahmad, X. Liu et al., “Towards privacy-preserving cloud storage: a blockchain approach,” Computers, Materials & Continua, vol. 69, no. 3, pp. 2903–2916, 2021. [Google Scholar]

13. G. Xu, Y. Cao, S. Xu, K. Xiao, X. Liu et al., “A novel post-quantum blind signature for log system in blockchain,” Computer Systems Science and Engineering, vol. 41, no. 3, pp. 945–958, 2022. [Google Scholar]

14. M. Liang, “Symmetric quantum fully homomorphic encryption with perfect security,” Quantum Information Processing, vol. 12, no. 12, pp. 3675–3687, 2013. [Google Scholar]

15. M. Liang, “Quantum fully homomorphic encryption scheme based on universal quantum circuit,” Quantum Information Processing, vol. 14, no. 8, pp. 2749–2759, 2015. [Google Scholar]

16. K. A. G. Fisher, A. Broadbent, L. K. Shalm, Z. Yan, J. Lavoie et al., “Quantum computing on encrypted data,” Nature Communications, vol. 5, no. 1, pp. 1–7, 2014. [Google Scholar]

17. P. P. Rohde, J. F. Fitzsimons and A. Gilchrist, “Quantum walks with encrypted data,” Physical Review Letters, vol. 109, no. 15, pp. 150501, 2012. [Google Scholar]

18. S. H. Tan, J. A. Kettlewell, Y. Ouyang, L. Chen and J. F. Fitzsimons, “A quantum approach to homomorphic encryption,” Scientific Reports, vol. 6, no. 1, pp. 33467, 2016. [Google Scholar]

19. L. Yu, C. A. Pérez-Delgado and J. F. Fitzsimons, “Limitations on information-theoretically-secure quantum homomorphic encryption,” Physical Review A, vol. 90, no. 5, pp. 50303, 2014. [Google Scholar]

20. A. Broadbent and S. Jeffery, “Quantum homomorphic encryption for circuits of low T-gate complexity,” in Annual Cryptology Conf., Berlin, Heidelberg, Springer, pp. 609–629, 2015. [Google Scholar]

21. Y. Dulek, C. Schaffner and F. Speelman, “Quantum homomorphic encryption for polynomial-sized circuits,” in Annual Int. Cryptology Conf., Berlin, Heidelberg, Springer, pp. 3–32, 2016. [Google Scholar]

22. Y. Ouyang, S. H. Tan and J. F. Fitzsimons, “Quantum homomorphic encryption from quantum codes,” Physical Review A, vol. 98, no. 4, pp. 42334, 2018. [Google Scholar]

23. U. Mahadev, “Classical homomorphic encryption for quantum circuits,” in 2018 IEEE 59th Annual Symp. on Foundations of Computer Science (FOCS), Paris, France, IEEE, pp. 3332–3338, 2018. [Google Scholar]

24. G. Alagic, Y. Dulek, C. Schaffner and F. Speelman, “Quantum fully homomorphic encryption with verification,” in Int. Conf. on the Theory and Application of Cryptology and Information Security, Hong Kong, China, Springer, pp. 438–467, 2017. [Google Scholar]

25. X. B. Chen, Y. R. Sun, G. Xu and Y. X. Yang, “Quantum homomorphic encryption scheme with flexible number of evaluator based on (k, n)-threshold quantum state sharing,” Information Sciences, vol. 501, no. 1, pp. 172–181, 2019. [Google Scholar]

26. M. Liang, “Teleportation-based quantum homomorphic encryption scheme with quasi-compactness and perfect security,” Quantum Information Processing, vol. 19, no. 1, pp. 1–32, 2020. [Google Scholar]

27. C. Gong, J. Du, Z. Dong, Z. Guo, A. Gani et al., “Grover algorithm-based quantum homomorphic encryption ciphertext retrieval scheme in quantum cloud computing,” Quantum Information Processing, vol. 19, no. 3, pp. 1–17, 2020. [Google Scholar]

28. Q. Zhou, S. Lu, Y. Cui, L. Li and J. Sun, “Quantum search on encrypted data based on quantum homomorphic encryption,” Scientific Reports, vol. 10, no. 1, pp. 1–11, 2020. [Google Scholar]

29. K. Marshall, C. S. Jacobsen, C. Schäfermeier, T. Gehring, C. Weedbrook et al., “Continuous-variable quantum computing on encrypted data,” Nature Communications, vol. 7, no. 1, pp. 1–7, 2016. [Google Scholar]

30. W. K. Tham, H. Ferretti, K. Bonsma-Fisher, A. Brodutch, B. C. Sanders et al., “Experimental demonstration of quantum fully homomorphic encryption with application in a two-party secure protocol,” Physical Review X, vol. 10, no. 1, pp. 11038, 2020. [Google Scholar]

31. J. Zeuner, I. Pitsios, S. H. Tan, A. N. Sharma, J. F. Fitzsimons et al., “Fitzsimons et al., “Experimental quantum homomorphic encryption,” npj Quantum Information, vol. 7, no. 1, pp. 1–6, 2021. [Google Scholar]

32. M. A. Nielsen and I. Chuang, “Quantum computation and quantum information,” American Journal of Physics, vol. 70, no. 5, pp. 558–559, 2002. [Google Scholar]

33. J. W. Zhang, X. B. Chen, G. Xu and Y. X. Yang, “Universal quantum circuit evaluation on encrypted data using probabilistic quantum homomorphic encryption scheme,” Chinese Physics B, vol. 30, no. 7, pp. 70309, 2021. [Google Scholar]

34. D. Gottesman, H. K. Lo, N. Lutkenhaus and J. Preskill, “Security of quantum key distribution with imperfect devices,” in Int. Symp. on Information Theory, Chicago, IL, USA, pp. 136, 2004. [Google Scholar]

This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. |