Full-Blind Delegating Private Quantum Computation

Wenjie Liu Zhenyu Chen Jinsuo LiuZhaofeng Su and Lianhua Chi

Abstract: The delegating private quantum computation (DQC) protocol with the universal quantum gate set was firstly proposed by Broadbent et al. [Broadbent (2015)], and then Tan et al. [Tan and Zhou (2017)] tried to put forward a half-blind DQC protocol (HDQC) with another universal set .However, the decryption circuit of Toffoli gate (i.e. T) is a little redundant, and Tan et al.’s protocol [Tan and Zhou (2017)] exists the information leak. In addition, both of these two protocols just focus on the blindness of data (i.e. the client’s input and output),but do not consider the blindness of computation (i.e. the delegated quantum operation).For solving these problems, we propose a full-blind DQC protocol (FDQC) with quantum gate set , where the desirable delegated quantum operation, one of , is replaced by a fixed sequence to make the computation blind, and the decryption circuit of Toffoli gate is also optimized. Analysis shows that our protocol can not only correctly perform any delegated quantum computation, but also holds the characteristics of data blindness and computation blindness.

Keywords: Delegating private quantum computation, universal quantum gate set, full-blind,Toffoli gate, circuit optimization.

1 Introduction

Blind quantum computation (BQC) is a novel model of quantum computation, where the client with limited quantum resources can perform quantum computation by delegating the computation to an untrusted quantum server, and the privacy of the client can still be guaranteed. As BQC provides a convenient and safe way to access the quantum computation, it could potentially be an ideal model for the quantum application in the early days of “quantum computer era”.

BQC can be generally divided into two categories: one is the measurement-based blind quantum computation (MBQC), and the other is the circuit-based blind quantum computation (CBQC). In MBQC, measurement is the main driving force of computation,which follows the principle of “entangle-measure-correct”, and a certain number of quantum qubits are entangled to form a standard graph state. To be specific, it first prepares a certain graph state according to the requirements of desirable computation, and measures the first qubit according to the computation. Then the measurement result will decide the following measurement basis which is known as “correction”. In 2009,Broadbent et al. [Broadbent, Fitzsimons and Kashefi (2008)] proposed the first MBQC protocol, where the client generates the rotated single photons, and he/she sends them to the server to build the brickwork state that can implement the specific quantum computation. Since then, some other MBQC protocols were proposed [Morimae (2012a);Morimae and Fujii (2012b); Li, Chan, Wu et al. (2014); Xu and Wang (2014); Morimae,Dunjko and Kashefi (2015); Kong, Li, Wu et al. (2016)].

Different from MBQC, CBQC is based on the traditional circuit, which can be composed of all kinds of quantum gates. In 2005, Childs [Childs (2005)] proposed the first CBQC protocol based on the ideal of encrypting data with quantum one-time pad [Ambainis,Mosca, Tapp et al. (2000); Boykin and Roychowdhury (2003)]. However, the client must possess quantum memory and the ability to execute the quantum SWAP operation. And in 2006, Arrighi et al. [Arrighi and Salvail (2006)] proposed another CBQC protocol for the calculation of certain functions, i.e. not the universal quantum computation, and it requires Alice to prepare and measure multi-qubit entangled states. Since then, some other CBQC protocols [Aharonov, Ben-Or and Eban (2008); Broadbent, Gutoski and Stebila (2013)] have been proposed. Recently, the concept of delegating private quantum computation has been proposed, which belongs to the CBQC model. In 2015, Broadbent[Broadbent (2015)] proposed the first delegating private quantum computation (DQC)protocol with the universal quantum set. In one way, they relax the requirements of fully homomorphic encryption [Rivest, Adleman and Dertouzos(1978); Gentry (2009)] by allowing interaction. But at the same time, they strengthen the requirements by asking for information-theoretic security. Later, Tan et al. [Tan and Zhou (2017)] proposed a half-blind DQC protocol (HDQC) with another universal set, where “half-blind” means that the server cannot learn anything about client’s input and output (also referred as the blindness of data), but client’s computation are exposed to the server, i.e. the blindness of computation cannot be guaranteed.Obviously, the half-blindness of quantum computation is undesirable, because the privacy of computation is also an important aspect of information security.

Compared with previous work, the main contribution of our work is to propose a full-blind DQC protocol (FDQC) with universal gate set, where the desirable delegated quantum operation, one of, is replaced by a fixed sequenceto make the computation blind. In addition, we also optimize the decryption circuit ofToffoligate, and also solve the problem of information leak in Tan et al.’s protocol [Tan and Zhou (2017)]. The rest of this paper is organized as follows. In the following section, we briefly review DQC and HDQC. A full-blind delegating private quantum computation protocol with universal gate setis proposed in Section 3, and the correctness and full-blindness are discussed in Section 4. Finally, conclusion is drawn in the last section.

2 Review of DQC and HDQC

2.1 Review of DQC

DQC enables an almost-classical client to delegate the execution of any quantum computation to a remote server without exposing his information. The brief process of DQC [Broadbent (2015)] is as follows (also shown in Fig. 1).

Quantum encryption:Client uses Pauli operationsandto encrypt quantum state, and then obtainsand are the encryption keys randomly selected from, after that he sendsto the server QC.

Quantum computation:QC implements the specific quantum computation (certainunitary operation ) on the encrypted quantum state.

Quantum decryption:The server returns the output stateto the client. Then the client decrypts the output state:ding to the decryption rules, and finally gets the quantum computation result.

Figure 1: The main process of DQC model

As we know, the quantum gate setis universal [Nielsen and Chuang (2011)], which means itcan be used to construct arbitrary quantum computation(i.e. arbitrary unitary operation . These quantum gates have following properties,

And their encryption and decryption circuits are shown in Fig. 2.

2.2 Review of HDQC

Figure 2: The encryption and decryption circuits for the universal quantum gate set [Fisher, Broadbent, Shalm et al. (2013)]

Figure 3: The encryption and decryption circuit of Toffoli gate. The quantum operations in the dotted box denote that they are performed in the server side

However, there are two flaws in Tan et al.’s HDQC protocol [Tan and Zhou (2017)]. First,the protocol is half-blind, i.e. it only guarantees the blindness of the data. Although the server cannot get any information about the data, the desirable computation can be obtained by the server because the delegated operations are exposed to the server. Second,the protocol exists the information leak. To be specific, if the server is performing theToffoligate, the client may delegate the server to perform some correction operations.Referring to the decryption circuit in Fig. 3, the corrections are related with the encryption keys, i.e. theCZ,SWAPandCNOTcorrections represent the encryption keysf=1,c=1and (a=1,c=1), respectively. Since the server knows all the delegated quantum operations, he can deduce the corresponding encryption key based on the above rules. For example, in the HDQC process forToffoligate, if the client asks the server to perform aCZoperation between the first and second qubit, then the secret keyf=1will be revealed to the server.

3 Full-blind delegating private quantum computation

3.1 The FDQC protocol

Suppose that the client delegates the server to implement a certain quantum computation which is composed of quantum operations (i.e. quantum gates in), the procedures of FDQC are given as follows.

1. The client generates a 9-qubit sequence S which consists of ancillary qubits and message qubits. And then he/she divides the sequence into five subsequences(The first subsequence consists of the first qubit, the second subsequenceconsists of the second qubit, the third subsequenceconsists of the third and fourth qubits, the fourth subsequenceconsists of the fifth and sixth qubits, and the fifth subsequenceconsists of the remaining three qubits). It should be noted that the five subsequences,,,andare prepared for the fixed ordered operations.

2. According to the delegated quantum operation, the client chooses one ofas the message part (also called the message subsequence), and the other subsequences as the ancillary part (which will be used to confuse the delegated operation). Forexample, if the delegated quantum operation isTgate, then he/she chooses as the message part, and the remainderis the ancillary part.

3. The client encrypts every qubitin message subsequence by the unitary operationwhereare the encryption keys randomly chosen by him,. After that, he sends the sequenceSto the server.

4. The server performs the operationson the qubits in the subsequence, and returns the output qubits to the client.

5. The client extracts the message qubits from the output qubits according to hisselection in Step 1, and decrypts them byith the decryption keys (the decryption keys and decryption process will be in detail discussed in the next subsection). If the delegated quantum operation isTand the encryption keysf=1,c=1ora=1, then the client will perform the corrections according to the following rule: iff=1, then correction operation isCZbetween the first and second qubits; ifa=1, then correction operation isCNOTbetween the first and third qubits; ifc=1, then correction operation isCNOTbetween the second and third qubits. Then the client delegates the server to perform the correction operation as the above steps.

6. The client and the server repeat the above steps until all the delegated quantum operations are completed.

For ease of understanding, we suppose the client wants to delegate the operation to the server, and Fig. 4. describes the whole delegation process ofU.

In the proposed FDQC protocol, the fixed order operationsare all performed in each round, which will confuse the delegated quantum operation and finally achieve the computation blindness.

3.2 The encryption and decryption of universal quantum gate set

Figure 4: The delegation process of U = PH in our protocol.is ancillary qubit randomly generated by the client. The operations in dotted box are the desirable operations

Figure 5: The encryption and decryption process for H

Figure 6: The encryption and decryption process for P

Figure 7: The encryption and decryption process for CNOT

Figure 8: The encryption and decryption process for T (i.e. Toffoli gate)

Since the encryption and decryption circuits ofare given in Broadbent[Broadbent (2015)] and Tan et al. [Tan and Zhou (2017)], here we skip them and focus on the description ofToffoligate.In our study, we simplify the encryption and decryption circuit ofToffoli(shown in Fig. 9).

Figure 9: The encryption and decryption circuit of Toffoli gate. Here, the two-qubit operations in dotted box are viewed as correction

4 Correctness and security analysis

4.1 Correctness analysis

In this section, the correctness of the proposed protocol forToffoligate is verified. Since the correctness of the processes forH,PandCNOTis already verified in Broadbent et al.[Broadbent (2015); Tan and Zhou (2017)]. Then the only remaining gate isToffoligate.Assume that the encryption secret keys for the encryption progress ofToffoligate are . The verification procedure is given as follows. First, assuming that

Given that the correctness of encryption and decryption processes ofH,P,T,CNOTandCZhave been shown, correctness of the proposed FDQC protocol is obvious: after each round delegation, the client adjusts his secret keys according to Figs. 5-8. So that he/she can perform the decryption correctly. Because each process of itself is correct, so the proposed FDQC protocol implements the quantum computation as desired.

4.2 Security analysis

In the client-server scenario, the security of the proposed protocol contains many aspects, but the main problem is the security of the data and the computation, as well as the blindness of the message qubits and the delegated quantum operations. The blindness of the message qubits and the delegated quantum operations are discussed in the following parts.

4.2.1 The blindness of data

Considering the encryption and decryption processes ofH,P,CNOTandCZare the same as Broadbent’s DQC protocol, then the processes of the four gates provide the same level of security as the original one, which is perfectly (information-theoretic) secure. Therefore, we will only focus on the security of encrypted qubits which is performing on the encryption and decryption circuit ofToffoligate. Because the client is not able to perform theCNOTandCZcorrections, then the two operations should be delegated to the server. However, once the server obtains the information of corrections, then the encryption keys of encrypted qubits are exposed (also mentioned in the review of HDQC).

In order to eliminate the particularity of the corrections, the CZ andCNOTcorrections are added into the fixed order of gateswhich is performed in each round delegation. In each round, the server is asked to perform the five unitary operations indistinguishably, therefore there is no mechanism for the server to distinguish the correction operation from the other four operations, so the particularity of the corrections disappears, and the privacy of encryption keys holds. To be specific, suppose that the desired operation is theToffoligate in one round delegation, and the encryption keyf=1, then the client will delegate the server to perform theCZcorrection in the next round delegation. However theCZcorrection is confused by the other four operations,the server is not able to know that the desired operation is theCZcorrection, then the security of encryption key f is guaranteed. Since the encrypted qubit which is performing on the gate set is secure, then the blindness of data is obvious.

4.2.2 The blindness of data

The computation that the client wants to implement can be seen as a desirable circuit which is made up of the delegated quantum operations, therefore the blindness of computation is equivalent to the blindness of the delegated quantum operations. In order to make the delegated quantum operations blind, each operation of the delegated quantum operations is replaced by the fixed order of gates, where theH,P,CNOTandToperations are needed for the universality, and theCZandCNOToperations are needed in the decryption process of certain operation (such as theToffoligate). Client uses ancillary part to confuse the message part, there is no mechanism for the server to distinguish the message part and the ancillary part, so the server is not able to deduce the desired operations,thus computation that the client wants to implement is blind.

Without loss of generality, we take the delegation of quantum computationU=HPas an example. If the client wants to ask the server to perform theUon the encrypted qubit, then the whole produce of FDQC is as follows, he/she firstly generates a 9-qubit sequencewhich consists of ancillary qubits and message qubits, where themessage qubit is in the subsequence(i.e. the message part), and the other four subsequence,,andare the ancillary part. The client sendsto the sever to perform the fixed order of gates. Because the server cannot distinguish the message part from the ancillary part, he/she cannot know that the desired operation which is performed on the message qubit is thePgate. So in this round, the delegated quantum operationPis secure. Then the server sends all the qubits back to the client, the client reconstructs the message part and the ancillary part (the ancillary qubits can be reused)according to the delegated operationHin next round. He/she sends new generated to the server to implement the fixed order of gates again, the server still cannot know that the desired operation is theHgate in this round. Finally, he/she sends all the qubits back to client, and when the computationis done, the client decryptsaccording to the decryption rules. During the process, the server cannot learn anything about client’s desired operations. Thus, the computation is blind.

5 Conclusion

As quantum devices are scarce and expensive, it is not hard to imagine that very few companies or scientific institutions can have a quantum device or a quantum computer in the foreseeable future. It is an impossible mission for the quantum computer to be popularized in the following decades. But the delegating private quantum computation provide a solution, which will enable the ordinary clients with uncomplicated quantum device to perform the quantum computation with unconditional security. Thus delegating quantum computation to the remote server has strong practical and economic motivation.In recent years, quite a lot of delegating private quantum computation protocols have been proposed, but some protocols might exist the design flaws that might cause some security problems. Therefore the improvement of the existing protocols is also an attractive work.

In this study, we pointed out that the decryption circuit ofToffoligate is a little complicated and the information leaking risk exists in HDQC. To solve the problem of protecting the blindness of computation, we propose a full-blind DQC protocol with. In the practical application, the quantum gate setseems more commonly used thanas theToffoligate (i.e.T) is considered to be the basic unit for constructing complex quantum circuits. So the research on DQC withis a meaningful work. In the proposed protocol, although we have optimized the decryption circuit ofToffoligate, it still needs multiple interactions. One of our future work is to further simplify the decryption circuit ofToffoligate, reduce the times of interaction, and even get rid of the interaction.As FDQC can provide a secure “client-server” mode for universal quantum computation,one hand, we can try to use this model to solve some classic security calculation problems. Another important work is to combine DQC with some practical quantum protocols, such as quantum key agreement [Liu, Chen, Ji et al. (2017)], quantum private comparison [Yang and Wen (2009); Liu, Liu, Liu et al. (2014a); Liu, Liu, Chen et al.(2014b); Liu, Liu, Wang et al. (2014c)], quantum sealed-bid Auction [Liu, Wang, Ji et al.(2014d); Liu, Wang, Yuan et al. (2016)], which will be another interesting direction to be further studied. We conclude this paper with an expectation that the work reported here will be realized experimentally and further applied in the daily life.

Acknowledgement:The authors would like to thank the anonymous reviewers and editor for their comments that improved the quality of this paper. This work is supported by the National Nature Science Foundation of China (Grant Nos. 61502101 and 61501247), the Natural Science Foundation of Jiangsu Province, China (Grant No. BK20171458), the Six Talent Peaks Project of Jiangsu Province, China (Grant No. 2015-XXRJ-013), the Natural science Foundation for colleges and universities of Jiangsu Province, China (Grant No.16KJB520030), the Research Innovation Program for College Graduates of Jiangsu Province,China (Grant No. KYCX17_0902), the Practice Innovation Training Program Projects for the Jiangsu College Students (Grant No. 201810300016Z), and the Priority Academic Program Development of Jiangsu Higher Education Institutions (PAPD).