Int J Theor Phys https://doi.org/10.1007/s10773-018-3711-9

Application of Blind Quantum Computation to Two-Party Quantum Computation Zhiyuan Sun1 · Qin Li1

· Fang Yu2 · Wai Hong Chan3

Received: 29 July 2017 / Accepted: 1 March 2018 © Springer Science+Business Media, LLC, part of Springer Nature 2018

Abstract Blind quantum computation (BQC) allows a client who has only limited quantum power to achieve quantum computation with the help of a remote quantum server and still keep the client’s input, output, and algorithm private. Recently, Kashefi and Wallden extended BQC to achieve two-party quantum computation which allows two parties Alice and Bob to perform a joint unitary transform upon their inputs. However, in their protocol Alice has to prepare rotated single qubits and perform Pauli operations, and Bob needs to have a powerful quantum computer. In this work, we also utilize the idea of BQC to put forward an improved two-party quantum computation protocol in which the operations of both Alice and Bob are simplified since Alice only needs to apply Pauli operations and Bob is just required to prepare and encrypt his input qubits. Keywords Blind quantum computation · Two-party quantum computation

1 Introduction Quantum computation uses the principles of quantum mechanics to perform computation. It is widely believed that quantum computation can solve some computational tasks much faster than its classical counterparts [1]. For instance, Shor’s algorithms offer an efficient solution for factoring big integers and solving discrete logarithm problems in polynomial time [2]. Grover’s algorithm provides a quadratic speedup over its best-known classical

 Qin Li

[email protected] 1

College of Information Engineering, Xiangtan University, Xiangtan 411105, China

2

Department of Computer Science, Jinan University, Guangzhou 510632, China

3

Department of Mathematics and Information Technology, The Education University of Hong Kong, Tai Po, New Territories, Hong Kong

Int J Theor Phys

algorithm for searching problems [3]. However, the experimental realization of quantum computation is still a big challenge now. Due to the limitation of current technologies, quantum computers are still in the primary stage and they just allow for several operations on a few qubits. It may be a long way to build large-scale quantum computers. In the future, the first generation quantum computers may be used in the cloud style [4] where only a small number of groups such as governments and huge industries can possess them. Although delegating computing to a remote system may be highly practical and economical, it may cause some security problems [5]. For example, if a client who holds only limited quantum resources wants to perform quantum computation, he may need to delegate his computation to powerful quantum servers in the network and still wants his own data private. Blind quantum computation (BQC) can help him to achieve both goals at the same time. BQC was first proposed by Childs on the basis of circuit model [6]. In this protocol, the client needs quantum memory and the ability to implement the SWAP gate. Then Arrighi and Salvail proposed a BQC protocol which only requires Alice to prepare and measure entangled states [7]. But it only allows for calculating certain classical functions and thus is not universal. Based on the measurement model, Broadbent, Fitzsimons, and Kashefi (BFK) presented the first universal BQC protocol [8], where the client only requires preparing single-qubit states and does not require quantum memory or any quantum computation power. In Ref. [9], the measurement-based quantum computation (MBQC) model is shown to be the same as the circuit model. It can be viewed as a set of classical measurement angles on a highly entangled quantum state to perform quantum computation. Thereafter, various protocols have been proposed based on different models [10–24]. On the one hand, some researchers tried to make the BQC as practical as possible, such as using entanglement swapping to make client just need to access quantum channels [11], using some anti-noise technologies to perform BQC in a noisy environment [12–14], or designing some verification methods to make the client verify her quantum computation efficiently [15, 16]. On the other hand, some of them utilized the BQC to achieve special functions [25–27], such as extending the verifiable BQC protocol [15] to realize a two-party computation protocol [25]. Two-party computation was first introduced by Yao [28] in the form of the millionaire problem where two persons want to compare which of them is richer without revealing their personal fortunes. The quantum version of two-party computation can be described as follows [29]: Alice holds her private input |ρinA , Bob holds |ρinB , and both of them want to perform a unitary transform U on their joint input |ρinA  ⊗ |ρinB  without revealing any information about their input as described in Fig. 1. In Ref. [25], Kashefi and Wallden proposed such a protocol that can allow two users Alice and Bob can receive their own outputs which depend on their inputs. It was called QYao protocol which requires Alice to prepare rotated single qubits and perform the Pauli-X and Z(θ ) operations and requires Bob to have a powerful quantum computer to perform quantum computation. In this work, we design an improved protocol which eases both Alice and Bob’s burden. More specifically, Alice is not required to prepare rotated single qubits and Bob is

Fig. 1 The process of two-party quantum computation

Int J Theor Phys

just required to prepare and encrypt his input qubits by delegating their computation to an untrusted quantum server. The rest of this paper is organized as follows. In Section 2, we briefly review the QYao protocol in Ref. [25]. Section 3 presents our protocol. Section 4 analyzes the security of the proposed protocol and makes a comparison with the QYao protocol. The last section gives a conclusion of this paper.

2 The Review of QYao Protocol Before presenting the main part of our protocol, we first review the QYao protocol. The QYao protocol shows that the measurement-based quantum computation model can be used in two-party quantum computation tasks and provides the idea of our work. Suppose that Alice has her input |A , Bob has input |B , and both of them know the unitary operator U that they wish to compute. Alice has a description of their computation in MBQC using the base graph G. Suppose that the base graph G has three vertices and two edges as described in Fig. 2a. Then Alice maps it to the DT(G) as shown in Fig. 2b. For each vertices vi in G, there is a set of three new vertices Pvi = {p1vi , p2vi , p3vi } in DT(G). Corresponding to each edge e(vi , vj ) that connects vi and vj in G, there is a set of nine edges Ee (Pvi , Pvj ) that connect each of the vertices in Pvi and Pvj [15]. Then, Alice randomly chooses the added qubit from the set {|0, |1} for each Ee to get the DT(G). By using the DT(G), Alice can hide her actual computation graph G (such as the blue one) in three subgraphs which are described in Fig. 2c. For each qubit only Alice knows the initial rotation angles and its dependencies. The base-locations of the inputs and outputs of both parties are public [25]. Then the QYao protocol can be briefly described as follows. Q1 Q2 Q3

Bob encrypts his input using secret keys (mz,i , mx,i ) and then sends to Alice the states Xmx,i Z mz,i |B  for all i∈IB , where IB denotes the specific positions of Bob’s input. Alice prepares all the states of the DT(G) except the computation qubits of Bob’s input. After receiving Bob’s input qubits which are described in step 1, Alice chooses at random xi , θi for each Bob’s input qubit and encrypts them to obtain the  states:X xi Z(θi )X mx,i Z mz,i |B .

Fig. 2 a The base graph G. Assume that the base graph of Alice is described in a and it includes the unitary operation U and Alice’s input qubits. b DT(G). The dotted triple-graph which is mapped from a. Here, for each qubit vi which belongs to base graph G, there is a set of three qubits Pvi which are denoted as circles. For each edge which belongs to base graph G, there is a set of nine added qubits Ae which are denoted as squares. c The colored blue sub-graph is the real computation graph and will be used to perform the computation, and the white/black sub-graph is used to set trap/dummy qubits

Int J Theor Phys

Fig. 3 Bob sends his input (colored in green) to Alice, and Alice mixes it with a trap qubit and a dummy qubit by randomly choosing their locations. So, Bob cannot know which sub-graph is used to perform the quantum computation

Q4

Q5 Q6

Q7

Q8 Q9 Q10 Q11

Alice mixes the computation qubit of the Bob’s input with a dummy qubit and a trap qubit and returns to Bob the three qubits of Bob’s input base-locations using the method shown in Fig. 3. Bob produces the DT(G) state that was specified by Alice. Then, Bob returns to Alice the secret bits (mz,i , mx,i ) for all i of his input. Alice computes xi := xi + mx,i and θi := (−1)mx,i θi + π mz,i and uses these (xi , θi ) for computing the suitable measurement angles δi = φi + θi + π ri like the way in the UBQC protocol in Ref. [8]. On the output stage, Bob chooses pair of secret bits (mx,i , mz,i ) to encrypt each qubit in position i that corresponds to Bob’s output base-locations. Then he   sends to Alice the state X mx,i Z mz,i T rA (U (|A , |B )) and the Alice’s output is T rB (U (|A , |B )). Alice keeps the qubits that correspond to traps and dummies in the final layer of Bob’s output, and returns to Bob the computation qubits of his output. Bob sends to Alice the key (mx,i , mz,i ). Alice checks the traps and returns to Bob the final layer paddings for Bob’s input locations. Bob uses the final paddings to obtain the output.

At the end of this protocol, Alice and Bob obtain the output qubits respectively if this protocol is performed correctly. In this QYao protocol, Alice only requires limited quantum power but Bob needs the ability of performing quantum computation as a fully quantum server.

3 The Proposed Protocol In this section, we propose a protocol which allows two users Alice and Bob with limited quantum power to perform two-party quantum computation with the help of an untrusted quantum server Charlie. In our protocol, Alice needs to prepare {|0, |1} states and perform Pauli-X and Z(θ ) operations and Bob only needs to prepare and encrypt his input qubits. Supposed that Alice and Bob plan to implement the same quantum computation as that in the reviewed QYao protocol [25] and use similar parameters in it. Then inputs of Alice and Bob are |A  and |B  respectively, and both of them want to perform the unitary operator U on them. The detailed steps of our protocol are described as follows.

Int J Theor Phys

Preparation Stage: Charlie prepares a single qubit |+ and sends it to Alice. Once receiving the particle, Alice randomly chooses (a) to perform Z(θi ) on it and sends to Charlie the state | + θi , where θi is randomly selected from S ≡ {kπ/4|k = 0, 1, ..., 7} or (b) to prepares a dummy quantum state selected in {|0, |1} which will be sent to Charlie. D3 They repeat (1)-(2) until the qubits is enough to construct the DT(G). Then Charlie produces the Alice’s initial DT(G) which are specified by Alice via the method described in Fig. 3. D4 Bob encrypts his input |B  using secret keys (mz,j , mx,j ) and then sends to Alice the state X mx,j Z mz,j |B . For simplicity, in the following we just give the case that the input is only one qubit since it can be generalized to multiple qubits trivially. D5 Alice randomly chooses (xj , θj ) for each of the Bob’s input and encrypts it again to D1 D2



obtain the following state: X xj Z(θj )X mx,j Z mz,j |B . D6 Bob prepares a trap qubit state | + θj  = |0 + eiθj |1, where θj is selected randomly from the set S, and sends it to Alice. D7 Alice prepares a dummy qubit and mixes it with Bob’s input qubit and trap qubit. Then, Alice sends the three qubits to Charlie to entangle it in Bob’s input base-locations which are shown in Fig. 3. Computation Stage: D8

D9

In order to avoid the key releasing, Alice and Bob use classical secure oblivious transfer (OT) [30] as a function to compute the suitable measurement angles j δj (mx,j , mz,j ) = φj + ((−1)mx,j +x θj + π mz,j ) + π rj , where (mz,j , mx,j ) and (xj , θj ) are Bob and Alice’s secret key values respectively and φj is a modified angle according to the previous measurement results. Alice and Charlie perform the computation just like the UBQC protocol in Ref. [8] from the step 3. Alice tells the classical information δi to Charlie. Charlie measures the ith qubit in the basis ±|δi  and sends the result to Alice. Through a set of measurements in the DT(G), Alice and Bob can achieve their computation goal U (|A , |B ).

Output Stage: D10

Charlie sends the output qubits to Alice and Bob corresponding to their baselocations respectively. D11 Alice checks her traps qubits and keeps her output T rB (U (|A , |B )). D12 Alice tells Bob the information about which qubit is his output qubit, trap qubit or dummy qubit, and returns to Bob the final layer paddings for their locations. D13 Bob uses the final paddings to check his trap qubit and obtain his output T rA (U (|A , |B )).

4 Security Analysis and Comparisons In this section, we will analyze the security of the proposed protocol and show it will not reveal the information about users’ input and output. Similar to the QYao protocol, we suppose that Alice is a specious (quantum honest-but-curious) [29] user, and Bob and Charlie

Int J Theor Phys

can be fully malicious. The specious adversary must appear to act honestly at any step during the execution of a protocol. It means that he may want to learn some information of the honest party without being detected. In steps D1-D3, Alice prepares rotated single qubits | + θi  by perform the Z(θi ) operations on qubits |+, and only Alice knows their values. Moreover, Alice encrypts Bob’s input and mixes it with a trap qubit and a dummy qubit to hide the input qubits’ positions. Bob cannot know which qubits are used in real computation and which qubits are trap qubits and thus there is no information about Alice’s input that can be revealed. In addition, Bob encrypts his input qubit by using random key (mz,j , mx,j ) in step D4, thus Alice also cannot get any information about Bob’s input. 2. If Charlie does not implement the protocol as being told, he still cannot obtain the private data of both participants. For simplicity, suppose he may try to learn the information of θi , where θi is the rotation angle of Alice’s input qubit |+θi . In step D3, Alice mixes her input qubit with a dummy qubit and a trap qubit and only Alice knows the positions of the three qubits. Thus Charlie’s attack may be detected when he measures a trap qubit and the probability that he escapes from the detection is pf ail ≤ 23 . If Alice has n qubits as her input, the Charlie’s attack can be detected by Alice with the probability p ≥ 1−( 23 )n . Furthermore, Alice can verify the computational result through measuring trap qubits in the output phase. The analysis for Bob is similar to that for Alice. 3. If Bob has collusion with Charlie, they can get (mz,j , mx,j ) and δj . But it is impossible 1.



for them to get something about φj = δj − ((−1)mx,j +xj θj + π mz,j ) − π ri , since they have no information about Alice’s secret key values (xj , θj ). Without knowing φj and the sub-graph used to perform the real computation, Bob and Charlie cannot get any information about Alice’s input and output and thus the proposed protocol can be against Bob and Charlie’s collusion attack. 4. If Alice colludes with Charlie, they can get some information about Bob’s input if they does not mind being caught by Bob. For example, in step D8, if Alice sets φj = θj = rj = 0, then δj = π mz,j and she can get the value of mz,j . But if Alice tries to get Bob’s secret key values through the above method, it will be detected by Bob according to the change of δj and the computation process will be aborted. Moreover, if Bob has n qubits as input, Alice and Charlie only have the probability of 1/2n to get Bob’s input. Thus the proposed protocol can be against Alice and Charlie’s collusion attack to some extent.

In Kashefi et al.’s protocol in Ref. [25], Alice needs the ability to prepare rotated single qubits and implement quantum encryption and Bob needs the ability to perform quantum computation as a fully quantum server. But in our protocol Alice is not required to prepare rotated single qubits and Bob is unnecessary to own a powerful quantum computer. The cost is that an untrusted quantum server is introduced. In addition, both of the QYao protocol and our proposed protocol need Alice to be a specious (quantum honest-but-curious) user and Table 1 Comparisons between the QYao protocol and the proposed protocol QYao protocol [25]

The proposed protocol

generate | + θ ,

generate {|0, |1},

apply Pauli-X and Z(θ)

apply Pauli-X and Z(θ)

Bob’s quantum power

own fully quantum capability

prepare input qubit,

An untrusted Server

unnecessary

Alice’s quantum power

apply Pauli-X and Z(θ) necessary

Int J Theor Phys

require the users Alice and Bob to have the ability to perform Pauli operations. The specific comparisons are shown in Table 1.

5 Conclusions In conclusion, we have applied BQC to propose an improved protocol of two-party quantum computation which simplifies both two parties’ quantum operations compared with those in the original two-party quantum computation protocol in Ref. [25]. Furthermore, we also have shown that the proposed protocol can be against untrusted Charlie, malicious Bob, and specious Alice. Finally, our protocol may be modified to execute in a noisy environment by using some anti-noise methods when transmitting qubits from Alice or Bob to Charlie in the preparation stage, such as using quantum state amplification [31, 32], entanglement purification [33, 34], and entanglement concentration [35, 36] between two servers. However, the problem about how to deal with a malicious Alice has not been addressed and it will be future work. Acknowledgements We would like to thank Zhulin Li, Chengdong Liu, and Yu Peng for useful discussion and suggestion. This work was supported by the Joint Funds of the National Natural Science Foundation of China and China General Technology Research Institute (Grant No. U1736113), and the Hunan Provincial Natural Science Foundation of China (Grant No. 2018JJ2403).

References 1. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press (2010) 2. Shor, P.W.: In: Proceedings of the 35th Annual IEEE Symposium on the Foundations of Computer Science, pp. 124–134 (1994) 3. Grover, L.K.: Phys. Rev. Lett. 79, 325 (1997) 4. Morimae, T., Fujii, K.: Phys. Rev. A 87, 050301(R) (2013) 5. Fitzsimons, J.F.: npj Quant. Inf. 3, 23 (2017) 6. Childs, A.M.: Quant. Inf. Comput. 5, 456 (2005) 7. Arrighi, P., Salvail, L.: Int. J. Quant. Inf. 04, 883 (2006) 8. Broadbent, A., Fitzsimons, J., Kashefi, E.: In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 517–526 (2009) 9. Raussendorf, R., Briegel, H.J.: Phys. Rev. Lett. 86, 5188 (2001) 10. Morimae, T., Fujii, K.: Phys. Rev. Lett. 111, 020502 (2013) 11. Li, Q., Chan, W.H., Wu, C., Wen, Z.: Phys. Rev. A 89, 040302(R) (2014) 12. Sheng, Y.B., Zhou, L.: Sci. Rep. 5, 7815 (2015) 13. Takeuchi, Y., Fujii, K., Ikuta, R., Yamamoto, T., Imoto, N.: Phys. Rev. A 93, 052307 (2016) 14. Sheng, Y.B., Zhou, L.: Available at arXiv:1609.08902 (2016) 15. Kashefi, E., Wallden, P.: Available at arXiv:1510.07408 (2015) 16. Fitzsimons, J.F., Kashefi, E.: Phys. Rev. A 96, 012303 (2017) 17. Dunjko, V., Kashefi, E., Leverrier, A.: Phys. Rev. Lett. 108, 200502 (2012) 18. Morimae, T., Fujii, K.: Nat. Commun. 3, 251 (2012) 19. Li, Q., Li, Z., Chan, W.H., Zhang, S., Liu, C.: Phys. Lett. A 382, 938 (2018) 20. Brennen, G.K., Miyake, A.: Phys. Rev. Lett. 101, 010502 (2008) 21. Morimae, T.: Phys. Rev. Lett. 109, 230502 (2012) 22. Sueki, T., Koshiba, T., Morimae, T.: Phys. Rev. A 87, 060301 (2013) 23. Mantri, A., P´erez-Delgado, C.A., Fitzsimons, J.F.: Phys. Rev. Lett. 111, 230502 (2013) 24. Kong, X., Li, Q., Wu, C., Yu, F., He, J., Sun, Z.: Int. J. Theor. Phys. 55, 3001 (2016) 25. Kashefi, E., Wallden, P.: Cryptography 1, 6 (2017) 26. Kashefi, E., Pappa, A.: Available at arXiv:1606.09200 (2016) 27. Sheng, Y.B., Zhou, L.: Sci. Bull. 62, 1025 (2017)

Int J Theor Phys 28. Yao, A.C.: In: Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, pp. 160–164 (1982) 29. Dupuis, F., Nielsen, J.B., Salvail, L.: In: Advances in Cryptology-Crypto 2010, pp. 685–706 (2010) 30. Naor, M., Pinkas, B.: In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pp. 245–254 (1999) 31. Osorio, C.I., Bruno, N., Sangouard, N., Zbinden, H., Gisin, N., Thew, R.T.: Phys. Rev. A 86, 023815 (2012) 32. Zhou, L., Sheng, Y.B.: Laser Phys. Lett. 12, 045203 (2015) 33. Zwerger, M., Briegel, H.J., Dur, W.: Phys. Rev. A 90, 012314 (2014) 34. Zhou, L., Sheng, Y.B.: Sci. Rep. 6, 28813 (2016) 35. Du, F.F., Deng, F.G.: Science china physics. Mech. Astron. 58, 040303 (2015) 36. Sheng, Y.B., Pan, J., Guo, R., Zhou, L., Wang, L.: Science china physics. Mech. Astron. 58, 060301 (2015)