Quantum attacks on classical bit commitment schemes

Gilles Brassard Claude Crépeau Université de Montréal ^{∗}

Dominic Mayers Princeton University ^{†}

Louis Salvail Århus Universiteit ^{‡}

October 28, 1997

Abstract

Recent results of Mayers [] unveil a serious flaw in the proof of security of the Quantum Bit Commitment (QBC) Scheme of Brassard, Crépeau, Jozsa and Langlois [] and provide evidence that such a protocol is scritly impossible from quantum physics alone. We now investigate the power of attackers equipped with a quantum computer to break classical bit commitment scheme. We show that in certain scenarios the classical bit commitments offer little security. We also argue that certain type of proof techniques due to NOVY[] cannot be extended to the scenario of quantum computers.

1 Introduction

Quantum cryptographic protocols were born with quantum cryptography in Wiesner’s seminal paper [] where he introduced “Quantum Multiplexing” later known as one-out-of-two Oblivious Transfer []. Nevertheless, in the same paper Wiesner provides an attack based on general quantum measurements against his own scheme and prove it insecure. Later Bennett and Brassard, introduced a Quantum Coin Tossing Protocol [] together with an attack based on EPR effects. Back to Oblivious Transfer, Crépeau and Kilian described a quantum protocol for this problem making the strong assumption that photon storage for long periods of time is impossible. The security of this scheme was proved recently by Crépeau []. A more realistic version of this protocol that could tolerate transmission errors was described in [].

An extension to this result was also described in []: a secure Oblivious Transfer Protocol in a model where photon storage is possible based on the existence of a Bit Commitment Scheme. The security of this protocol was proved in two steps: first Mayers and Salvail showed the security of the scheme in a model restricted to measurements of single particules and later generalized by Yao in the most general model [].

Until recently, it was implicit that the Bit Commitment Scheme used to “bootstrap” Oblivious Transfer was a Quantum Bit Commitment Scheme. Such a scheme was first offered by Brassard and Crépeau [] and later polished by Brassard, Crépeau, Jozsa and Langlois in [] who claimed a proof of the security of their scheme. Unfortunately, a flaw was recently unveiled in this proof by Mayers [] who argued quite convincingly that Quantum Bit Commitment Scheme is impossible if no limit is put on the kind of complex system and measurement the parties may use.

∗ Département IRO, Université de Montréal, C.P. 6128, succursale centre-ville, Montréal (Québec), Canada H3C 3J7. e-mail: {brassard,crepeau}@iro.umontreal.ca.

†Department of Computer Science, Princeton University, Princeton, NJ 08544-2087, U.S.A.. e-mail: mayers@cs.princeton.edu.

‡Department of Computer Science,University of Århus, Ny Munkegade, building 540, DK-8000 Århus C, Denmark. e-mail: salvail@daimi.aau.dk

Although some two-party cryptographic protocols could still be found despite the result of Mayers that QBC is impossible in the most general model, all existing two-party protocols also collapse against the most general attacks allowed by quantum mechanics. The only exception to this situation is the Quantum Key Distribution protocol of Bennett and Brassard [] that is NOT a two-party protocol in the sense considered here that is still valid despite Mayers’ result.

2 Bit Commitment

Assume that a party, A, has a bit b in mind, to which she would like to be committed toward another party, B. That is, A wishes, through a procedure BC(b), to provide B with a piece of evidence w that she has a bit b in mind and that she cannot change it (the commitment is binding). Meanwhile, B should not be able to tell from that evidence what b is (the commitment is hiding). At a later time, A can reveal, through an unveiling procedure UN(b, p), the value of b and prove through p to B that the piece of evidence sent earlier (w) really corresponded to that bit.

Bit commitment schemes have several applications in the field of cryptographic protocols. In particular one can implement zero-knowledge proofs of a variety of statements using bit commitment schemes [GMR89, GMW91, BCC88]. The first implementations of bit commitment schemes were given in a computational complexity scenario [Blu82]. Unfortunately, proofs of their (computational) security have always required an unproved assumption since otherwise they would imply very strong results such as P ≠ N P.

3 NOVY Bit Commitment Scheme

In a computational scenario two techniques reduce bit commitment to very general cryptographic assumptions: the protocol of Naor [] reducing unconditionally binding–computationally hiding–bit commitment to pseudorandomness and the protocol of NOVY [] reducing computationally binding– unconditionally hiding–bit commitment to one-way permutations. We restrict our attention to this second result and first present their construction. Let π : {0, 1}^{n} → {0, 1}^{n} be a one-way permutation.

Protocol 3.1 ( NOV Y/Commit(b) )

1: A picks x ∈R {0, 1}^{n}, and computes y := π(x),

2: for i ∈ {1, ..., n − 1} do

3: B picks a hash vector h_{i} ∈R {0, 1}^{n} and announces it to A,

4: A anounces r_{i} := h_{i} · y to B,

5: endfor

6: Let y_{0}, y_{1} be the two solutions to {r_{i} = h_{i} · y_{∗}}_{1≤i<n} such that y_{0} < y_{1},

7: A sets a such that y_{a} = y and anounces a ⊕ b to B.

The fact that this protocol is unconditionally hiding is trivial since the commitment depends entirely on the fact that A knows the inverse of y_{0} or y_{1}. Since both have a unique inverse, it is impossible to B o tell which one A knows.

Protocol 3.2 ( NOV Y/Unveil(b) )

1: A discloses b and x to B, 2: B checks that y_{a⊕b} = π(x).

NOVY showed that it is computationally equivalent to cheat the unveiling protocol or to inverse the one-way permutation. Any efficient algorithm to solve one problem yeilds an efficient algorithm to solve the other.

3.1 Weak Breaking of NOVY

Let γ := \frac{1}{\sqrt{2}}.

Protocol 3.3 ( NOV Y/Commit(∗) )

1: A sets up a quantum register in state ∑_{x∈{0,1}^{n}} γ^{n}|x, π(x)⟩,

2: for i ∈ {1, ..., n − 1} do 3: B picks a hash vector h_{i} ∈R {0, 1}^{n} and announces it to A,

4: A sets up her quantum register R in state ∑_{{x∈{0,1}^{n}|h_{j}·π(x)=r_{j},1≤j<i}} γ^{n−i+1}|x, π(x), h_{i} · π(x)⟩,

5: A anounces to B, r_{i} := outcome of measuring h_{i} · π(x), and she drops that last bit 6: endfor 7: Let y_{0}, y_{1} be the two solutions to {r_{i} = h_{i} · y_{∗}}_{1≤i<n} such that y_{0} < y_{1}, 8: A picks a at random and announces a to B.

Protocol 3.4 ( NOV Y/Unveil(∗) )

1: A measures R, observes |x_{c}, y_{c}⟩, for some bit c, discloses b := a ⊕ c and x := x_{c} to B, 2: B checks that y_{a⊕b} = π(x).

3.2 Stronger Breaking

Consider the following unitary operators:

U := ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) X := ( \begin{matrix}I_{2} & 0_{2} \\ 0_{2} & U \end{matrix} ) .

Protocol 3.5 ( NOV Y/Commit(∗) )

...

7: Let y_{0}, y_{1} be the two solutions to {r_{i} = h_{i} · y_{∗}}_{1≤i<n} such that y_{0} < y_{1}, w.l.o.g. assume y_{0}[n] = 0 and y_{1}[n] = 1,

8: A applies (I_{2^{n−1}} ⊗ X) to (R ⊗ |ψ⟩) and obtains |Ξ⟩,

9: A measures the last position of |Ξ⟩, observes |a⟩ and announces a to B.

At step 8 of protocol 3.5, the quantum register R starts in the state γ(|x_{0}, y_{0}⟩ + |x_{1}, y_{1}⟩) and assume the input state is |ψ⟩ := α|0⟩ + β|1⟩. We assume without lose of generality that y_{0}[n] = 0 and y_{1}[n] = 1. If this is not the case, position n may be swapped with any other position i where this holds and may be swapped back in place later. Thus the original state is

(R ⊗ |ψ⟩) = γα|x_{0}, y_{0}, 0⟩ + γβ|x_{0}, y_{0}, 1⟩ + γα|x_{1}, y_{1}, 0⟩ + γβ|x_{1}, y_{1}, 1⟩

is mapped by (I_{2^{n−1}} ⊗ X) to

|Ξ⟩ = γα|x_{0}, y_{0}, 0⟩ + γβ|x_{0}, y_{0}, 1⟩ + γβ|x_{1}, y_{1}, 0⟩ + γα|x_{1}, y_{1}, 1⟩

since y_{0}[n] = 0 and y_{1}[n] = 1 and thus

|Ξ⟩ = γ(α|x_{0}, y_{0}, 0⟩ + β|x_{1}, y_{1}, 0⟩) + γ(β|x_{0}, y_{0}, 1⟩ + α|x_{1}, y_{1}, 1⟩).

As a result, if the last position of |Ξ⟩ is measured, bit |a⟩ is observed with the property that

R = \{ \begin{matrix}α|x_{0}, y_{0}⟩ + β|x_{1}, y_{1}⟩ & if |a⟩ is observed as |0⟩, \\ β|x_{0}, y_{0}⟩ + α|x_{1}, y_{1}⟩ & if |a⟩ is observed as |1⟩, \end{matrix} .

Another way to see this is R = α|x_{a}, y_{a}⟩ + β|xā, yā⟩.

3.2.1 When A Unveils

First we observe that if NOV Y/Unveil(∗) takes place, then B is satisfied, i.e. y_{a⊕b} = π(x) by the simple facts that b := a ⊕ c and x := x_{c}. What is more interesting in this case is the fact that given a, B knowing |ψ⟩ knows that y_{a⊕0} should be observed by A with probability ||α||^{2} and that y_{a⊕1} should be observed by A with probability ||β||^{2}. But this follows immediatly from the fact that R = α|x_{a}, y_{a}⟩ + β|xā, yā⟩.

3.2.2 When A never Unveils

Second we observe that if NOV Y/Unveil(∗) does not take place, then A may recover |ψ⟩ from her register R. Remembering that R = α|x_{a}, y_{a}⟩ + β|xā, yā⟩ A sets |ψ⟩ := γ|0⟩ + γ|1⟩ and constructs a new state

(|ψ⟩ ⊗ R) = γα|0, x_{a}, y_{a}⟩ + γβ|0, xā, yā⟩ + γα|1, x_{a}, y_{a}⟩ + γβ|1, xā, yā⟩

which is mapped by (X ⊗ I_{2^{n−1}}) to

|Ξ⟩ = γα|0, x_{a}, y_{a}⟩ + γβ|0, xā, yā⟩ + γβ|1, x_{a}, y_{a}⟩ + γα|1, xā, yā⟩

and thus

|Ξ⟩ = γ(α|0, x_{a}, y_{a}⟩ + β|1, x_{a}, y_{a}⟩) + γ(α|1, xā, yā⟩ + β|0, xā, yā⟩).

After measuring R, if |x_{a}, y_{a}⟩ is observed, then |ψ⟩ is left in state α|0⟩ + β|1⟩, which achieves our goal. Otherwise |xā, yā⟩ is observed and then |ψ⟩ is left in state β|0⟩ + α|1⟩, which is corrected by applying the unitary operator U.

4 Two-Prover Bit Commitment Scheme

Protocol 4.1 ( 2P/Commit(b) )

1: A picks r ∈R {0, 1}^{n}, and shares it as r′ with A’,

2: A and A’ are physically split,

3: B sets m_{0} := 0^{n} and picks m_{1} ∈R {0, 1}^{n}, and announces them to A,

4: A sends z := r ⊕ m_{b} to B,

Protocol 4.2 ( 2P/Unveil(b) )

1: A discloses b and r to B,

2: A’ discloses r′ to B,

3: B checks that r = r′ and that z = r ⊕ m_{b},

4.1 Cheating 2P/Commit

Let ψ, ψ′ be a pair of photons in state \frac{1}{\sqrt{2}}(|00⟩ + |11⟩) shared between A and A’ before they are physically separated and let μ := α|0⟩ + β|1⟩ be the particle given to A. Consider the action of applying X to the pair (μ, ψ). Because ψ′ is left untouched by this operator we may write the operator acting on the triple (μ, ψ, ψ′) = \frac{α}{\sqrt{2}}|000⟩ + \frac{α}{\sqrt{2}}|011⟩ + \frac{β}{\sqrt{2}}|100⟩ + \frac{β}{\sqrt{2}}|111⟩ as

X ⊗ ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} )

and thus X ⊗ ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) (μ, ψ, ψ′) = \frac{α}{\sqrt{2}}|000⟩ + \frac{β}{\sqrt{2}}|101⟩ + \frac{α}{\sqrt{2}}|011⟩ + \frac{β}{\sqrt{2}}|110⟩. Consider now what

happens if A measures particle ψ. With probability \frac{||α||^{2}}{2} + \frac{||β||^{2}}{2} = \frac{1}{2}, she gets ψ = |0⟩ and (μ, ψ′) = α|00⟩ + β|11⟩. Similarly, with probability \frac{||α||^{2}}{2} + \frac{||β||^{2}}{2} = \frac{1}{2}, she gets ψ = |1⟩ and (μ, ψ′) = α|01⟩ + β|10⟩. Notice that in both cases particle μ considered by itself has not changed from her original state α|0⟩ + β|1⟩. Notice also that the measured state of particle ψ indicates whether future readings of (μ, ψ′) will be correlated (ψ = |0⟩) or anti-correlated (ψ = |1⟩).

Now let’s see how we use this to cheat the protocol.

Protocol 4.3 ( 2P/Commit(∗) )

1: A and A’ share n pairs of particles (ψ_{i}, ψ′_{i}) in state \frac{1}{\sqrt{2}}(|00⟩ + |11⟩),

2: A and A’ are physically split,

3: B sets m_{0} := 0^{n} and picks m_{1} ∈R {0, 1}^{n}, and announces them to A,

4: for i ∈ {1, ..., n} do

5: if m_{1}[i] = 1 then A applies X to (μ, ψ_{i}),

6: A sets z[i] := outcome of measurement on ψ_{i},

7: endfor

8: A sends z to B.

Protocol 4.4 ( 2P/Unveil(∗) )

1: A measures μ to get b, sets r = z ⊕ m_{b}, discloses b and r to B,

2: A’ measures ψ′_{1}, ..., ψ′_{n} to get r′ and discloses r′ to B,

3: B checks that r = r′ and that z = r ⊕ m_{b},

We now show that this unveiling is always succesful. For this we consider each position i individually and show that r[i] = r′[i] as well as z[i] = r[i] ⊕ m_{b}[i].

Assume first that m_{1}[i] = m_{0}[i] = 0, then A sets r[i] = z[i] regardless of b. Remember that z[i] was obtained in protocol 2P/Commit as the outcome of measurement on ψ_{i} and r′[i] was obtained in protocol 2P/Unveil as the outcome of measurement on ψ′_{i}. Because (ψ, ψ′) was left in state \frac{1}{\sqrt{2}}(|00⟩ + |11⟩) both outcomes are the same and thus r′[i] = z[i] as well.

Assume last that m_{1}[i] = 1 (and m_{0}[i] = 0), then A sets r[i] = z[i] ⊕ m_{b}[i] = z[i] ⊕ b. Remember that z[i] was obtained in protocol 2P/Commit as the outcome of measurement on ψ_{i} after application of X(μ, ψ_{i}), r′[i] was obtained in protocol 2P/Unveil as the outcome of measurement on ψ′_{i} and b was obtained as the outcome of measurement on μ. Because of our earlier discussion we know that z[i] indicates whether later measurements of μ and ψ′_{i} are correlated (r′[i] = b for z[i] = 0) or anti-correlated (r′[i] ≠ b for z[i] = 1). Thus r′[i] ⊕ b = z[i] and r′[i] = z[i] ⊕ b for A’ as well.

5 Conclusion and Open Questions

6 Acknowledgments

We thank X for support, suggestions and comments on this work.

References

[BBCS92] C. H. Bennett, G. Brassard, C. Crépeau, and M.-H. Skubiszewska. Practical quantum oblivious transfer. In Advances in Cryptology: Proceedings of Crypto ’91, Lecture Notes in Computer Science, Vol. 576, pages 351–366. Springer-Verlag, 1992.

[BBR88] C. H. Bennett, G. Brassard, and J.–M. Robert. Privacy amplification by public discussion. SIAM Journal on Computing, 17(2):210–229, April 1988.

[Blu82] M. Blum. Coin flipping by telephone. In Proceedings of IEEE Spring Computer Conference, pages 133–137. IEEE, 1982.

[BCC88] G. Brassard, D. Chaum, and C. Crépeau. Minimum disclosure proofs of knowledge. Journal of Computer and System Sciences, 37:156–189, 1988.

[BC91] G. Brassard and C. Crépeau. Quantum bit commitment and coin tossing protocols. In Advances in Cryptology: Proceedings of Crypto ’90, Lecture Notes in Computer Science, Vol. 537, pages 49–61. Springer-Verlag, 1991.

[Cré90] C. Crépeau. Correct and Private Reductions among Oblivious Transfers. PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 1990.

[CK88] C. Crépeau and J. Kilian. Achieving oblivious transfer using weakened security assumptions. In 29^{th} Symposium on Foundations of Computer Science, pages 42–52. IEEE, 1988.

[GMW91] O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity, or All languages in N P have zero-knowledge proof systems. Journal of the ACM, 38:691–729, 1991.

[GMR89] S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof-systems. SIAM Journal on Computing, 18:186–208, 1989.

[Kra86] E. Kranakis. Primality and cryptography. John Wiley and Sons, 1986.

[MS77] F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes. North-Holland, 1977.

[Shi84] A.N. Shiryayev. Probability. Springer-Verlag, 1984.

[Wie83] S. Wiesner. Conjugate coding. SIGACT News, 15(1):78–88, 1983. Manuscript written circa 1970, unpublished until it appeared in SIGACT News.

Contents

1 Introduction 1 2 Bit Commitment 2 3 NOVY Bit Commitment Scheme 2

3.1 Weak Breaking of NOVY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3.2 Stronger Breaking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3.2.1 When A Unveils . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3.2.2 When A never Unveils . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

4 Two-Prover Bit Commitment Scheme 5

4.1 Cheating 2P/Commit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5 Reverting to very short Computational Assumptions 7 6 Conclusion and Open Questions 7 7 Acknowledgments 7