PaperlayerView exact revision on arXiv

Source-linked AI summary

Private Randomness Expansion With Untrusted Devices

Roger Colbeck, Adrian Kent

arXiv:1011.4474v3quant-ph

TL;DR

The paper asks whether untrusted, potentially adversarial devices can generate private randomness without trusting their internal workings. It proposes device-independent expansion from an initially private seed, addresses a composability vulnerability through privacy amplification, and leaves security against the most general attacks open.

  • Problem

    The paper investigates whether untrusted devices can generate longer random strings that remain private from all other parties.

  • Method

    The paper proposes a device-independent protocol using private inputs and GHZ tests to expand an initially private random string, with privacy amplification addressing partial seed compromise.

  • Results

    The paper introduces a finite expansion protocol, discusses an extension for arbitrarily long output, and reports candidate security intuitions rather than a complete general-attack proof.

  • Takeaways & Limitations

    The protocols aim to provide users with a virtual guarantee that outputs from supplied devices are private and random without requiring knowledge of their internal operation.

  • Takeaways & Limitations

    Security against the most general attacks remains an open problem; a post-quantum extension additionally assumes no signalling between devices and Eve.

Abstract

from arXiv · show

Randomness is an important resource for many applications, from gambling to secure communication. However, guaranteeing that the output from a candidate random source could not have been predicted by an outside party is a challenging task, and many supposedly random sources used today provide no such guarantee. Quantum solutions to this problem exist, for example a device which internally sends a photon through a beam-splitter and observes on which side it emerges, but, presently, such solutions require the user to trust the internal workings of the device. Here we seek to go beyond this limitation by asking whether randomness can be generated using untrusted devices---even ones created by an adversarial agent---while providing a guarantee that no outside party (including the agent) can predict it. Since this is easily seen to be impossible unless the user has an initially private random string, the task we investigate here is private randomness expansion. We introduce a protocol for private randomness expansion with untrusted devices which is designed to take as input an initially private random string and produce as output a longer private random string. We point out that private randomness expansion protocols are generally vulnerable to attacks that can render the initial string partially insecure, even though that string is used only inside a secure laboratory; our protocol is designed to remove this previously unconsidered vulnerability by privacy amplification. We also discuss extensions of our protocol designed to generate an arbitrarily long random string from a finite initially private random string. The security of these protocols against the most general attacks is left as an open question.

I. INTRODUCTION

The paper frames private randomness expansion as generating longer private random strings from untrusted devices, without trusting their internal workings. It introduces protocols addressing a composability vulnerability while leaving security against the most general attacks unresolved.

  • Motivation: Device-independent protocols aim to guarantee private random outputs using tests on device outputs rather than verification of internal construction.This avoids requiring users to establish that supplied devices contain no accidental or deliberate security flaws.
  • Research task: Private randomness expansion uses an initially private random string to generate a longer string that remains private from all other parties.The paper investigates this task within the device-independent paradigm.
  • Contribution: Earlier protocols were not secure in a composable way because plausible attacks could partly compromise the final private random string.The present protocol modifies an earlier proposal to address this vulnerability.
  • Contribution: The proposed protocol lets a user provide a sufficiently long private seed to adversary-created devices and obtain a finite longer private random string.An extension is intended to generate arbitrarily long private output, but requires many isolated devices that cannot communicate.
  • Open questions: Security against the most general possible attacks remains an open question, so the work presents candidate protocols and supporting intuitions rather than a complete proof.The authors stress that such intuitions should ultimately be accepted only when proven.

A. Assumptions

The protocol assumes a secure laboratory and authenticated internal processing while removing the assumption that the user knows how the devices operate. It also assumes isolation, noiseless operation, and quantum-mechanical constraints on the adversary.

  • Laboratory security: Bob’s laboratory is assumed secure against messages leaving Eve’s devices and against external probing by Eve.Secret messages cannot be sent from devices inside the laboratory to the outside world.
  • Isolation: Bob must be able to isolate devices so they cannot send signals outside their isolated regions.This assumption constrains communication from devices held in the laboratory.
  • Classical processing: Bob is assumed to have secure classical processors and authenticated internal communication that Eve’s devices cannot spoof.Device outputs reach Bob’s classical devices only through prescribed channels.
  • Adversary and operation: The model assumes Eve is constrained by quantum theory and that all communication channels and devices operate noiselessly.These are explicit assumptions of the protocol setting.
  • Device trust: The protocol does not assume that Bob has complete knowledge of the devices’ operation.Instead, the devices are treated as supplied by Eve under the stated laboratory and isolation assumptions.

B. Non-classical correlations

The paper uses private inputs and Bell-type tests to obtain randomness from non-classical correlations, then defines privacy through closeness to an ideal uniform state. Privacy amplification is needed to make raw outputs sufficiently private.

  • Private inputs: Private random inputs are essential because otherwise Eve can precompute outputs that pass Bob’s publicly known tests.Bob therefore begins with a private random string and seeks to generate a longer one.
  • Non-classical correlations: Bell tests are intended to certify non-classical correlations whose intrinsic randomness is uncorrelated with other systems.Verifying these correlations is the intuition underlying private randomness expansion.
  • GHZ test: The GHZ test asks three devices with two settings each to satisfy four product constraints that no classical assignment can satisfy.Entangled quantum measurements can meet the demands, and the paper derives the complete corresponding states and operators in the Appendix.
  • Security definitions: A private random string is modeled as uniformly distributed and uncorrelated with the adversary’s system in an ideal joint state.The paper compares the real state with this ideal form.
  • Security definitions: Security is defined using trace distance, whose non-increase under quantum operations preserves the privacy condition when the string is used.Trace distance also bounds distinguishability between the real and ideal states.
  • Privacy amplification: Raw device outputs typically require privacy amplification to reduce their distance from ideal privacy to an acceptable security level.Privacy amplification is presented as a necessary post-processing step for private randomness expansion.
  • Security definitions: A finite device-independent protocol cannot guarantee non-trivial security with certainty, so the criterion allows a small probability ζ of abort-free non-privacy.The security definition uses both δ, measuring privacy approximation, and ζ, measuring failure probability.

B. Privacy Amplification

Privacy amplification compresses a partially exposed string into one approximately uniform and independent of an adversary’s knowledge. The protocol uses two-universal hashing and characterizes security through smooth conditional min-entropy.

  • Privacy amplification: Privacy amplification compresses X′, partially known to an adversary, into a shorter string S that is approximately uniform and independent of that knowledge.The procedure uses additional randomness R to choose a compression function.
  • Security measure: The extractable private-string length is characterized by the smooth conditional min-entropy of X′ given the adversary’s quantum knowledge E.The smooth min-entropy extends conditional min-entropy to quantum systems and maximizes over nearby states.
  • Choice of extractor: Two-universal hashing is the paper’s focus, while Trevisan-based schemes are noted as alternatives that can require shorter seeds against quantum information.The discussion does not analyze optimality or general attacks.
  • Hashing construction: Two-universal hashing maps X′ to S using a uniformly random, uncorrelated string R, with |S| = 2^t.Theorem 1 bounds the resulting distance from an ideal private state.
  • Protocol setting: Unlike conventional three-party amplification, private randomness expansion involves only Bob, who seeks data secret from Eve and may reveal R during amplification.The protocol therefore treats R as potentially available to Eve while relying on the hashing guarantee.

IV. PROTOCOLS

The protocol begins with three two-setting, binary-output devices supplied by Eve and tests their joint behavior through four GHZ quantities. The devices must satisfy the required output products without communicating.

  • Device triple: Bob requests three devices, each with two inputs and two possible outputs, and treats them together as a device triple.The inputs are P_i and Q_i, and outputs are +1 or −1.
  • GHZ tests: The devices must produce specified products for four GHZ quantities: −1 for P1P2P3 and +1 for the other three combinations.The tested quantities include P1Q2Q3, Q1P2Q3, and Q1Q2P3.
  • Isolation requirement: The device triple must satisfy these conditions without communication among the devices.The protocol’s setup also prevents communication with the outside world, as shown in the figure caption.

Protocol 1

Protocol 1 partitions private randomness, uses part of it to select GHZ tests on isolated devices, and privacy-amplifies the resulting string. Under quantum-constrained attacks, successful tests can yield new private randomness, but security parameters and operational limitations remain.

  • Setup: Bob isolates three devices from one another and from outside communication, then partitions X into X1 and R.The devices learn only their supplied inputs, while the relative partition sizes depend on the privacy-amplification function.
  • Testing: Two bits of X1 select one of four GHZ tests, and each device receives only its own input before Bob combines the outputs.This prevents each device from learning the complete test-selection string.
  • Testing: Bob aborts when the output product is wrong; otherwise he converts valid outputs into two bits and repeats until X1 is exhausted.The resulting bits form the string X̃.
  • Privacy amplification: Bob concatenates X1 and X̃ into X′, computes γ from |X1|, ζ, and δ, and hashes X′ to a γ-bit string S.For two-universal hashing, R and X′ have equal length, requiring 2 log2 |X1| = log |R|.
  • Security intuition: Under quantum-constrained attacks, passing all tests with certainty requires a pure shared state producing unbiased outcomes, which gives Eve no information.In that case, two bits of X1 generate two new random bits each time.
  • Limitations: The protocol’s security analysis leaves the explicit function γ open, and γ may be zero when parameters are too small.The same open problem applies to the noise-tolerant version, where γ also depends on the number of tests passed.
  • Limitations: The generated string is private from Eve but not from the devices, which may remember their outputs and therefore cannot safely receive it as an independent future input.Bob must also prevent signals leaving the laboratory until the private randomness is no longer needed.

Attacks on the initially private string

The paper identifies attacks that can make the initially private string partially insecure, even when used only inside a secure laboratory, and proposes privacy amplification on that string as a remedy.

  • Attack strategy: Eve can program devices so the protocol aborts unless specified bits of X1 take particular values, allowing her to learn information conditioned on protocol behavior.For small m, the devices can preserve a significantly nonzero probability that the protocol does not abort.
  • Practical consequence: If a casino opens or remains open after the protocol, Eve can condition bets on information learned about the purportedly private bits.This attack makes the generated string inconsistent with a sensible definition of private randomness.
  • Relation to earlier work: The earlier protocol in [16] is likewise vulnerable, although its presented version never aborts and can leak information through the final key length.The relevant initial-string portion could be discarded, but this may make the final string shorter than the initial one in practical implementations.
  • Remedy: The proposed protocol applies privacy amplification to X1 as well as to ˜X, directly addressing the initial-string vulnerability.Discarding X1 before amplification is presented as an alternative when the protocol generates enough new randomness.

Iteration via Isolation

The paper extends finite expansion by iterating the protocol across isolated device triples, but rigorous analysis remains incomplete and the construction requires many additional devices.

  • Iteration via Isolation: The extended protocol applies Protocol 1 sequentially to N device triples, using each generated string to operate on the next triple.The triples are arranged so that no two can communicate, for example in separate sub-laboratories.
  • Iteration via Isolation: The construction is intended to suggest that indefinite expansion from a finite private string may be achievable in principle.The initial string must be sufficiently long to securely start the iteration.
  • Iteration via Isolation: The extended protocol has the disadvantage of requiring a large number of additional devices.
  • Iteration via Isolation: Rigorous security analysis of the extended protocol remains a task for future work.The stated limitation concerns the proof status rather than the protocol’s intended operation.

V. TESTS BASED ON OTHER CORRELATIONS

The paper considers higher-party correlation tests to improve expansion rates, illustrating a seven-party GHZ generalization that generates more output randomness than is used for setting selection, while introducing device and seed-length trade-offs.

  • V. TESTS BASED ON OTHER CORRELATIONS: Higher-party generalizations of GHZ correlations are proposed as candidates for improving private-randomness expansion rates while keeping device requirements relatively small.The paper also discusses tests based on CHSH correlations and other input distributions.
  • V. TESTS BASED ON OTHER CORRELATIONS: For k = 2, eight settings use seven two-input, two-output devices, with seven products required to be +1 and the final product −1.These conditions are achieved using PRC’s seven-party generalization of the GHZ state.
  • V. TESTS BASED ON OTHER CORRELATIONS: 3 bits of randomness choose among eight settings, while a successful implementation generates 6 output bits, tripling the private string if Eve is trusted.For larger k, the text describes the expansion as more dramatic.
  • V. TESTS BASED ON OTHER CORRELATIONS: Privacy amplification remains necessary to protect Bob against a dishonest Eve, despite the attractive expansion properties of these tests.
  • V. TESTS BASED ON OTHER CORRELATIONS: Theorem 1 is currently proven only when the randomness selecting the function is perfectly uniform and perfectly uncorrelated with S and E.
  • V. TESTS BASED ON OTHER CORRELATIONS: For large k, analogous protocols are expected to roughly double the private-string length, with potentially greater rate increases when privacy amplification uses a shorter R.
  • V. TESTS BASED ON OTHER CORRELATIONS: Improved rates trade off against requiring more devices and likely requiring a longer initial private string for a given security level.The intuition is based on the higher escape probability available to classical attacks in generalized GHZ tests.

VI. DISCUSSION

The discussion frames private randomness expansion as a practical primitive for untrusted-device settings and considers security beyond quantum adversaries. These prospects remain conditional on no-signalling assumptions and unresolved security proofs.

  • VI. DISCUSSION: Private randomness expansion may serve as a primitive for other protocols involving untrusted devices.The paper also presents nature itself as a possible untrusted adversary supplying devices.
  • VI. DISCUSSION: The nature-based interpretation assumes no-signalling and initial randomness uncorrelated with nature’s subsequent behavior.The paper notes that cosmic conspiracy cannot be ruled out.
  • VI. DISCUSSION: The protocols aim to give ordinary users a virtual guarantee that supplied devices produce private and random outputs without requiring them to construct their own hardware.The motivation is that users may rely on suppliers as they do for computers and encryption software.
  • VI. DISCUSSION: Security against post-quantum adversaries is posed as a possibility under no-signalling constraints between Bob’s devices and between those devices and Eve.A security proof in this scenario remains an open problem.
  • VI. DISCUSSION: Additional private randomness is expected to be generated at a lower rate in the post-quantum scenario because Eve has more general attacks available.Non-local boxes are mentioned as an example of such hypothetical resources.

Appendix

The appendix characterizes tripartite states and two-setting measurement operators satisfying the specified GHZ relations. Under a pure-state assumption, the derivation reduces the operators to Pauli-like forms and identifies the complete solution set up to local unitaries.

  • The method uses a technique based on characterizing states and measurements that maximally violate the CHSH inequality.
  • The appendix seeks the complete set of tripartite states and two-setting measurement devices satisfying the specified relations.
  • The derivation assumes pure tripartite states, with the mixed-state case stated to follow immediately.
  • Schmidt decompositions and projections yield anticommuting operator pairs, which form reducible SU(2) representations restricted to two-dimensional blocks.
  • In a suitable basis, the operators behave as Pauli σx and σy operators, while the state decomposes into subspaces satisfying GHZ relations.
  • The complete set of states and operators satisfying the relations is obtained up to local unitaries.
Loading 1011.4474v3…