Jan 29, 2011 - In [14, 15], the MLC no-go theorem was proved in the following basic idea. Suppose the initial states of Alice and Bob are |bãA (b â...

0 downloads 3 Views 133KB Size

On the impossibility of non-static quantum bit commitment between two parties

2

Qin Li,1, 2, ∗ Chengqing Li,1 Dong-Yang Long,2 W. H. Chan,3 and Chun-Hui Wu4 1 College of Information Engineering, Xiangtan University, Xiangtan 411105, China Department of Computer Science, Sun Yat-sen University, Guangzhou 510006, China 3 Department of Mathematics, Hong Kong Baptist University, Kowloon, Hong Kong 4 Department of Computer Science, Guangdong University of Finance, Guangzhou 510521, China (Dated: August 10, 2018)

3

2

4 5 6 7

14

Recently, Choi et al. proposed an assumption on Mayers-Lo-Chau (MLC) no-go theorem that the state of the entire quantum system is invariable to both participants before the unveiling phase. This means that the theorem is only applicable to static quantum bit commitment (QBC). This paper find that the assumption is unnecessary and the MLC no-go theorem can be applied to not only static QBC, but also non-static one. A non-static QBC protocol proposed by Choi et al. is briefly reviewed and analyzed to work as a supporting example. In addition, a novel way to prove the impossibility of the two kinds of QBC is given.

15

PACS numbers: 03.67.Dd

8 9 10 11

arXiv:1101.5684v1 [cs.CR] 29 Jan 2011

12 13

I.

16

INTRODUCTION

a secure QBC protocol in a bounded quantum-storage model [18]; Hardy and Kent gave a secure cheat sensitive 53 QBC protocol ensuring that if either a committer or a 54 committee cheat, the other can detect it with a nonzero 55 probability [19]. Besides these, secure QBC protocols are 56 implemented in a noisy-storage model under the assump57 tion that the dishonest party can not access large-scale 58 reliable quantum storage [20]. 59 Recently, Choi et al. proposed a secure non-static QBC 60 protocol with help of a trusted third party (TTP) [21] 61 and pointed out that the MLC no-go theorem is based 62 on an assumption that the whole quantum state is static 63 before Alice reveals the committed bit. That is to say, 64 the MLC no-go theorem was thought to be adapted to 65 static QBC only. D’Ariano et al. also hold this opinion 66 and gave another strengthened and explicit proof involv67 ing impossibility of some non-static QBC protocols [22]. 68 However, we find that the assumption given by Choi et 69 al. in [21] is unnecessary and non-static QBC is also im70 possible just due to the MLC no-go theorem. Although 71 Choi et al. proposed a secure non-static QBC protocol by 72 adopting a TTP [21], the protocol is still different from a 73 general two-party QBC protocol and is somewhat similar 74 to a quantum secret sharing protocol. Interestingly, the 75 non-static QBC protocol without the TTP can just serve 76 as an example to show that the MLC no-go theorem can 77 be applied to non-static QBC also. In addition, we prove 78 the impossibility of the two kinds of QBC in a different 79 way: prove any binding QBC protocols is not concealing, 80 while the related proofs proposed in [14, 15, 21, 22] show 81 any concealing protocols are not binding. 82 The rest of this paper is organized as follows. In the 83 next section, it will be shown that the assumption of the 84 MLC no-go theorem given by Choi et al. is unnecessary 85 and the MLC no-go theorem can be adapted to both 86 static QBC and non-static QBC. The non-static QBC 87 protocol proposed by Choi et al. is reviewed and analyzed 88 in Sec. III. Then the impossibility of QBC is proved in 89 Sec. IV in a different way. The last section concludes the 90 paper. 51

52

Bit commitment allows a sender (Alice) to commit a bit b ∈ {0, 1} to a receiver (Bob) in the following way: 19 1) Alice can not change the value of the committed bit 20 after the commitment phase (binding property); 2) Bob 21 can not obtain the value of the committed bit before the 22 unveiling phase (concealing property). Bit commitment 23 is an important cryptographic primitive and can be used 24 as a building block for some other cryptographic proto25 cols, such as coin flipping [1], oblivious transfer [2], zero26 knowledge proof [3], and multiparty computation [4]. 27 A secure bit commitment protocol should satisfy the 28 binding property and the concealing property at the same 29 time. However, unconditionally secure classical bit com30 mitment protocols do not exist. There are only some un31 conditionally binding and computationally concealing bit 32 commitment protocols [5] or unconditionally concealing 33 and computationally binding bit commitment ones [6]. 34 Since unconditionally secure quantum key distribution 35 protocols were proposed in [7–9], some quantum bit com36 mitment (QBC) protocols have been proposed with the 37 hope that QBC can provide unconditional security [10– 38 12]. The most famous one is the bit commitment protocol 39 proposed by Brassard et al. in [11], which was claimed 40 to be unconditionally secure. Unfortunately, the protocol 41 was showed to be insecure afterwards [13]. Furthermore, 42 Mayers, Lo and Chau proved that general secure QBC 43 protocols are impossible [14, 15], which is called MLC 44 no-go theorem. 45 Although discovery of the MLC no-go theorem de46 pressed much study on QBC protocols, researchers try 47 to design secure QBC by adopting certain restrictions 48 or weakening some security requirements. For instance, 49 Kent proposed two bit commitment protocols based on 50 special relativity theory [16, 17]; Damgard et al. designed 17

18

∗

[email protected]

2 91 92

II.

APPLICABILITY OF THE MLC NO-GO THEOREM TO NON-STATIC QBC

124

125

In [14, 15], the MLC no-go theorem was proved in the following basic idea. Suppose the initial states of Alice and Bob are |biA (b ∈ {0, 1}) and |ϕiB , respectively, and let UAB denote all the algorithms that Alice and Bob may implement. Then the final quantum state shared by Alice and Bob is |φb iAB = UAB (|biA ⊗ |ϕiB ). If a QBC protocol is perfectly concealing, namely

126

and ρB b = T rA (|φb iAB hφb |) X X = T rA aijbl cl |iiA |jiB a∗pqbr c∗r A hp|B hq| pqr

ijl

127

=

X

ijlqr

aijbl a∗iqbr cl c∗r |jiB hq|.

Suppose a non-static QBC protocol is perfectly conB cealing, P then ρB 0 and ρ1 should be identical for any 130 |ϕiB = m cm |miB , i.e. X 131 aij0l a∗iq0r cl c∗r |jiB hq| ρB 0 =

128

129

B ρB 0 = T rA (|φ0 iAB hφ0 |) = T rA (|φ1 iAB hφ1 |) = ρ1 ,

then there exists a local unitary transformation SA satisfying

ijlqr

=

132

(SA ⊗ I)UAB (|biA ⊗ |ϕiB ) = UAB (|1 − biA ⊗ |ϕiB ) according to Gisin-Hughston-Jozsa-Wootters theorem given in [23, 24]. So, by postponing measurements and 95 implementing local unitary operations, Alice can change 96 the value of the committed bit arbitrarily without be97 ing discovered by Bob. If the QBC protocol is supposed 98 to be unconditionally concealing, similar results can be 99 derived also. 100 However, Choi et al. observed that the local unitary 101 operation SA performed by Alice is related to Bob’s ini102 tial state |ϕiB [21]. If |ϕiB is random and unknown to 103 Alice, she can not find a suitable local unitary operation 104 to change the committed value. Thus, a necessary as105 sumption of the MLC no-go theorem is that the state of 106 quantum system should be static to both participants. 107 This means the MLC no-go theorem was considered to 108 be applicable to static QBC only. 109 As shown above, the proof of the MLC no-go theorem 110 is based on the following strategy: a QBC protocol is 111 first supposed unconditionally concealing and it is then 112 proved that unconditionally binding is impossible. So, 113 Theorem 1 can be obtained, which means that the as114 sumption of the MLC no-go theorem suggested by Choi 115 et al. is unnecessary. 93 94

X

ijlqr

= ρB 1 .

133

134 135

aij1l a∗iq1r cl c∗r |jiB hq|

Since the above formula always holds for any |ϕiB , we have aij0l a∗iq0r = aij1l a∗iq1r .

136

Let SA =

P xy

sxy |xiA hy|, where

if x 6= y, sxy = 0, sxx = 0, if axq1r = 0 for any q and r, ∗ sxx = a∗xq0r , otherwise. a xq1r

137

138

Equation (1) makes SA always satisfy (SA ⊗ IB )|φ0 iAB =

X xy

139

=

140

Theorem 1 The MLC no-go theorem is also applied to non-static QBC.

sxy |xiA hy| ⊗

X ijl

X

=

141

X

X k

|kiB hk|

!

aij0l cl |iiA |jiB

aij0l cl

X x

ijl

ijl

116

(1)

sxi |xiA |jiB

aij1l cl |iiA |jiB

= |φ1 iAB ,

142

for any |ϕiB . Thus the non-static QBC protocol is not binding. If assume it is unconditionally concealing, sim145 ilar results can be obtained also. 118 Proof : Assume P |ϕiB is random and unknown to Al119 ice. Let UAB = ijkl aijkl |iiA |jiB A hk|B hl| and |ϕiB = P 120 c |mi , then we have m B m 117

143 144

146

147

121

122

|φb iAB = UAB (|biA ⊗ |ϕiB ) ! X X = aijkl |iiA |jiB A hk|B hl| cm |biA |miB m

ijkl

123

=

X ijl

aijbl cl |iiA |jiB ,

III.

REVIEW AND ANALYSIS OF CHOI ET AL.’S NON-STATIC QBC PROTOCOL

In [21], Choi et al. proposed an unconditionally secure non-static QBC protocol with aid of a TTP. We briefly 150 reviewed it in the following four phases and then show its 151 simplified version can serve as an example demonstrating 152 the MLC no-go theorem is applicable to non-static QBC. 148

149

3 the above non-static QBC protocol do not correspond to the fact that only two parties is involved in a general QBC protocol, although TTP plays a little role in offering quantum sources and is not involved in communication between two parties directly. In a way, the protocol is more like a quantum secret sharing protocol. For instance, the cooperation between Bob and TTP can get Aice’s committed value while one of them cannot. If the actions implemented by TTP are replaced by Bob, the protocol will not be secure. As shown by Choi et al. in [21], if the non-static QBC protocol without a TTP is perfectly concealing, a local unitary operator a b SA = c d

a. Preparing phase : First, Alice and TTP share N maximally entangled states in the form |ψ − iAT = |01>−|10> √ . This kind of entangled state has a special 2 property, namely equation |ψ − iAT = (U ⊗ U )|ψ − iAT holds up to the global phase for any unitary transformation U . Then, TTP applies random projection measurements represented as Mi = {|fi iT hfi |, |fi⊥ iT hfi⊥ |} to its qubit of each entangled state |ψ − iAT for i = 1 ∼ N . ⊥ 154 If the measurement outcome of TTP is |fi i(|f i i), then ⊥ 155 Alice’s measurement result should be |ψi iA = |f i i(|fi i). 156 But TTP does not announce Mi now, so Alice can not 157 know the result |ψi iA . 158 b. Commitment phase : To committee the bit 159 b, Alice applies the corresponding operations Pi ∈ 160 {M, N, J, K}, where 0 −1 1 0 161 , ,N = M= 1 0 0 1 1 1 1 i 1 i J=√ 162 ,K = √ . 2 1 −i 2 −1 i 153

If Alice chooses to commit b = 0, she randomly sends M |ψi iA or N |ψi iA to Bob. Otherwise, she sends J|ψi iA or K|ψi iA instead with the same probability. To guarantee the randomness, Alice introduces an auxiliary system A′ A′ whose initial state is |+iA′ = |0iA′√+|1i . Then the 2 ′ state of the whole system A A is |+i|ψi i. If b = 0, Alice applies |0iA′ h0| ⊗ M + |1iA′ h1| ⊗ N to A′ A to obtain |ϕ0 iA′ A =

|0iA′ ⊗ M |ψi iA + |1iA′ ⊗ N |ψi iA √ . 2

such that J = aM + bN and K = cM + dN , can be used to freely change the committed bit. Thus it can be 179 seen that Choi et al.’s non-static QBC protocol without 180 a TTP can serve as a specific example to demonstrate 181 that the MLC no-go theorem is applicable to non-static 182 QBC also. 177

178

183 184

|ϕ1 iA′ A

PROOF OF IMPOSSIBILITY OF QBC BY ANOTHER WAY

Although non-static QBC between two participants is also impossible due to the MLC no-go theorem, it pro187 vides us another way to prove the impossibility of both 188 non-static and static QBC. 189 Let us show the case on non-static QBC first. Premise 190 of the proof of the MLC no-go theorem is that the QBC 191 protocol is supposed to be perfectly concealing, 185

186

192

B F (ρB 0 , ρ1 ) = 1,

(2)

or unconditionally concealing,

Otherwise, she implements |0iA′ h0| ⊗ J + |1iA′ h1| ⊗ K on A′ A and gets |0iA′ ⊗ J|ψi iA + |1iA′ ⊗ K|ψi iA √ . = 2

IV.

B F (ρB 0 , ρ1 ) = 1 − δ,

where δ > 0. For non-static QBC protocols, different initial states B B B 195 |ϕiB may lead to different ρ , so the value of F (ρ , ρ ) 0 1 b 196 may vary and it is difficult to make the concealing prop197 erty be satisfied. On the other hand, since |ϕiB is totally 198 random and unknown to Alice, it is difficult for Alice to 199 find an appropriate local unitary operator SA such that 193

194

Due to the randomness of |ψi iA , the resulting state |ϕb iA′ A is also different, thus Alice cannot control the 165 relationship between |ϕ0 iA′ A and |ϕ1 iA′ A without know166 ing the exact state |ψi iA . 167 c. Sustaining phase : In this phase, both Alice and 168 Bob do nothing. 169 d. Revealing phase : Alice unveils all Pi ’s, and then 170 TTP opens all Mi ’s and the corresponding measurement 171 outcomes. After knowing all the information, Bob mea† 172 sures P Pi |ψi i with Mi and compares all the measurei 173 ment results with those TTP announced. If all the mea174 surement outcomes are opposite, Alice is honest and the 175 committed value has not been changed; otherwise Alice 176 is dishonest. In [21], Choi et al. claimed that the protocol is unconditionally secure. However, the usage of TTP makes 163

164

200

F ((SA ⊗ I)UAB (|biA ⊗ |ϕiB ), UAB (|1 − bi ⊗ |ϕiB )) = 1 (3) or F ((SA ⊗ I)UAB (|biA ⊗ |ϕiB ), UAB (|1 − bi⊗ |ϕiB )) = 1 − δ

is satisfied for all |ϕiB . Thus, it is better to suppose a non-static QBC protocol 203 is perfectly or unconditionally binding and then prove it 204 cannot be perfectly or unconditionally concealing. 201 202

4 Assume a non-static QBC protocol is perfectly binding, i.e., there does not exist a local unitary operator SA such that Eq. (3) holds for any |ϕiB . Then there must be some |ϕiB such that B ρB 0 = T rA (|φ0 iAB hφ0 |) 6= T rA (|φ1 iAB hφ1 |) = ρ1 .

Otherwise, the assumption violates the MLC no-go theorem. In other words, if Eq. (2) holds for any |ϕiB , Alice 207 can find a local unitary operation SA to freely change 208 the committed bit according to the MLC no-go theorem. 209 Thus Bob can choose such |ϕiB to get some information 210 of Alice’s committed bit and the non-static QBC is not 211 perfectly concealing. If a non-static QBC protocol is as212 sumed to be unconditionally binding, similar conclusions 213 can be made. This new approach also can be used to prove impossibility of static QBC. Given a fixed |ϕiB , if a static QBC protocol is supposed to be perfectly binding, then there is no local unitary operator SA satisfying Eq. (3). According to the Uhlmann’s theorem in [25], we can find |φi, a purification of ρB 0 , such that

216 217

218

tionally binding, we can prove it is not unconditionally concealing employing the similar method.

V.

CONCLUSION

205

In this paper, we show the assumption given by Choi et al. on the MLC no-go theorem in [21], that the en221 tire quantum state should be static to both participants 222 before the unveiling phase, is unnecessary, and the MLC 223 no-go theorem can be applied to both static QBC and 224 non-static QBC. In addition, a secure non-static QBC 225 protocol proposed by Choi et al. in [21] is found more 226 like to a quantum secret sharing protocol, instead of a 227 general two-party QBC protocol. Just inspired by the 228 non-static QBC, we prove the impossibility of QBC in 229 another way: suppose a QBC protocol is binding first, 230 then show it is not concealing. Now, we can say that 231 the MLC no-go theorem lets any two-party QBC pro232 tocol satisfying concealing property is not binding and 233 the novel proof for the impossibility of QBC given by B F (ρB 234 us makes any two-party QBC protocol satisfying binding 0 , ρ1 ) = |hφ|φ1 i|, 235 property is not concealing. In all, any two-party QBC where |φ1 i = UAB (|1iA ⊗ |ϕiB ) is a purification of 236 protocol, no matter static or non-static, is not secure. B ρB 1 . Between two purifications of ρ0 , |φi and |φ0 i = 237 ACKNOWLEDGEMENTS UAB (|0iA ⊗ |ϕiB ), there always exist a local unitary operator SA such that (SA ⊗ I)|φ0 i = |φi. Besides, from the assumption, we know that there does not exist a local 238 The authors would like to thank Guang-Ping He and unitary operator SA such that (SA ⊗ I)|φ0 i = |φ1 i. Thus 239 Chun-Yuan Lu for their constructive suggestions on im240 proving this paper. The work of Qin Li and Chengqing Li |φi cannot be equal to |φ1 i and 241 was supported by start-up funding of Xiangtan UniverB B 242 sity of grant number 10QDZ39. The work of W. H. Chan F (ρ0 , ρ1 ) = |hφ|φ1 i| 6= 1, 243 was partially supported by the Faculty Research Grant 214 which means the static QBC protocol is not perfectly 244 of Hong Kong Baptist University under grant number 215 concealing. If assume a static QBC protocol is uncondi245 FRG2/08-09/070. 206

[1] A. Nayak and P. Shor, Physical Review A 67, article no. 012304 (2003). 248 [2] C. Crepeau, Journal of Modern Optics 41, 2445 (1994). 249 [3] G. Brassard, D. Chaum, and C. Crepeau, Journal of 250 Computer and System Sciences 37, 156 (1988). 251 [4] C. Crepeau, J. van de Graaf, and A. Tapp, in Advances 252 In Cryptology-Crypto’95, Lecture Notes in Computer Sci253 ence, Vol. 963 (Springer, 1995) pp. 110–123. 254 [5] M. Naor, Journal of Cryptology 4, 151 (1994). 255 [6] M. Naor, R. Ostrovsky, R. Venkatesan, and M. Yung, 256 Journal of Cryptology 11, 87 (1998). 257 [7] C. H. Bennett and G. Brassard, in Proceedings of the 258 IEEE International Conference on Computers Systems 259 and Signal Processing (1984) pp. 175–179. 260 [8] A. K. Ekert, Physical Review Letters 67, 661 (1991). 261 [9] C. H. Bennett, Physical Review Letters 68, 3121 (1992). 262 [10] G. Brassard and C. Crepeau, in Advances In Cryptology263 Crypto’90, Lecture Notes in Computer Science, Vol. 537 264 (Springer, 1991) pp. 49–61. 246

247

219 220

[11] G. Brassard, C. Crepeau, R. Jozsa, and D. Langlois, in Proceedings of the 34th Annual Symposium on Founda267 tions of Computer Science (1993) pp. 362–371. 268 [12] M. Ardehali, “A quantum bit commitment proto269 col based on EPR states,” (1996), arXiv:quant270 ph/9505019v5. 271 [13] D. Mayers, “The trouble with quantum bit commit272 ment,” (1996), arXiv:quant-ph/9603015v3. 273 [14] D. Mayers, Physical Review Letters 78, 3414 (1997). 274 [15] H.-K. Lo and H. F. Chau, Physical Review Letters 78, 275 3410 (1997). 276 [16] A. Kent, Physical Review Letters 83, 1447 (1999). 277 [17] A. Kent, Journal of Cryptology 18, 313 (2005). 278 [18] I. B. Damgard, S. Fehr, L. Salvail, and C. Schaffner, in 279 Proceedings of the 46th Annual Symposium on Founda280 tions of Computer Science (2005) pp. 449–458. 281 [19] L. Hardy and A. Kent, Physical Review Letters 92, arti282 cle no. 157901 (2004). 283 [20] S. Wehner, M. Curty, C. Schaffner, and H.-K. Lo, Phys284 ical Review A 81, article no. 052336 (2010). 265

266

5 [21] J. W. Choi, D. Hong, K.-Y. Chang, D. P. Chi, and S. Lee, in Proceedings of the 9th Asian Conference on Quantum 287 Information Science (2009) pp. 205–206, also available 288 at: arXiv:0901.1178v4. 289 [22] G. M. D’Ariano, D. Kretschmann, D. Schlingemann, and 290 R. F. Werner, Physical Review A 76, article no. 032328

(2007). [23] N. Gisin, Helvetica Physica Acta 62, 363 (1989). 293 [24] L. P. Hughstona, R. Jozsa, and W. K. Wootters, Physics 294 Letters A 183, 14 (1993). 295 [25] R. Jozsa, Journal of Modern Optics 41, 2315 (1994).

285

291

286

292