PaperlayerView exact revision on arXiv

Source-linked AI summary

Degrees of concealment and bindingness in quantum bit commitment protocols

R. W. Spekkens, T. Rudolph

arXiv:quant-ph/0106019v2quant-ph

TL;DR

Bit commitment must balance concealing a committed bit from Bob against binding Alice to it, and the paper studies the best simultaneous degrees of these properties. It derives bounds for general protocols and determines the optimal trade-off for Alice-supplied protocols, including a protocol that achieves it. The optimal trade-off is attainable with mixed commuting states in a three-dimensional Hilbert space, while whether the general bound is saturable remains open.

  • Problem

    The paper asks what degrees of concealment and bindingness can be achieved simultaneously in quantum bit commitment, where perfect concealment and binding are impossible.

    Source: §I · p. 1

  • Method

    The paper quantifies Bob’s information gain and Alice’s control, derives bounds for general protocols, and analyzes protocols where Alice supplies all systems used during commitment.

    Source: §I · p. 1, §IX · p. 9

  • Results

    For Alice-supplied protocols, the optimal trade-off is Cmax + Gmax = 1/2 and is achieved by purification protocols using mixed commuting states in a three-dimensional Hilbert space.

    Source: §IX · p. 9

  • Takeaways & Limitations

    Restrictions to a single two-dimensional support, states that are not both mixed, or both-pure states prevent achieving the optimal Alice-supplied trade-off.

    Source: §IX · p. 9

    Whether any protocol beyond the Alice-supplied class can outperform the linear trade-off Cmax + Gmax = 1/2 remains unanswered.

    Source: §IX · p. 9

Abstract

from arXiv · show

Although it is impossible for a bit commitment protocol to be both arbitrarily concealing and arbitrarily binding, it is possible for it to be both partially concealing and partially binding. This means that Bob cannot, prior to the beginning of the unveiling phase, find out everything about the bit committed, and Alice cannot, through actions taken after the end of the commitment phase, unveil whatever bit she desires. We determine upper bounds on the degrees of concealment and bindingness that can be achieved simultaneously in any bit commitment protocol, although it is unknown whether these can be saturated. We do, however, determine the maxima of these quantities in a restricted class of bit commitment protocols, namely those wherein all the systems that play a role in the commitment phase are supplied by Alice. We show that these maxima can be achieved using a protocol that requires Alice to prepare a pair of systems in an entangled state, submit one of the pair to Bob at the commitment phase, and the other at the unveiling phase. Finally, we determine the form of the trade-off that exists between the degree of concealment and the degree of bindingness given various assumptions about the purity and dimensionality of the states used in the protocol.

I. INTRODUCTION

Bit commitment seeks to bind Alice to a bit while concealing it from Bob, but perfect concealment and binding cannot both be achieved. This paper bounds their simultaneous degrees and determines the optimum for Alice-supplied protocols.

I. INTRODUCTION

  • Perfectly concealing and binding bit commitment is impossible, but protocols can be partially concealing and partially binding.The paper asks how well both properties can be achieved simultaneously.Source: §I · p. 1
  • The paper establishes an upper bound on simultaneous concealment and bindingness for all protocols, but whether it can be saturated is unknown.For protocols in which Alice supplies all systems used during commitment, it determines a saturable bound.Source: §I · p. 1
  • An entangled-pair protocol achieves the restricted-class maximum: Alice sends one system to Bob at commitment and the other at unveiling.Its maximum bindingness is simply related to the fidelity between Bob’s reduced states at the end of commitment.Source: §I · p. 1
  • Because bit commitment is a primitive in other cryptographic tasks, its achievable security has implications for those tasks; this paper considers coin tossing.The paper limits its discussion of such implications to coin tossing.Source: §I · p. 1

II. DEGREES OF CONCEALMENT AND BINDINGNESS

This section defines the paper’s measures of Alice’s control and Bob’s information gain, then frames the optimization of their trade-off across protocol classes. It establishes a lower bound for all protocols and identifies the optimum for Alice-supplied protocols.

II. DEGREES OF CONCEALMENT AND BINDINGNESS

  • Bob’s information gain measures his increase in correct-estimation probability, while Alice’s control measures her increase in probability of unveiling her desired bit.Both compare a party’s strategy with that party’s honest behavior; the paper assumes Bob has no prior information and Alice’s desired bit is equally likely to be 0 or 1.Source: §II · p. 2
  • Bob’s maximum information gain and Alice’s maximum control quantify the degrees of concealment and bindingness, respectively.The section defines partial and arbitrary degrees of these properties using the maxima and security parameters.Source: §II · p. 2
  • The section asks for each party’s maximum advantage and the strategy achieving it, then asks how low Alice’s maximum control can be at a given Bob information gain.The latter optimization defines a curve whose monotonically decreasing form is the optimal trade-off relation.Source: §II · p. 2
  • The paper derives a lower bound on the optimal trade-off for all protocols, but does not determine whether that bound is saturable.It finds the optimal trade-off for Alice-supplied protocols, including generalized BB84 and purification protocols, and shows purification protocols attain it.Source: §II · pp. 2–3

III. BC PROTOCOLS

The paper models quantum bit commitment using unitary actions on a pure total system, with communication represented by transfers of systems. It then specifies Alice-supplied protocols and the purification protocol used in its analysis.

III. BC PROTOCOLS

  • In the general model, each party’s laboratory actions are unitary operations, communication transfers systems, and the total system begins in a pure state.Random choices and measurements can be represented within this model by unitary operations involving ancillas.Source: §III · p. 3
  • A general commitment phase can involve multiple rounds of operations and communication, after which Bob holds a reduced state obtained by tracing out Alice’s systems.The model also describes the unveiling phase through further rounds of party operations.Source: §III · p. 3
  • Alice-supplied protocols require that Alice provide all systems Bob uses during commitment, while leaving the unveiling phase unrestricted.The class includes generalized BB84 and purification protocols, but excludes protocols using Bob-supplied systems or ancillas during commitment.Source: §III · pp. 3–4
  • A purification protocol uses two systems and orthogonal joint states: Alice sends the token at commitment, then the proof at unveiling for Bob’s measurement.At unveiling, Alice provides a purification of the state Bob received during commitment.Source: §III · p. 4

IV. MEASURES OF DISTINGUISHABILITY FOR DENSITY OPERATORS

This section introduces trace distance and fidelity as measures of density-operator distinguishability and presents relations between them. It also states properties of fidelity used in the investigation.

IV. MEASURES OF DISTINGUISHABILITY FOR DENSITY OPERATORS

  • Trace distance and fidelity are the two density-operator distinguishability measures used in the paper.The paper presents relations between the measures and states that the second inequality is saturated for any pair of pure states.Source: §IV · p. 4
  • A stronger lower bound on trace distance applies when one density operator is pure and also applies to mixed states of qubits.The section separately identifies a result for states whose supports lie in a single two-dimensional Hilbert space; the stated inequalities can be saturated.Source: §IV · p. 4
  • Uhlmann’s theorem relates fidelity to the overlap of maximally parallel purifications of the density operators.The section also introduces another critical property of fidelity for the investigation.Source: §IV · p. 4

V. OPTIMIZING OVER ALL BC PROTOCOLS

For any bit commitment protocol, the degrees of concealment and bindingness obey a universal trade-off; the bound rules out both arbitrarily strong properties at once. The bound's attainability is unresolved, while the proof lower-bounds Bob's information gain and Alice's control using holding-phase strategies.

V. OPTIMIZING OVER ALL BC PROTOCOLS

  • 2Gmax + 2Cmax = 1 is a lower-bound trade-off for any protocol, shown as curve I in Fig. 1.No protocol can lie below this curve.Source: §V · pp. 4, 6, Figure 1 · p. 5
  • Bob's optimal holding-phase discrimination of ρ0 and ρ1 establishes a lower bound on his maximum information gain.Cheating earlier in the commitment phase could raise his gain, but cannot make it lower.Source: §V · p. 5
  • Alice's holding-phase strategy, using a unitary before unveiling, establishes a lower bound on her maximum control.Her control may be higher if she also cheats during commitment or unveiling.Source: §V · p. 5
  • Cmax = Gmax = 3−4 ≈ .19098 is the best fair protocol point allowed by the universal bound.It corresponds to point A in Fig. 1.Source: §V · p. 6
  • Whether any protocol simultaneously attains the universal lower bounds for both parties remains unresolved.Such a protocol would require neither party to gain more by cheating during other phases than during the holding phase.Source: §V · p. 6

A. Optimal degrees of concealment and bindingness

For Alice-supplied protocols, the paper establishes optimal degrees of concealment and bindingness in terms of the distance and fidelity of Bob's reduced states. Purification protocols attain these bounds by using entangled proof and token systems.

A. Optimal degrees of concealment and bindingness

  • Purification BC protocols saturate the bounds for Alice-supplied protocols.An honest Alice prepares an entangled proof-token state and submits the token system to Bob.Source: A. Optimal degrees of concealment and… · pp. 6–7
  • Alice's access to all commitment-phase systems lets her replace the cheating-operation optimization with one over arbitrary unitaries on the total system.This argument applies only to Alice-supplied protocols because she must initially have access to those systems.Source: A. Optimal degrees of concealment and… · p. 6
  • Gmax = 1/2 D(ρ0, ρ1) is Bob's maximum information gain in an Alice-supplied protocol, achieved by a Helstrom measurement.The bound follows from the general result, and the measurement attains it for this class.Source: A. Optimal degrees of concealment and… · pp. 6–7
  • Cmax = 1/2 F(ρ0, ρ1) is Alice's maximum control in a purification protocol.Alice achieves it by preparing the maximizing state and choosing unveiling unitaries whose product is Umax.Source: A. Optimal degrees of concealment and… · p. 7

B. Optimal trade-off relations

The section determines optimal concealment–bindingness trade-offs under different restrictions on the states held by Bob. For Alice-supplied protocols, commuting mixed states in a three-dimensional space attain the unrestricted trade-off; narrower state restrictions yield different curves.

B. Optimal trade-off relations

  • The section derives optimal trade-off relations for different restrictions on the states Bob holds during the holding phase.It then gives examples of protocols achieving the optimal trade-offs.Source: B. Optimal trade-off relations · pp. 7–8
  • States supported in one 2-dimensional Hilbert space, or states that are not both mixed, cannot attain the optimal trade-off.The section gives separate optimal curves for these restrictions and for the both-pure case.Source: B. Optimal trade-off relations · p. 7
  • Commuting mixed states in a 3-dimensional Hilbert space attain the optimal Alice-supplied trade-off, with D(ρ0, ρ1) + F(ρ0, ρ1) = 1.Three dimensions are the smallest space in which this bound can be saturated.Source: B. Optimal trade-off relations · pp. 7–8
  • When both states are pure, purification protocols achieve the trade-off curve (Cmax)^2 + (Gmax)^2 = 1/4.Varying φ from 0 to π/2 traces the curve.Source: B. Optimal trade-off relations · p. 8
  • The best fair Alice-supplied protocol has Cmax = Gmax = 0.25.Here, “fair” means Alice’s control equals Bob’s information gain.Source: B. Optimal trade-off relations · p. 8

VII. SIGNIFICANCE FOR COIN TOSSING

The paper applies bit-commitment results to coin tossing, where each party’s bias measures their advantage over a fair win probability. It establishes a saturable bias condition and notes that arbitrarily small biases for both parties remain unresolved.

VII. SIGNIFICANCE FOR COIN TOSSING

  • Coin-tossing protocols can achieve any pair of biases satisfying α + β ≥ 1/2, and the inequality can be saturated.A fair protocol with both biases equal to 0.25 is achievable this way.Source: §VII · p. 8
  • Whether coin tossing can achieve arbitrarily small biases for both parties remains an open question.The impossibility of arbitrarily concealing and binding bit commitment does not settle this question because coin tossing is a weaker primitive.Source: §VII · p. 8
  • Bounded-bias coin-tossing protocols may support gambling protocols in which both parties’ winning probabilities are guaranteed to exceed a bound.The paper gives the casino and gambler as an example.Source: §VII · p. 8

VIII. RELATED OPTIMIZATION PROBLEMS

The paper identifies optimization questions beyond the concealment–bindingness trade-off: how Alice can balance control against the chance of being caught cheating, and how commitment might extend to multiple values. It relates these questions to information gain versus disturbance in quantum state estimation.

VIII. RELATED OPTIMIZATION PROBLEMS

  • Alice’s control-versus-disturbance relation describes the minimum probability of being caught cheating for each possible degree of control.The optimization matters when Alice assigns costs to protocol outcomes and seeks to minimize them.Source: §VIII · pp. 8–9
  • Integer commitment generalizes bit commitment by letting Alice unveil one of more than two integers.The related questions concern her maximum success probability and the minimum chance of being caught for each success probability.Source: §VIII · p. 9
  • These optimization problems parallel state estimation, which considers maximum information gain and minimum disturbance at each gain level.The paper proposes pursuing the control–information-gain analogy in future work on purification protocols.Source: §VIII · p. 9

IX. CONCLUSION

The conclusion summarizes bounds and optimal trade-offs for bit commitment, including a saturating purification protocol within the Alice-supplied class. It leaves open whether protocols beyond that class can improve on the linear trade-off and connects the analysis to broader questions about remote state preparation.

IX. CONCLUSION

  • For all bit-commitment protocols, the paper derives a bound on concealment and bindingness but does not determine whether it can be saturated.For Alice-supplied protocols, it obtains a stronger bound that purification protocols saturate.Source: §IX · p. 9
  • For Alice-supplied protocols, the optimal trade-off is Cmax + Gmax = 1/2, attained by mixed commuting states in a 3-dimensional Hilbert space.The conclusion contrasts this with restrictions under which the optimal trade-off cannot be achieved, including states supported in one 2-dimensional space or states not both mixed.Source: §IX · p. 9
  • Whether any bit-commitment protocol has a trade-off better than the linear Cmax + Gmax = 1/2 relation remains unanswered.The analysis would need to extend beyond Alice-supplied protocols to settle the question.Source: §IX · p. 9
  • The conclusion frames Alice’s cheating strategy in purification protocols as remotely preparing one of two states after she has submitted half of a bipartite system.It places this task among remote-state-preparation problems distinguished by constraints on the preparer, cooperation, and available resources.Source: §IX · p. 9
  • The authors suggest that understanding remote state preparation may contribute to foundational research on quantum mechanics.They connect this prospect to identifying which information-processing tasks can be implemented with quantum resources.Source: §IX · pp. 9–10

Appendix

The appendix proves a qubit-state inequality by representing density operators as Bloch-sphere vectors and minimizing over their relative angle. The result is D(ρ, σ) + F(ρ, σ)^2 ≥ 1.

Appendix

  • Qubit density operators are represented by Bloch-sphere vectors to express trace distance and squared fidelity.Source: Appendix · p. 10
  • The angular term is minimized at φ = 0, with r ≥ s assumed without loss of generality.Here r and s are the lengths of the Bloch vectors and φ is their relative angle.Source: Appendix · pp. 10–11
  • Together with other stated facts, (1 − r²)(1 − s²) ≥ (1 − r)(1 + s) implies D(ρ, σ) + F(ρ, σ)² ≥ 1.Source: Appendix · p. 11
Loading quant-ph/0106019v2…