Quantum private comparison over noisy channels

Abstract

Quantum private comparison (QPC) allows us to protect private information during its comparison. In the past, various three-party quantum protocols have been proposed that claim to work well under noisy conditions. Here, we tackle the problem of QPC under noise. We analyze the EPR-based protocol under depolarizing noise, bit flip and phase flip noise. We show how noise affects the robustness of the EPR-based protocol. We then present a straightforward protocol based on CSS codes to perform QPC which is robust against noise and secure under general attacks.

1 Introduction

Quantum ideas have led to surprising developments in the field of secure communication. The most startling example is that of cryptography, where quantum ideas have revolutionized the field. While most classical cryptography schemes depend on computational complexity for their security, quantum cryptographic schemes [1–4] offer security based on physical laws. There have been further developments such as quantum secure direct communication [5–7], quantum secret sharing [8–10], quantum authentication and quantum signatures [11–14].

Secure multi-party computation allows several distrustful parties to jointly compute a function while keeping their inputs private [15] and is of fundamental importance in secure communication. A particular instance is to compute the equality function with just two parties [15]. Quantum private comparison (QPC) aims to do the above computation without sharing the party’s private information. This is in contrast to quantum key distribution (QKD) which provides a secure way to share private information.

Let Alice and Bob have private information $M_{\mathrm{A}}$ and $M_{\mathrm{B}}$, respectively. QPC involves the computation of the function $f(M_{\mathrm{A}},M_{\mathrm{B}})$ such that

$$\begin{aligned} f(M_{\mathrm{A}},M_{\mathrm{B}}) = {\left\{ \begin{array}{ll} 0 &{}\quad \text {if}\,\,M_{\mathrm{A}} = M_{\mathrm{B}}\\ 1 &{}\quad \text {if}\,\,M_{\mathrm{A}} \ne M_{\mathrm{B}} \end{array}\right. } \end{aligned}$$

(1)

Furthermore, at the end of the protocol, Alice and Bob do not wish the other party to learn anything about their information, apart from what can be inferred logically from $f(M_{\mathrm{A}},M_{\mathrm{B}})$. Lo [16] pointed out that the above function $f(M_{\mathrm{A}},M_{\mathrm{B}})$ cannot be computed securely by two parties alone. Hence, a third party is needed to facilitate the process. One might think that a three-party QPC is trivial. Both Alice and Bob can convey their information to a trusted third party (Charlie) and he can tell Alice and Bob the outcome of the function f. The problem here is a little different; Alice and Bob do not wish to disclose their information to anyone, including Charlie and yet wish to compare their private information. In fact, they do not want to transmit the information at all. In the past, several three-party quantum protocols have been proposed [17–21]. They impose the following restriction on the third party:

• (a) Charlie tries to learn information about Alice and Bob’s input while being restricted to faithfully follow the protocol. In other words, he is semi-honest or honest but curious.

• (b) Charlie may know the positions at which $M_{\mathrm{A}}$ and $M_{\mathrm{B}}$ differ, but not the actual bit values.

Further, these protocols assume that all channels are noiseless or remain silent on this aspect. We show that under the proposed restrictions, we can build a protocol to achieve QPC even under noisy conditions. A slight modification of our protocol allows us to relax the condition, that Charlie is honest. That is, he may not cooperate with Alice and Bob and return false results. We also show how our protocol is more efficient than similar quantum protocols [21].

It is hard to build perfect quantum channels, and hence, we must build protocols that are robust against noise. We choose a specific protocol described by Tseng et al. [18] and add noise to its channels. We consider depolarizing noise, bit flip and phase flip noise. We show that the protocol as such, is not robust under noise. We note that three-party QPC involves transmission of correlated keys between the parties and that under noise, these correlations are altered. Quantum error correction helps overcome the effects of noise. We note that quantum error correction and quantum cryptography have a deep connection [22]. Exploiting this connection, we use the CSS quantum error correction scheme [23] to transmit correlated keys to relevant parties under noisy conditions in a secure manner. This allows us to perform three-party QPC under noisy conditions. Further, by repeated use of our protocol and through cooperation between Alice and Bob, any dishonesty on the part of Charlie can also be detected.

2 EPR-based QPC protocol and noise

We review the EPR-based QPC protocol given in [18]. Alice and Bob have n-bit strings $M_{\mathrm{A}}$ and $M_{\mathrm{B}}$, respectively. They want to compare their information with the help of a semi-honest third party called Charlie. Let Alice, Bob, and Charlie be connected by noiseless quantum channels that can be eavesdropped upon and classical channels that can be eavesdropped upon but not altered. For each qubit, we consider the computational basis $\vert 0 \rangle$ and $\vert 1 \rangle$ and define the rotated basis state as $\vert + \rangle =\frac{1}{\sqrt{2}} (\vert 0 \rangle + \vert 1 \rangle )$ and $\vert - \rangle =\frac{1}{\sqrt{2}} (\vert 0 \rangle - \vert 1 \rangle )$. For pairs of qubits, the four Bell states are defined as

$$\begin{aligned} |\phi ^{\pm }\rangle = \frac{|00\rangle \pm |11\rangle }{\sqrt{2}}, \quad |\psi ^{\pm }\rangle = \frac{|01\rangle \pm |10\rangle }{\sqrt{2}}. \end{aligned}$$

(2)

Using these resources over the quantum channels and classical communication over the classical channels, the secure QPC protocol proceeds as follows:

Protocol 1

• 1. Charlie prepares a random n-bit string $C_T$. For each bit of $C_T$, he prepares a quantum state. If the bit is 0, then he prepares one of the states from $|\phi ^{\pm }\rangle$ (it does not matter which). Otherwise, he prepares one of the states from $|\psi ^{\pm }\rangle$. Sequence $T_{\mathrm{A}}$ consists of the first half of each of these entangled pairs, while $T_{\mathrm{B}}$ consists of the second halves.

• 2. Charlie prepares two sets of decoys $D_{\mathrm{A}}$ and $D_{\mathrm{B}}$ randomly in the states: $|0\rangle , |1\rangle , |+\rangle$ and $|-\rangle$. Charlie randomly interleaves $D_{\mathrm{A}}$ with $T_{\mathrm{A}}$ and $D_{\mathrm{B}}$ with $T_{\mathrm{B}}$ to form $S_{\mathrm{A}}$ and $S_{\mathrm{B}}$, which are then sent to Alice and Bob respectively.

• 3. Upon receipt of the complete sequences $S_{\mathrm{A}}$ and $S_{\mathrm{B}}$, Alice and Bob signal Charlie to disclose the positions and the basis ($\{|0 \rangle , |1 \rangle \}$ or $\{ |- \rangle , |+ \rangle \}$) for measuring the decoys.

• 4. Alice and Bob measure the decoys in the appropriate basis and consult over a classical channel to check for eavesdroppers. If the error rate is more than a predetermined rate then they abort the protocol, else they proceed.

• 5. Alice and Bob measure the non-decoy particles in the Z basis to obtain bit strings $R_{\mathrm{A}}$ and $R_{\mathrm{B}}$ respectively. Note that each of $R_{\mathrm{A}}$ and $R_{\mathrm{B}}$ are uniformly random while $R_{\mathrm{A}} \oplus R_{\mathrm{B}} = C_T$.

• 6. Alice and Bob calculate $C_{\mathrm{A}} = M_{\mathrm{A}} \oplus R_{\mathrm{A}}$ and $C_{\mathrm{B}} = M_{\mathrm{B}} \oplus R_{\mathrm{B}}$. They cooperate to calculate $C= C_{\mathrm{A}} \oplus C_{\mathrm{B}}$ and send it to Charlie.

• 7. Charlie computes $R_c = C \oplus C_T$. $R_c$ has a single nonzero entry if and only if $M_{\mathrm{A}} \ne M_{\mathrm{B}}$, in which case Charlie outputs 1, otherwise he outputs 0.

It is not hard to see that in the absence of noise and eavesdropping, the protocol computes the function $f(M_{\mathrm{A}},M_{\mathrm{B}})$ with certainty. We note that if an eavesdropper (Eve) passes undetected, then the output of the protocol can be different from $f(M_{\mathrm{A}},M_{\mathrm{B}})$ because Eve can tamper with the non-decoy particles (she may cause $R_{\mathrm{A}} \oplus R_{\mathrm{B}} \ne C_T$) and make the protocol malfunction. It has been shown that the above protocol is secure against certain insider and outsider attacks [18] and hence computes $f(M_{\mathrm{A}},M_{\mathrm{B}})$ with very high probability.

2.1 One-qubit noisy channels

In the QPC protocol described above, perfect (noiseless) single- qubit quantum channels between Alice, Bob, and Charlie have been employed. In any real situation, noise can act on these channels in a number of ways. Therefore, we need to consider noisy one-qubit channels instead of noiseless channels and explore the possibility of carrying out QPC over these noisy channels. We begin by describing the noisy channels and then figure out their effect on the EPR-based QPC protocol.

The bit flip channel with error probability $1-p$ is defined through its action on a one-qubit density operator $\rho$ via the action of the bit flip gate X as

$$\begin{aligned} \mathcal {F}(\rho ) = (1-p) X \rho X^{\dag } + p \rho . \end{aligned}$$

(3)

Similarly, the phase flip channel with error probability $1-p$ is described through the action of the phase flip gate Z as

$$\begin{aligned} \mathcal {G}(\rho ) = (1-p) Z \rho Z^{\dag } + p \rho . \end{aligned}$$

(4)

The depolarizing channel with error probability p is

$$\begin{aligned} \mathcal {H}(\rho ) = (1-p)\rho + \frac{p}{3}\left( X \rho X^{\dag } + Y \rho Y^{\dag } + Z \rho Z^{\dag }\right) . \end{aligned}$$

(5)

The above equation admits the interpretation that the state is acted upon by each Pauli operator with probability $\frac{ p}{3}$ and remains unchanged with probability $1-p$.

2.2 QPC and depolarizing channels

Let both the channels between Alice and Charlie (AC) and between Bob and Charlie (BC) suffer from depolarizing noise. If the error represented by the Pauli matrix $\sigma _{\mathrm{A}}$ acts on the AC channel and the error represented by $\sigma _{\mathrm{B}}$ affects the BC channel, then we call the combined error $\sigma _{\mathrm{A}} \sigma _{\mathrm{B}}$. From Eq. (5), we see that under depolarizing noise the channel acts such that each Pauli matrix acts on the qubit with equal probability $\frac{p}{3}$. Since both the channels AC and BC are independent the errors act independently. Hence, the probability for an $X_{\mathrm{A}} X_{\mathrm{B}}$ error is $\frac{p}{3} \cdot \frac{p}{3}$. If an error acts such that it takes the state $|\phi ^{\pm }\rangle$ to the state $|\psi ^{\pm } \rangle$ or vice-versa then the protocol will return an incorrect answer. This happens because the flipping of a correlated to an anti-correlated state and vice-versa makes the string $C_T$ an unfaithful record of the positions at which $R_{\mathrm{A}}$ and $R_{\mathrm{B}}$ differ. After the error has acted, $C_T \ne C'_T$ where

$$\begin{aligned} C'_T \equiv R_{\mathrm{A}} \oplus R_{\mathrm{B}} \end{aligned}$$

(6)

So in step 7 of Protocol 1, Charlie gets $R_c = (C_T \oplus C'_T) \oplus (M_{\mathrm{A}} \oplus M_{\mathrm{B}})$ instead of $R_c = M_{\mathrm{A}} \oplus M_{\mathrm{B}}$.

Under the action of depolarizing noise mentioned in Eq. (5), the probability that the state changes from $|\phi ^{\pm }\rangle$ to $|\psi ^{\pm }\rangle$ or viceversa is $r = \frac{4p}{3}(1-\frac{2p}{3})$, which means that the probability that $C_T$ and $C'_T$ differ at a given position is r. Even if there is a difference at a single position in $C_T$ and $C'_T$, the protocol will give wrong results. Let n be the length of the strings and $P(C_T = C'_T)$ the probability that $C_T = C'_T$. It is straightforward to see that

$$\begin{aligned} P\left( C_T \ne C'_T\right)= & {} 1 - P\left( C_T = C'_T\right) \nonumber \\= & {} 1-(1-r)^n \end{aligned}$$

(7)

Hence, the protocol [18] is not robust against any amount of depolarizing noise. For large n and small r, the error is linear in r.

2.3 Bit flip and phase flip channels and QPC

Consider bit flip and phase flip noise in channels AC and BC. Suppose bit flip (3) acts with probability p and phase flip (4) with probability q. The combined action of the error is given by

$$\begin{aligned} \mathcal {F} \circ \mathcal {G}(\rho )= & {} \mathcal {G} \circ \mathcal {F}(\rho ) \nonumber \\= & {} (1-q)pX\rho X + (1-p)qZ\rho Z + pq Y \rho Y \nonumber \\&+\,(1-q)(1-p)\rho . \end{aligned}$$

(8)

Equation (8) gives the total action of noise on each channel. Let the length of $C_T$ and $C'_T$ be n, then

$$\begin{aligned} P(C_T \ne C'_T) = 1-(1-2p(1-p))^n. \end{aligned}$$

(9)

Hence the protocol [18] is robust against phase flip noise but not bit flip noise. For large n and small p, the error is linear in p.

We see that due to depolarizing noise and bit flip noise in the communication channels between Alice (Bob) and Charlie, the protocol returns incorrect results. This is because noise alters the quantum state being sent and consequently the string $R_{\mathrm{A}}$ and $R_{\mathrm{B}}$. This alteration results in $C_T$ (the string with Charlie) becoming an unfaithful record of the correlations between $R_{\mathrm{A}}$ and $R_{\mathrm{B}}$. In general, channels are noisy and any protocol fit for implementation must be robust against noise. Hence we need to design protocols that work even under noisy conditions.

3 CSS code-based protocol

In order to perform three-party QPC under noise, it is necessary to preserve the information encoded in the quantum states being sent by Charlie to Alice (Bob). This will ensure that $C_T$ remains a faithful record of the correlations. One way to achieve this is through error correction on the quantum states being sent to convey $R_{\mathrm{A}}$ and $R_{\mathrm{B}}$. We utilize CSS codes to perform error correction [23]. We note that these codes have a deep connection with QKD [22].

We propose a protocol for QPC that is robust under noise and completely secure from attacks. The basic idea is to use the CSS codes to securely transfer a known key from Charlie to Alice and Bob. This allows the QPC to work perfectly under noise as long as the bit (phase) error rate is under an acceptable limit.

3.1 CSS codes

We review the CSS codes [23, 24] and the protocol for using CSS codes to perform a secure key distribution of a known random key.

Suppose $C_1$ and $C_2$ are $[n,k_1]$ and $[n,k_2]$ classical linear codes such that $\{0\} \subset C_2 \subset C_1 \subset \mathbb {F}^{n}_2, C_1$ and $C_2^T$ both correct t errors. Then $\hbox {CSS}(C_1,C_2)$ is an $[n, k_1 - k_2]$ quantum error-correcting code capable of correcting t-qubit errors. For $x \in C_1$, we define a code state

$$\begin{aligned} |x+C_2 \rangle \equiv \frac{1}{\sqrt{|C_2|}}\sum _{y \in C_2} |x \oplus y \rangle \end{aligned}$$

(10)

where $\oplus$ is summation modulo 2. If $x,x'$ belong to the same coset in $C_2$, i.e., $x-x' = y' \in C_2$, then they define the same code state, and hence the total number of distinct code states is the number of cosets of $C_2$ in $C_1, |C_1|/|C_2| = 2^{k_1-k_2}$. Each code state can be used to encode a distinct n-bit classical string. This can then be exchanged between interested parties.

The code state can get affected by noise in the channel, which we must be able to correct. It is sufficient to write the corrupted code state as

$$\begin{aligned} \frac{1}{\sqrt{|C_2|}}\sum _{y \in C_2} (-1)^{(x+y)\cdot e_2}|x \oplus y \oplus e_1 \rangle \end{aligned}$$

(11)

where $e_1$ is the n-bit string with a nonzero entry only at positions where a bit flip has occurred and $e_2$ is a similar n bit string for phase flips. By correcting both these kind of errors, we can correct any kind of error [23, 24]. In order to detect and correct errors, we consider $\sigma _{a(k)}$ the Pauli matrix acting on the kth bit, where $a(k) \in \{x,y,z\}$. The operator $\sigma ^{[l]}_{a}$ is defined as

$$\begin{aligned} \sigma ^{[l]}_{a} = \sigma ^{l_1}_{a(1)} \oplus \sigma ^{l_2}_{a(2)} \oplus \cdots \oplus \sigma ^{l_n}_{a(n)} \end{aligned}$$

(12)

l is an n-bit string and its ith entry is $l_i$ that takes values from $\{0,1\}$. By definition, $\sigma ^{0}_{a(k)} = \mathbb {I}$. Note that eigenvalues of $\sigma _{a(k)}$ are $\pm 1$.

In classical error correction, if F is a parity check matrix for a code M, an error y affecting the code word p giving $p'= p + y$ has syndrome $Fp' = Fy$ ($Fp=0$ by definition). This syndrome is used to determine the most likely error y. Note that the $m{\text {th}}$ entry of the column vector Fy is $f_m \cdot p' \mod 2$, where $f_m$ is the $m{\text {th}}$ row in F.

For correcting the quantum state in Eq. (11), we employ a measurement protocol along similar lines. Let $H_1$ be the parity check matrix for $C_1$ and $H_2$ for $C^{T}_2$ (the dual code of $C_2$). If l is the ith row of $H_1$, then we determine the ith column entry for the bit flip error syndrome $H_1\cdot e_1$ by measuring $\sigma ^{[l]}_{z}$ with the understanding that the eigenvalue $1 (-1)$ is mapped to 0 (1). Thus by measuring $\sigma ^{[l]}_{z}$ for each row $l \in H_1$, we obtain the full syndrome. The $i{\text {th}}$ column entry for the phase flip error syndrome $H_2\,\cdot \,e_2$ is similarly obtained by measuring $\sigma ^{[l']}_{x}$ where $l'$ is the $i{\text {th}}$ row of $H_2$. From these syndromes, we can accurately get back $e_1$ and $e_2$ using classical linear coding theory as long as $wt(e_1) \le t$ and $wt(e_2) \le t$ respectively. We then correct the corrupted state and retrieve the encoded state

$$\begin{aligned} \frac{1}{\sqrt{|C_2|}}\sum _{y \in C_2} |x \oplus y \rangle \end{aligned}$$

(13)

A generalized $\hbox {CSS}(C_1,C_2)$ code for any two n-bit strings x and z can be defined as

$$\begin{aligned} |v+C_2 \rangle \equiv \frac{1}{\sqrt{|C_2|}}\sum _{w \in C_2} (-1)^{z\cdot w} |v \oplus x \oplus w \rangle \quad v \in C_1 \end{aligned}$$

(14)

We may use these code states. Let $s\equiv (x,z)$ then we denote the quantum code with the above code states as $Q_{s}$. For $x=0$ and $z=0 Q_{s}$ reduces to $\hbox {CSS}(C_1,C_2)$. If we measure $\sigma ^{[l]}_{z}$($l \in H_1$) and $\sigma _{x}^{l'}$ ($l' \in H_2$) on code state (14), then we will obtain syndromes corresponding to $H_1x$ and $H_2z$, respectively. If there was a bit flip error $e_1$ and a phase flip error $e_2$ on the code state (14), then our syndrome measurements would be corresponding to $H_1(x+e_1)$ and $H_2(z+e_2)$. We can recover the error with the understanding that we must subtract x and z to retrieve the $e_1$ and $e_2$, respectively. If we perform syndrome measurements on any state $|\psi \rangle$ and obtain that the syndrome are both null vectors, then we can conclude $|\psi \rangle = |v+C_2 \rangle \; v \in C_1$ for some v. The syndrome measurement projects the state $|\psi \rangle$ into the subspace spanned by $|v+C_2 \rangle , \; v \in C_1$. Alternatively, if we obtain syndromes corresponding to $H_1.x$ and $H_2$. z for bit flip and phase flip, respectively, then we may conclude that $|\psi \rangle$ has been projected onto a subspace spanned by code states of $Q_{s},\; s=(x,z)$.

3.2 The protocol

Let us first describe the CSS-based protocol for sharing a known randomly chosen secret key. Let us assume that a secret key is to be distributed between Alice and Charlie.

Protocol 2

• 1. Alice creates n random check bits, a random m-bit key k and a random 2n-bit string b.

• 2. Alice generates $s=(x,z)$ by choosing n-bit strings x and z at random.

• 3. Alice encodes her key k as $|k\rangle$ using the CSS code $Q_s$.

• 4. Alice chooses n positions (out of 2n) and puts the check bits in these positions and the code bits in the remaining positions.

• 5. Alice applies a Hadamard transform to those qubits in those positions where b is 1.

• 6. Alice sends the resulting state to Charlie. He acknowledges the receipt once he receives all qubits.

• 7. Alice announces b, the positions of the check bits, the values of the check bits and the strings s.

• 8. Charlie performs Hadamard on the qubits where b is 1.

• 9. Charlie checks whether too many of the check bits have been corrupted and aborts the protocol if so.

• 10. With the help of s, Charlie decodes the key bits and uses them for the key.

The above protocol works correctly and is unconditionally secure as long as the noise is under a given threshold value [22]. The protocol for carrying out QPC under noisy conditions is as follows

Protocol 3

• 1. Charlie generates a random n-bit string $R_{\mathrm{A}}$ and uses the CSS code-based quantum error correction protocol (Protocol 2) to send it to Alice.

• 2. Charlie generates a random n-bit string $C_T$ and computes $R_{\mathrm{B}} = R_{\mathrm{A}} \oplus C_T$

• 3. Charlie uses Protocol 2 to send $R_{\mathrm{B}}$ to Bob.

• 4. Alice and Bob compute $C_{\mathrm{A}} = M_{\mathrm{A}} \oplus R_{\mathrm{A}}$ and $C_{\mathrm{B}} = R_{\mathrm{B}} \oplus M_{\mathrm{B}}$.

• 5. Alice and Bob collaborate together to compute $C = C_{\mathrm{A}} \oplus C_{\mathrm{B}}$ and send it to Charlie over a public channel.

• 6. Charlie computes $R_c = C \oplus C_T$. $R_c$ has a single nonzero entry if and only if $M_{\mathrm{A}} \ne M_{\mathrm{B}}$, in which case Charlie outputs 1, otherwise he outputs 0

The entire process is summarized in Fig. 1. It is easy to see that in the absence of noise and eavesdropping, the protocol computes the function $f(M_{\mathrm{A}},M_{\mathrm{B}})$ correctly. In the presence of noise alone, the CSS-based scheme can transmit keys correctly as long as noise is within an acceptable level (the current acceptable level of bit(phase) flip errors is 20.0 % [25, 26]). When both noise and eavesdropping are allowed, the protocol is secure and gives correct results with very high probability. We now show the security and correctness in the presence of noise and eavesdropping. We note that participant attacks are stronger than non-participant attacks since participants always have more information. We consider attacks by Alice and Bob to demonstrate the security of the protocol.

Fig. 1

The schematic diagram of the protocol where Charlie generates random strings $R_{\mathrm{A}}$ and $C_T$; using the CSS- based protocol he sends $R_{\mathrm{A}}$ to Alice and $R_{\mathrm{B}}= R_{\mathrm{A}} \oplus C_T$ to Bob over the noisy channels. Alice and Bob encode their respective messages $M_{\mathrm{A}}$ and $M_{\mathrm{B}}$ in $C_{\mathrm{A}}$ and $C_{\mathrm{B}}$. They collaborate to compute $C = C_{\mathrm{A}} \oplus C_{\mathrm{B}}$ and send it via a public channel to Charlie

Consider an attack by Alice to gain information about $M_{\mathrm{B}}$. She can attack the transmission channel between Bob and Charlie and try to extract information by performing any physical operation permitted by quantum mechanics. Alternatively, she may exploit side channel attacks which exploit loopholes in the devices used to implement key distribution [27–35]. These two are fundamentally different kinds to attack.

Let us first analyze a direct attack on the transmission by Alice. She has access to $M_{\mathrm{A}}, C_{\mathrm{B}}, C_{\mathrm{A}}$ and $R_{\mathrm{A}}$. We may assume that $M_{\mathrm{A}}$ contains no information about $M_{\mathrm{B}}$. We note $M_{\mathrm{B}} = R_{\mathrm{B}} \oplus C_{\mathrm{B}}$, hence information about $R_{\mathrm{B}}$ implies information about $M_{\mathrm{B}}$ and vice-versa. Alice can gain information about $R_{\mathrm{B}}$ through $C_T$ ($R_{\mathrm{B}} = C_T \oplus R_{\mathrm{A}}$), alternatively she may intercept the communication between Bob and Charlie. The semi-honest nature of Charlie ensures that Alice does not learn anything about $C_T$. We know [22, 36] that once Bob and Charlie authenticate the CSS protocol the probability that intercepts by Alice go undetected is exponentially close to 1. In the event, the protocol is authenticated Alice’s mutual information about the key ($M_{\mathrm{B}}$) is exponentially small. So, any attack by Alice on the communication between Bob and Charlie cannot help her gain more than an exponentially small amount of information about $R_{\mathrm{B}}$ without going undetected with a probability exponentially close to 1. So with very high probability, attacks by Alice are unsuccessful.

Consider an attack by Alice on the devices used to implement the CSS based key distribution scheme. A CSS-based scheme can be turned into an equivalent modified BB-84 scheme [22], we need only analyze attacks on the latter to discuss the security of the former. Implementations of QKD employ devices that may not adhere to the strict assumptions made while proving their unconditional security. This allows for side channels for eavesdroppers to attack. These attacks can also be tackled. One can use measurement device-independent quantum key distribution [37] and appropriate experimental designs [38, 39] to achieve this. Specifically, it has been shown that we can implement key distribution such that it is immune to all side channel attacks [39].

In the event, the attacks are unsuccessful then we need to only care about the noise. But as we saw earlier, the CSS protocol is robust as long as the noise is under an acceptable level. Since the protocol is symmetric with respect to Alice and Bob, any attacks by Bob are also ruled out. We note that Charlie has access to $R_{\mathrm{A}}, R_{\mathrm{B}}, C_T$ and C and is restricted to be semi-honest. It is easy to see that under these restrictions, he can gain no information about $M_{\mathrm{A}}$ or $M_{\mathrm{B}}$.

3.3 Dishonest third party

It is possible to modify our protocol to achieve three-party QPC for weaker conditions on the third party. We allow the third party to be dishonest, in the sense that he may return incorrect comparisons to Alice and Bob. We note that by providing false results Charlie does not stand to gain any information about the private strings of Alice and Bob. We adapt the technique from [21] for our purposes. Alice and Bob share m strings whose values are known to them. They repeat the QPC protocol(as described above) $m + 1$ times. They compare m known strings and 1 secret string. Their secret strings are compared at some random repetition, known to Alice and Bob but unknown to Charlie. This prevents Charlie from being dishonest. In the event Charlie tries to give false information to Alice and Bob, he is caught with high probability ($1-\frac{1}{m+1}$).

4 Conclusions

We analyze EPR-based three-party QPC under noisy conditions and show that it is not robust under any amount of bit flip noise and depolarizing noise. We then present a CSS-based protocol that is robust against noise and secure under general attacks, as long as the noise is under an acceptable rate.

It is important to compare our work with the available classical and quantum protocols in the literature. Recently, a protocol using quantum key distribution (QKD) [21] have been proposed. This protocol does not consider noisy channels or side channel attacks. Though it is possible from our analysis above, to extend their work to the noisy channel case, in terms of resources, for the case of a semi-honest third party, their protocol achieves QPC using 4-QKD relays each sharing n bits of information. In comparison, our protocols uses 2-QKD-like relays, decreasing the quantum resources and communication complexity by a factor of 2. However, the overall communication complexity and quantum resources(in terms of entangled states used to implement a QKD) are still O(n).

Several classical protocols have been designed to perform two-party and multi-party secure computation. These protocols either work under an honest majority [40] or a Common Reference String (CRS) along with complexity assumptions [41] or demand access to a trusted dealer [42] (implemented using public key technique) but are able to tackle both passive and active adversaries. It is well known that certain complexity assumptions such as absence of polynomial time algorithms for prime factorization or discrete logarithm are invalid when the adversary has access to quantum resources [43]. On the other hand it is possible to use classical public key cryptosystems based on the hardness of learning with errors [44]. These cryptosystems cannot be broken by quantum algorithms presently known to us. Implementations of public key cryptosystems are expensive but can be done with $O(\text {poly}(n))$ classical resources. In our work, we consider only 2 parties and propose a protocol to compute a single function (equality) but allow the parties to be corrupted by an adversary who however does not inject incorrect information into the protocol. While we do not need complexity assumptions, we do need secure channels between the interested parties, and we take into account the resources expended in creating secure channels. In our proposal, the resources (classical and quantum) utilized to implement the protocol from scratch are linear in the size of the input. Our proposal based on previous work demands a trusted third party but we show how that assumption can be relaxed by repeating the protocol several times, consequently incurring a cost which is still linear in the size of the input.

We note that our protocol no longer uses EPR states, but requires the used of CSS code states. In order to send CSS-encoded information, we may require multi-qubit channels. In order to perform QPC under noise, we exploit the connection between CSS codes and key distribution. This enables us to provide unconditional security for QPC in real time implementation schemes.

It would be interesting to see if other QPC protocols that use d- level quantum systems or Greenberger–Horne–Zeilinger (GHZ) states can also be made unconditionally secure against all possible attacks. It would also be worthwhile to explore protocols that work under milder restrictions on the third party and protocols that can work for multi-party and implement a wider class of functions.