WHY QUANTUM BIT COMMITMENT AND IDEAL QUANTUM COIN TOSSING ARE IMPOSSIBLE

There had been well-known claims of unconditionally secure quantum pro tocols for bit commitment. However, we, and independently Mayers, show ed that all proposed quantum bit commitment schemes are, in principle, insecure because the sender, Alice, can almost always cheat successfu lly by using an Einstein-Podolsky-Rosen (EPR) type of attack and delay ing her measurements. One might wonder if secure quantum bit commitmen t protocols exist at all. We answer this question by showing that the same type of attack by Alice will, in principle, break any bit commitm ent scheme. The cheating strategy generally requires a quantum compute r. We emphasize the generality of this ''no-go theorem'': Unconditiona lly secure bit commitment schemes based on quantum mechanics-fully qua ntum, classical or quantum but with measurements-are all ruled out by this result. Since bit commitment is a useful primitive for building u p more sophisticated protocols such as zero-knowledge proofs, our resu lts cast very serious doubt on the security of quantum cryptography in the so-called ''post-cold-war'' applications. We also show that ideal quantum coin tossing is impossible because of the EPR attack. This no -go theorem for ideal quantum coin tossing may help to shed some light s on the possibility of non-ideal protocols. (C) 1998 Elsevier Science B.V. All rights reserved.