PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum And Relativistic Protocols For Secure Multi-Party Computation

Roger Colbeck

arXiv:0911.3814v2quant-ph

TL;DR

The thesis studies secure multi-party computation across physical theories and adversarial device assumptions. It introduces protocols and models, proves insecurity for broad function classes, and presents conjectured random-expansion protocols.

  • Problem

    Secure computation lacks known protocols or impossibility results for several two-party tasks, while device-independent randomness expansion must address untrusted quantum devices.

  • Method

    The thesis develops quantum and relativistic coin-tossing protocols, a general secure-computation model with cheating attacks, and device-independent randomness-expansion protocols.

  • Results

    It matches the best known security for non-relativistic strong coin tossing, establishes broad secure-computation impossibility results, and proposes two conjectured randomness-expansion protocols.

  • Takeaways & Limitations

    The work expands the known landscape of secure multi-party computation by combining constructive protocols with explicit attacks and impossibility results.

  • Takeaways & Limitations

    The randomness-expansion protocols rely partly on conjectured security, and quantum attacks remain an undesirable assumption when the adversary supplies the devices.

Abstract

from arXiv · show

After a general introduction, the thesis is divided into four parts. In the first, we discuss the task of coin tossing, principally in order to highlight the effect different physical theories have on security in a straightforward manner, but, also, to introduce a new protocol for non-relativistic strong coin tossing. This protocol matches the security of the best protocol known to date while using a conceptually different approach to achieve the task. In the second part variable bias coin tossing is introduced. This is a variant of coin tossing in which one party secretly chooses one of two biased coins to toss. It is shown that this can be achieved with unconditional security for a specified range of biases, and with cheat-evident security for any bias. We also discuss two further protocols which are conjectured to be unconditionally secure for any bias. The third section looks at other two-party secure computations for which, prior to our work, protocols and no-go theorems were unknown. We introduce a general model for such computations, and show that, within this model, a wide range of functions are impossible to compute securely. We give explicit cheating attacks for such functions. In the final chapter we discuss the task of expanding a private random string, while dropping the usual assumption that the protocol's user trusts her devices. Instead we assume that all quantum devices are supplied by an arbitrarily malicious adversary. We give two protocols that we conjecture securely perform this task. The first allows a private random string to be expanded by a finite amount, while the second generates an arbitrarily large expansion of such a string.

Declaration

The thesis declares that it is the author's own work, except where collaboration is specifically indicated.

  • The thesis is declared to be the author's own work, excluding collaborative work unless specifically indicated in the text.

Introduction

The thesis examines how quantum and relativistic physics affect secure multi-party computation, developing protocols and impossibility results across coin tossing, secure computation, and randomness expansion. It seeks security guaranteed by physical laws rather than assumptions about adversaries’ computational power.

  • Quantum cryptographic motivation: Quantum key distribution generates keys remotely with unconditional security because measuring quantum states necessarily disturbs them, allowing eavesdropping to be detected.Remote key distribution is impossible classically, making quantum mechanics cryptographically more powerful in this respect.
  • Strong coin tossing: Strong coin tossing illustrates that different physical theories provide different cryptographic power, while a new non-relativistic quantum protocol matches the best known bias using a different technique.The protocol also demonstrates entanglement as a cryptographic resource.
  • Variable bias coin tossing: Variable bias coin tossing is achieved with unconditional security for a specified bias range and cheat-evident security for any bias.Two additional protocols are discussed and conjectured to be unconditionally secure for any bias.
  • Other secure computations: The thesis introduces a general model for two-party secure computations and proves that functions within broad classes are impossible to compute securely.The results include explicit cheating attacks and are summarized in Table 4.4.
  • Randomness expansion: Under relaxed cryptographic assumptions, the thesis studies expanding a private random string when all quantum devices may be supplied by an arbitrarily malicious adversary.The proposed protocols respectively provide finite expansion and arbitrarily large expansion.

2. Alice does not learn

Oblivious transfer is sufficient for secure multi-party computation but impossible, while relativistic bit commitment offers a different primitive with useful yet limited security properties. The section outlines Kent’s RBC1 implementation and notes its communication drawback alongside RBC2’s constant-rate alternative.

  • Oblivious transfer is sufficient for any secure multi-party computation, yet it is impossible to construct.The thesis provides a proof of impossibility in Section 4.4.3.
  • Bit commitment has two steps: one party commits to a bit, then later reveals it to the other party.Before revelation, the recipient is oblivious to the bit, while the committer cannot alter its value.
  • The bit-commitment flavour usable for oblivious transfer is impossible even relativistically, whereas Kent’s alternative is possible classically but unproven secure quantumly.Kent’s relativistic schemes require sustained communication and are retractable, preventing their use for Yao’s oblivious-transfer construction.
  • RBC1 commits Alice’s bit using modular random integers, then sustains the commitment by iteratively committing binary forms of successive masks.Alice later unveils by sending the random numbers used in the final commitments, with causal-disconnection checks enabling verification.
  • RBC1 requires an exponentially increasing communication rate, while RBC2 combines RBC1 with Rudich’s scheme to achieve constant transmission rate.The thesis does not present RBC2’s full details.

The Power Of The Theory – Strong Coin Tossing

The chapter uses strong coin tossing to show how physical theory determines information-processing power. Classical non-relativistic physics cannot realize the task, quantum mechanics permits partial security, and relativistic protocols can realize it perfectly.

  • The Power Of The Theory – Strong Coin Tossing: Physical theory fundamentally dictates what information processing can achieve because information processing is performed by physical machines.The discussion attributes changes in information-processing power to the emergence of new physical theories.
  • The Power Of The Theory – Strong Coin Tossing: The chapter compares classical and quantum theories with and without relativity through the example of strong coin tossing.Strong coin tossing is presented as a simple cryptographic task in which separated parties generate a shared random bit.
  • The Power Of The Theory – Strong Coin Tossing: Classical non-relativistic theory cannot realize strong coin tossing, quantum mechanics permits protocols with partial security, and relativistic protocols realize it perfectly.The task ideally prevents either party from increasing the probability of either outcome by any method.
  • The Power Of The Theory – Strong Coin Tossing: When perfect security is unavailable, honest participants must obtain 0 or 1 with probability 1/2 each, while security is measured by the maximum cheating probability.The bias is defined as the deviation of the maximum cheating probability from 1/2.

2. A strong coin tossing

This section defines strong coin tossing and examines how quantum mechanics and relativity affect its security. It presents non-relativistic quantum protocols with bias 1/4, while noting that the optimality question remains open and relativistic protocols gain security from no-superluminal signalling.

  • Definitions: Strong coin tossing protects against an opponent whose preferred outcome is unknown, unlike weak coin tossing, which addresses bias toward one particular outcome.Strong coin tossing is relevant when the parties have knowledge asymmetry about each other’s desired outcome.
  • Non-relativistic protocols: Protocol 2.2 is a non-relativistic quantum strong coin-tossing protocol for which no protocol with a better bias is known.Its approach attempts to securely share entanglement before exploiting the resulting quantum correlations.
  • Quantum security: Quantum encoding in non-orthogonal bases creates knowledge asymmetry because neither party can determine the other’s information with certainty.This loss of information completeness provides cryptographic power beyond protocols using only classical systems.
  • Non-relativistic protocols: 1/4 is the bias achieved by the two non-relativistic quantum strong coin-tossing protocols presented in the section.The section states that the question of whether Kitaev’s bound can be reached remains open, although two protocols achieving bias 1/4 suggest this may be optimal.
  • Relativistic protocols: Relativistic strong coin tossing gains security from the impossibility of superluminal signalling, which can conceal information for at least the light-travel time.This enables zero-knowledge, finite-time commitment sufficient for coin tossing.

Variable Bias Coin Tossing

The chapter defines variable bias coin tossing and presents four protocols spanning limited-bias unconditional security, arbitrary-bias cheat-evident security, conjectured unconditional security, and classical security against classical attacks.

  • VBCT1: VBCT1 implements variable bias coin tossing with unconditional security for a limited range of biases, including general quantum attacks.The protocol is relativistic and quantum.
  • VBCT2: VBCT2 supports any range of biases but guarantees only cheat-evident security against general quantum attacks.Security improves asymptotically as protocol parameters increase, while cheating can be exposed.
  • VBCT3: VBCT3 extends VBCT2 with relativistic bit commitment to eliminate its discussed cheat-evident attack and is conjectured unconditionally secure.The modification prevents Alice from benefiting by sending inconsistent choices at the two locations.
  • VBCT4: VBCT4 is a classical protocol based on repeated classical relativistic bit commitment and is unconditionally secure against classical attacks.Its underlying bit-commitment scheme is described as conjectured secure against relevant attacks.
  • Generalizations: The chapter also identifies the variable bias n-faced die roll as the most general computation of this type, with a finite range of n outputs.A biased n-faced secure die roll can be implemented with unconditional security by generalizing a relativistic secure coin-toss protocol.

Secure Two-Party Classical Computation

The chapter introduces a black-box model for secure two-party classical computation and shows that quantum protocols cannot securely realize broad classes of such computations. The results rely on cheating strategies that let one party learn more about the other’s input than the computation should reveal.

  • Deterministic functions: For every 3 × 3 deterministic function satisfying conditions 1 and 2, Alice can use a superposition input and a measurement that distinguishes Bob’s outputs better than any honest strategy.This establishes an explicit cheating attack for the considered function class.
  • Binary-input functions: All genuinely two-input functions of the analysed 2 × 2 type are impossible to compute securely, except for cases where only one party has a meaningful input.The exceptional cases correspond to one-sided or otherwise degenerate functions.
  • Applications: One-sided variable bias coin tossing is impossible because it is a special case covered by the cheating theorem.The special case satisfies p00 = p10 and p01 = p11, and these cases are not exceptions.
  • Model and security condition: The chapter introduces a black-box computation model and a necessary security condition for unconditional security.Even if the prescribed black boxes existed, one party could break the security condition.
  • Extensions and limitations: The results extend to many larger functions: deterministic functions containing a potentially concealing 3 × 3 submatrix are insecure, while no two-party non-deterministic computation satisfies the security condition.The broader conjecture that all potentially concealing functions admit superposition-and-measurement attacks remains unproved.

Private Randomness Expansion Under Relaxed Cryptographic Assumptions

The chapter studies randomness expansion when all quantum devices are supplied by an adversary, showing that an initial private random string and non-local quantum tests can overcome deterministic and local-procedure no-go results. It presents two conjecturally secure protocols: one with finite expansion and one allowing arbitrary expansion, subject to efficiency, site, and proof limitations.

  • Limitations: The protocols are not efficiency-optimized, lack full security proofs, and Protocol 5.2 requires a large set of mutually noncommunicating sites.The initial-string length also depends on the desired tolerance for successful cheating by Snoop.
  • No-go results: Adversarially supplied devices defeat randomness generation when Alice uses a deterministic or local procedure without an initial private random string.Snoop’s devices can make predetermined classical outputs that Alice cannot distinguish from intended behavior.
  • Seeded expansion: An initial private random string hides sufficient details of Alice’s tests to constrain Snoop and enable generation of private random bits.The approach relaxes the assumption that Alice’s devices are trusted.
  • Finite expansion: Protocol 5.1 conjecturally expands a sufficiently long initial string by any specified finite amount, with privacy derived from passing non-local quantum tests.GHZ tests provide precise failure detection, and passing tests are conjectured to yield private randomness; the protocol’s generated string is longer than the initial one.
  • Arbitrary expansion: Protocol 5.2 conjecturally expands a sufficiently long initial string by an arbitrary amount, provided the number of sites meets the required error tolerance.Its device triples generate independent randomness, allowing the total output to scale with the number of triples.

Appendix A

Appendix A introduces a discussion on maximizing probability, but the supplied passage does not provide further details.

  • Appendix A: Appendix A is titled “Maximizing The Probability Of.”The supplied passage contains only this incomplete title.

Distinguishing Between Two · Quantum States

This section formulates a theorem on distinguishing two quantum states represented by density matrices with potentially unequal prior probabilities. It considers POVM-based discrimination and extends a prior argument to unequal priors.

  • Quantum States: The theorem considers Bob distinguishing between two quantum states with density matrices ρ0 and ρ1.
  • Quantum States: The state ρ0 occurs with prior probability η0.
  • Quantum States: The state ρ1 has prior probability η1 = 1−η0.
  • Quantum States: An optimal POVM is used to distinguish the two states with a stated success probability.
  • Quantum States: The proof follows an argument similar to Nielsen and Chuang.
  • Quantum States: The result extends the earlier argument to unequal prior probabilities.
  • Quantum States: A general POVM is described by measurement elements {Ei}N.
  • Quantum States: Measuring the supplied state with this POVM produces outcomes whose distributions are defined using traces such as QI(i) = tr(ρ1Ei).

Appendix A

Appendix A proves a state-discrimination bound by decomposing η0ρ0 − η1ρ1 into positive operators and constructing a POVM that saturates the resulting inequality. For equal priors, the theorem gives a corresponding upper bound on successful discrimination probability.

  • Theorem proof: The proof decomposes η0ρ0 −η1ρ1 as Υ0 −Υ1, with |η0ρ0 −η1ρ1| = Υ0 + Υ1 for positive operators with orthogonal support.This decomposition yields the trace inequality |tr (Ei (Υ0 −Υ1))| ≤tr (Ei |η0ρ0 −η1ρ1|).
  • Theorem proof: The inequality can be saturated by the POVM {Π0, Π1}, where each Πj projects onto the support of the corresponding Υj.The appendix states that this POVM has the desired properties and concludes the result.
  • Corollary: For states with equal priors, the corollary bounds their successful discrimination probability by at most 1.The supplied passage states this equal-prior corollary without giving a more specific numerical value.

Appendix B

Appendix B is identified by the heading “A Zero Knowledge Protocol For,” indicating a zero-knowledge protocol but not specifying its target task in the supplied passage.

  • Appendix B is headed “A Zero Knowledge Protocol For.”
  • The supplied heading identifies the subject as a zero-knowledge protocol.
  • The passage ends before stating what task the protocol addresses.

Graph Non-Isomorphism

The section uses a classical zero-knowledge proof for graph non-isomorphism to illustrate that universally composable security can hold even when one party responds after receiving information from another. It also describes the proof’s guarantees and the assumed computational capabilities of the prover and verifier.

  • Graph Non-Isomorphism: Universally composable security definitions can be satisfied for a protocol in which one party responds after receiving information from another.The example is a classical protocol whose universally composable properties are discussed here.
  • Graph Non-Isomorphism: A zero-knowledge proof lets an honest prover convince a verifier that a true statement holds without revealing other information, while false statements cannot be convincingly proved.The protocol involves a prover and verifier.
  • Graph Non-Isomorphism: For graph non-isomorphism, the prover convinces the verifier that two graphs are inequivalent under every permutation of their vertices.Graphs are described as nodes together with defined connectivity.
  • Graph Non-Isomorphism: The prover is assumed to possess a device that decides graph isomorphism, whereas the computationally bounded verifier cannot solve that problem.The device determines whether two graphs are isomorphic.

Appendix B

Appendix B describes a graph non-isomorphism proof protocol and its ideal functionality, in which the prover identifies a randomly permuted graph and the verifier accepts repeated correct responses. An additional device does not break universally composable security here, provided its inputs are made before the ideal functionality is executed.

  • Graph non-isomorphism protocol: The verifier randomly selects G0 or G1, applies a random permutation Ξ, and sends the resulting graph to the prover.The prover determines which graph was permuted and returns 0 or 1; the verifier checks correctness and repeats the process until sufficient confidence is reached.
  • Graph non-isomorphism protocol: The protocol outcome is a = 1 when the proof is accepted and a = 0 otherwise.If the prover’s response is incorrect, no proof of graph non-isomorphism has been provided.
  • Ideal functionality: When graphs are non-isomorphic, the ideal functionality lets the prover choose whether to output a = 1 or a = 0; when they are isomorphic, it can output only a = 0.
  • Additional-device security: An additional device using an algorithm unknown to the prover does not break universally composable security in this protocol.A dishonest prover can use the device together with a device implementing the ideal functionality to simulate all data obtained in the real protocol.
  • Additional-device security: The additional device’s inputs must be supplied before the ideal functionality executes, because later simulation cannot generate correctly distributed pairs (Ξ, c) with a.

Appendix C … Test

Appendix C seeks the complete finite-dimensional tripartite states and two-setting measurement devices that pass a GHZ test. The test requires specified products of detector outcomes for different measurement-setting combinations.

  • States That Can Pass A GHZ: The method follows the technique used to identify states and measurements producing maximal violation of the CHSH inequality.The cited CHSH-based technique is used as an analogue for the GHZ-test analysis.
  • Appendix C: The appendix seeks the complete set of tripartite states in finite-dimensional Hilbert spaces.This search concerns states capable of satisfying the GHZ-test conditions.
  • The Complete Set Of Quantum: It also seeks two-setting measurement devices whose outputs are either 1 or −1.The settings of device i are denoted Pi and Qi.
  • Test: When all three detectors measure Pi, the product of their outcomes must be +1.This is the first stated GHZ-test condition.
  • Test: When two detectors measure Qi and one measures Pi, the product of their outcomes is constrained by the GHZ-test condition.The supplied passage introduces this second setting combination but truncates before stating its required product.
  • Test: The listed measurement requirements are presented as equivalent to another set of demands.The supplied text does not include the equivalent demands themselves.

Appendix C

Appendix C characterizes all states and operators satisfying the stated relations. It derives anticommutation on projected subspaces, identifies the resulting SU(2) structure, and obtains GHZ-subspace decompositions up to local unitaries.

  • Projected operators: The operators satisfy {pi, qi} = 0 for i = 1, 2, 3 after restricting to their non-zero Schmidt subspaces.Projectors onto non-zero subspaces reduce the original operators while preserving the key relation.
  • SU(2) representation: The projected operators and commutators transform like SU(2) generators, with anticommutation restricting the representation to two dimensions.This permits a basis in which each operator pair is represented using Pauli matrices with identity multiplicities.
  • GHZ decomposition: The state decomposes into subspaces that each satisfy the GHZ relation, with |ψGHZ⟩= 1 √ 2(|000⟩−|111⟩) 1.The coefficients weighting the subspaces obey P j |aj|2 = 1.
  • Classification: The resulting states and operators form the complete solution set to (C.1–C.4), up to local unitaries.The classification follows from the projected operator relations and the resulting two-dimensional representation structure.
Loading 0911.3814v2…