Source-linked AI summary
Variable Bias Coin Tossing
Roger Colbeck, Adrian Kent
TL;DR
VBCT asks how two mistrustful parties can share a random bit while one secretly selects its bias within an agreed range. The paper develops quantum and relativistic protocols and places them within secure two-party computation. It obtains unconditional security for limited biases, cheat-evident security for arbitrary biases, and conjectured unconditional security for further arbitrary-range protocols.
Problem
VBCT requires a shared biased random bit whose bias is secretly chosen by one party within a prescribed range while the other learns only the outcome.
Source: B. Secure computation · p. 3Method
The paper develops quantum and relativistic VBCT protocols, including protocols using relativistic bit commitment, and relates them to secure two-party computation.
Source: B. Secure computation · p. 3, A. Protocol VBCT1 · p. 7, B. Protocol VBCT2 · p. 9Results
The protocols provide unconditional security for limited bias ranges, cheat-evident security for arbitrary ranges, and conjectured unconditional security for further arbitrary-range protocols.
Source: §V · p. 13Takeaways & Limitations
VBCT supplies cryptographic applications in which one party can influence a shared random outcome through a hidden authorized bias while preserving security guarantees.
Source: B. Secure computation · p. 3, A. Introduction · p. 4
Abstract
from arXiv · showhide
Alice is a charismatic quantum cryptographer who believes her parties are unmissable; Bob is a (relatively) glamorous string theorist who believes he is an indispensable guest. To prevent possibly traumatic collisions of self-perception and reality, their social code requires that decisions about invitation or acceptance be made via a cryptographically secure variable bias coin toss (VBCT). This generates a shared random bit by the toss of a coin whose bias is secretly chosen, within a stipulated range, by one of the parties; the other party learns only the random bit. Thus one party can secretly influence the outcome, while both can save face by blaming any negative decisions on bad luck. We describe here some cryptographic VBCT protocols whose security is guaranteed by quantum theory and the impossibility of superluminal signalling, setting our results in the context of a general discussion of secure two-party computation. We also briefly discuss other cryptographic applications of VBCT.
I. INTRODUCTION
The paper situates VBCT within physics-based secure computation, contrasting unconditional, cheat-evident, and cheat-sensitive security with known possibilities and impossibility results. It emphasizes relativistic constraints as enabling stronger protocols while introducing practical deployment costs.
A. Background
- Physics-based security distinguishes unconditional, cheat-evident, and cheat-sensitive guarantees by whether cheating is impossible or detected with certainty or non-zero probability.The paper focuses mainly on unconditional security while also considering cheat-evident protocols.Source: A. Background · p. 1
- Relativistic protocols can enable secure strong coin tossing and bit commitment despite impossibility results for corresponding non-relativistic protocols.Their security relies on separated communication locations and the impossibility of superluminal signalling.Source: A. Background · p. 2
- Quantum and relativistic implementations provide unconditional-security advantages but may require costly, less robust technology and separated sites.The paper notes that separation can be reduced in principle to colocated credit-card-sized secure devices, although site constraints remain relevant.Source: A. Background · p. 2
B. Secure computation
- VBCT is a two-sided, one-input random computation in which one party secretly selects a bias and both parties receive the resulting shared outcome.It is the two-faced special case of a variable-bias n-faced die roll and is the paper’s central task.Source: B. Secure computation · pp. 2–3
- Known classifications include unconditionally secure biased n-faced die rolls for zero-input two-sided random computations, while some one-input one-sided tasks such as oblivious transfer are impossible.Table I summarizes the broader classification using possible, impossible, conjectural, partial, and unknown categories.Source: B. Secure computation · p. 3, Table I · p. 3
- Secure two-input deterministic one-sided cryptographically nontrivial computations are impossible, while secure two-input non-deterministic computations have no known existence or no-go results.Lo’s impossibility argument extends from non-relativistic to relativistic protocols.Source: B. Secure computation · p. 3
II. VARIABLE BIAS COIN TOSSING
VBCT provides a shared biased random bit while allowing Bob to choose the bias within a prescribed range and limiting Alice’s information about that choice. The paper illustrates applications ranging from socially face-saving decisions to verifiable randomized noise in data sales.
A. Introduction
- VBCT lets Bob choose p0 within pmin ≤ p0 ≤ pmax while preventing Alice from influencing the outcome probabilities or learning more about Bob’s choice than the outcome reveals.The protocol targets a genuinely random outcome subject only to Bob’s authorized bias choice.Source: A. Introduction · p. 4
- A social application lets Bob choose a high or low acceptance probability while both parties can attribute an unfavorable invitation decision to the coin toss.Alice’s posterior estimate of Bob’s reluctance remains approximately 10^-n+1 in the example.Source: A. Introduction · p. 4
- Running VBCT independently across image bits can provide a buyer with randomly generated noise while making significant selective deviations detectable against the later-revealed dataset.The example uses p0 = pmin for one bit value and p0 = pmax for the other, with deviations on more than O(√N) bits almost certainly detectable.Source: A. Introduction · p. 4
B. Definitions
The definitions specify VBCT’s inputs, outputs, bias constraints, security conditions, and asymptotic parameters, then place the protocols within relativistic and quantum cryptographic practice. Security protects an honest party against unauthorized influence or information gain, while supplementary tests refine finite-parameter guarantees.
B. Definitions
- A VBCT protocol takes Bob’s one-bit input and gives both parties the same output, 0, 1, or abort, with abort possible only when a party refuses honest completion.The protocol may use classical or quantum communication, separated sites, bias parameters, and security parameters.Source: B. Definitions · p. 4
- Security limits outcome probabilities to the allowed bias range, up to ε, and limits Alice’s information about Bob’s bias to the coin-toss information plus δ, except with probability ζ.The guarantees apply when at least one party honestly follows the protocol.Source: B. Definitions · p. 5
- Supplementary security tests can increase security for finite parameters, but require modified definitions when Bob aborts after the outcome is determined.The asymptotic security criteria remain valid whether or not these tests are performed.Source: B. Definitions · p. 5
- The security errors ε, δ, and ζ vanish as security parameters grow, while perfect security sets all three to zero at fixed parameter values.These limits define the paper’s asymptotic and perfect-security notions.Source: B. Definitions · p. 5
- Unless a dishonest party accepts a significant abort risk, it cannot move outcome probabilities significantly outside the allowed range.The explicit bounds include an additional ε′ term for the probability of aborting under the fixed strategy.Source: B. Definitions · p. 5
III. SOME CRYPTOGRAPHIC BACKGROUND
- The protocols generally combine separated-site relativistic communication with quantum information, and some use RBC2, which is classically secure and conjectured secure against general quantum attacks.RBC2 is also proven immune to the Mayers-Lo-Chau attack.Source: §III · pp. 5–6
A. Review of relativistic cryptography
The protocols assume trusted local laboratories and agents but no trusted third party, using relativistic timing and separated sites to guarantee independent signal generation. Their security relies on approximate Minkowski causal structure and authenticated internal coordination.
A. Review of relativistic cryptography
- Security analyses use flat Minkowski spacetime as an approximation, while known general-relativistic corrections are stated not to affect them.The paper notes that exotic distortions of spacetime could undermine such protocols, but excludes those scenarios from consideration.Source: A. Review of relativistic cryptography · p. 6
- Relativistic protocols require parties to control appropriately located laboratories while trusting their own agents but no outside party, channel, or device.The parties may collaborate across distributed sites, provided their laboratories do not overlap and remain within agreed regions.Source: A. Review of relativistic cryptography · p. 6
- The discussion generalizes to protocols such as VBCT1 that require Alice and Bob to control three or more separate sites.Source: A. Review of relativistic cryptography · p. 6
- Signal arrival times and agreed timing constraints let each party verify that required pairs of transmissions were generated independently.The protocol can avoid disclosing exact laboratory locations while still checking timing compliance.Source: A. Review of relativistic cryptography · p. 7
- The setup assumes synchronized clocks, near-light-speed authenticated channels between a party’s agents, and aborts when an honest party fails to receive required signals.The agents share random strings and secure pairwise channels, although those channels need not be unjammable.Source: A. Review of relativistic cryptography · p. 7
B. Brief review of bit commitment
The paper reviews bit commitment and then presents VBCT1, a relativistic quantum protocol that achieves unconditional security over a limited bias range. It combines spacelike-separated communications, non-orthogonal qubit encoding, and a final XOR outcome.
B. Brief review of bit commitment
- Bit commitment is described as giving Bob data that fixes Alice to a bit without revealing it, followed later by information that unveils the committed value.The review notes that relativistic bit commitment is provably secure against classical attacks, while non-relativistic quantum bit commitment is insecure under Mayers–Lo–Chau attacks.Source: B. Brief review of bit commitment · p. 7
A. Protocol VBCT1
- VBCT1 implements variable-bias coin tossing with unconditional security for a limited bias range and requires each party to operate agents at three appropriately separated sites.The protocol is presented as a relativistic quantum construction.Source: A. Protocol VBCT1 · p. 7
- Bob selects a designated qubit after committing to guess its state, then chooses a bit according to that guess and his desired outcome; the result is c = a ⊕b.Spacelike separation prevents the designation announcement from depending on the selected state or its identity.Source: A. Protocol VBCT1 · p. 8
- Alice sends randomly chosen non-orthogonal qubits, later reveals their identities across spacelike-separated communications, and Bob checks the stored states before proceeding.The protocol aborts if Bob detects any mismatch between the received states and Alice’s descriptions.Source: A. Protocol VBCT1 · pp. 7–8
- VBCT1 uses Bob’s guessing choice to represent his desired outcome, while security requires equality in the stated criterion.This connects the protocol’s operational choice of b to its security analysis.Source: A. Protocol VBCT1 · p. 8
1. Bob’s strategy
Bob’s optimal strategy is to measure the selected non-orthogonal state and use the result to guess its preparation, with the selection index treated as independent of that state. The resulting protocol supports exactly complementary bias ranges.
1. Bob’s strategy
- The announced index n can be treated as a pre-agreed classical value independent of the selected state and previous states, so it gives Bob no additional advantage.This follows from the causal separation of the announcement from transmission of the selected state and its identity.Source: §1 · p. 8
- Bob is committed to guessing the selected state, and his best strategy is to measure it with projections corresponding to the most likely preparation outcomes.The protocol treats failure to make the required guess as evidence of cheating.Source: §1 · p. 8
- Measurements in the |±⟩ basis maximize Bob’s guessing probability for the two non-orthogonal states.The optimal projections are identified with the |±⟩ basis.Source: §1 · p. 8
- The security criterion is always satisfied, with Bob’s minimum correct-guessing probability given by 1 − pmax.Bob can attain the complementary strategy by associating his measurement outcome with the opposite guess.Source: §1 · p. 9
- VBCT1 implements VBCT for all values of pmin and pmax satisfying pmin + pmax = 1, and no others.Source: §1 · p. 9
2. Security against Alice
The first protocol is asymptotically secure against Alice, while VBCT2 supports arbitrary bias ranges with cheat-evident rather than unconditional security.
2. Security against Alice
- As the expected number of states grows, Alice’s probability of successfully changing Bob’s measurement probabilities can be made arbitrarily close to zero.The bound applies for any fixed deviation and affected-state fraction, with success at most γ(1 −δ^2)^(γn).Source: §2 · p. 9
- The security argument applies state by state to every Alice strategy, including strategies using entangled qubit sequences.Source: §2 · p. 9
B. Protocol VBCT2
- VBCT2 allows any bias range but achieves cheat-evident rather than unconditional security.Source: B. Protocol VBCT2 · p. 9
- VBCT2 creates entangled states with two possible biases, lets Alice test or trust Bob, and defines the toss by measuring the selected state.Source: B. Protocol VBCT2 · pp. 9–10
- In the limits M →∞ and N →∞, the protocol is expected to become secure against Bob and prevent Alice from gaining information beyond the honest measurement.Source: B. Protocol VBCT2 · p. 10
- Alice can learn Bob’s bias by making inconsistent claims across locations, but the attack is certainly exposed when Bob’s agents communicate.Source: B. Protocol VBCT2 · p. 10
- Alice may also force an abort after learning the outcome, but this provides no advantage.Source: B. Protocol VBCT2 · p. 10
1. Security against Alice
Against an honest Bob, Alice cannot significantly increase her information about his chosen bias through measurements on the remaining states.
1. Security against Alice
- Alice cannot affect the bias once Bob’s batch is accepted, because her announced test-or-trust choice is independent of the current batch.Source: §1 · p. 10
- As N →∞, the trace distance between the normalized remaining-state ensembles tends to zero, so Alice’s excess information about Bob’s bias tends to zero.Source: §1 · pp. 10–11
2. Security against Bob
Bob cannot reliably force an outcome probability outside the permitted bias range when Alice tests his honesty sufficiently often.
2. Security against Bob
- For any fixed deviation δ and cheating success probability δ′, the probability that Alice detects Bob approaches 1 as M becomes sufficiently large.Each cheating batch has failure probability at least δ′δ^2, and there are approximately 2^M testing batches.Source: §2 · p. 11
C. Protocol VBCT3
VBCT3 uses relativistic bit commitment to hide Bob’s selected state until the parties’ test choices are compared, eliminating VBCT2’s cheat-evident attack and conjecturally achieving unconditional security.
C. Protocol VBCT3
- Bit commitment keeps Bob’s state choice secret until B1 and B2 compare Alice’s announced test choices, eliminating the earlier cheat-evident attack.Source: C. Protocol VBCT3 · p. 11
- Bob prepares N shared entangled states, Alice chooses whether to test, and the parties broadcast their choices before Bob unveils the committed coin-toss state.Source: C. Protocol VBCT3 · pp. 11–12
- After the commitment delay, Bob unveils the selected index; Alice and Bob measure their halves in the computational basis to define the outcome.Source: C. Protocol VBCT3 · p. 12
- Bob may additionally test Alice’s returned qubits from all nonselected states and abort if those states fail the projective measurements.Source: C. Protocol VBCT3 · p. 12
1. Security against Alice
The protocol offers Alice no useful cheating attack, while security against Bob remains conjectural because composability is unproved. VBCT4 uses relativistic bit commitments and a matrix-based classical protocol to produce the toss.
1. Security against Alice
- Alice gains no useful advantage: inconsistent responses are detected with certainty, and encrypted commitments reveal nothing about Bob’s chosen bias.Intentionally causing a later abort after learning the outcome also gives Alice no advantage.Source: §1 · p. 12
2. Security against Bob
- VBCT3’s security against Bob is conjectured because a proof must establish secure composability against collective quantum attacks.The underlying single-round commitment is unconditionally secure against Bob, but the composed protocol has no proof.Source: §2 · p. 12
D. Protocol VBCT4
- VBCT4 has Bob commit to a secret paired-row matrix, Alice test random pairs, and both parties select an unopened matrix element for the coin outcome.Bob chooses the remaining row according to his desired bias, while Alice chooses a random column before Bob unveils the intersecting bit.Source: D. Protocol VBCT4 · p. 13
- After the tests pass, the selected matrix bit is unveiled as the coin-toss outcome while all remaining commitments stay unopened.Source: D. Protocol VBCT4 · p. 13
1. Security
The paper presents four VBCT protocols spanning quantum, relativistic, and classical settings, with security guarantees ranging from unconditional security to conjectured quantum security. It generalizes VBCT to variable-bias n-faced die rolls and connects these protocols to broader one-input two-party computation.
V. SUMMARY
- Four VBCT protocols are presented: VBCT1 is unconditionally secure for limited biases, VBCT2 is cheat-evident for arbitrary ranges, and VBCT3 is conjectured unconditionally secure.VBCT3 extends VBCT2 using a relativistic bit commitment subprotocol.Source: §V · p. 13
1. Security
- VBCT4 is classical and unconditionally secure against classical attacks, while its security against quantum attacks remains conjectural.Both the underlying relativistic commitment scheme and the resulting VBCT4 quantum security are conjectured rather than proven.Source: §V · p. 13, §1 · p. 13
V. SUMMARY
- VBCT is a random one-input two-sided secure computation, generalized by variable-bias n-faced die rolls whose output distribution is selected from an agreed finite set.Source: §V · p. 13
- Protocols VBCT2, VBCT3, and VBCT4 can be generalized to n-faced die rolls by adapting quantum states or matrix-row proportions to represent the allowed outcomes.The quantum adaptations are conjectured cheat-evidently and unconditionally secure respectively, while the VBCT4 adaptation is conjectured unconditionally secure.Source: §V · pp. 13–14
- If the conjectures are proven, variable-bias n-sided die rolling would implement all one-input random two-sided single-function computations with unconditional security.Source: §V · p. 14