PaperlayerView exact revision on arXiv

Source-linked AI summary

Position-Based Quantum Cryptography: Impossibility and Constructions

Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner

arXiv:1009.2490v4quant-phcs.CR

TL;DR

The paper asks whether geographical position can serve as the only credential for secure cryptography in the quantum setting, especially under different entanglement assumptions. It uses instantaneous nonlocal quantum computation to analyze attacks and constructs protocols in the No-PE model. Large pre-shared entanglement breaks any position-verification scheme of the general form considered, while no pre-shared entanglement permits secure position-verification and related protocols.

  • Problem

    The paper asks whether position-based cryptography is realizable in quantum settings beyond prior impossibility results and storage-restricted constructions.

  • Method

    The paper studies entanglement-assisted instantaneous nonlocal quantum computation and analyzes position-based protocols in a model prohibiting dishonest provers from pre-sharing entanglement.

  • Results

    Large pre-shared entanglement lets adversaries break any position-verification scheme of the general form considered, while No-PE protocols achieve secure position-verification and related tasks.

  • Takeaways & Limitations

    Position-based authentication and key exchange can be constructed in settings where secure position-verification is achievable.

  • Takeaways & Limitations

    The threshold amount of pre-shared entanglement that preserves security remains unknown.

Abstract

from arXiv · show

In this work, we study position-based cryptography in the quantum setting. The aim is to use the geographical position of a party as its only credential. On the negative side, we show that if adversaries are allowed to share an arbitrarily large entangled quantum state, no secure position-verification is possible at all. We show a distributed protocol for computing any unitary operation on a state shared between the different users, using local operations and one round of classical communication. Using this surprising result, we break any position-verification scheme of a very general form. On the positive side, we show that if adversaries do not share any entangled quantum state but can compute arbitrary quantum operations, secure position-verification is achievable. Jointly, these results suggest the interesting question whether secure position-verification is possible in case of a bounded amount of entanglement. Our positive result can be interpreted as resolving this question in the simplest case, where the bound is set to zero. In models where secure positioning is achievable, it has a number of interesting applications. For example, it enables secure communication over an insecure channel without having any pre-shared key, with the guarantee that only a party at a specific location can learn the content of the conversation. More generally, we show that in settings where secure position-verification is achievable, other position-based cryptographic schemes are possible as well, such as secure position-based authentication and position-based key agreement.

1 Introduction

The paper asks whether position-based cryptography can be realized in the quantum setting after prior work established strong impossibility and restricted-model constructions. It shows that large pre-shared entanglement breaks general position-verification, while no pre-shared entanglement supports secure position-based protocols.

  • 1.1 Background: Position-based cryptography uses geographical location as a party’s only credential, with position-verification as its central task.Position-verification asks verifiers to distinguish an honest prover at a claimed location from colluding provers elsewhere.
  • 1.1 Background: Prior work showed that colluding adversaries defeat secure positioning, while the Bounded-Retrieval Model constructs protocols under storage restrictions.The authors describe the bounded-storage assumption as relatively difficult to justify in practice.
  • 1.2 Our Approach and Our Results: The paper investigates whether quantum information can circumvent classical impossibility through the no-cloning principle, but pre-shared entanglement enables teleportation-based attacks.The initial no-cloning intuition therefore does not suffice when adversaries share entangled states.
  • 1.2 Our Approach and Our Results: Instantaneous nonlocal quantum computation lets entangled adversaries apply any shared-state unitary using local operations and one round of classical communication, breaking general position-verification.The attack extends beyond one-round protocols to schemes with multiple, interleaved rounds.
  • 1.2 Our Approach and Our Results: Secure protocols for position-verification, authentication, and key exchange exist when dishonest provers cannot pre-share or maintain entanglement.The amount of entanglement separating the fully insecure and information-theoretically secure cases remains unknown.

2 Preliminaries

The preliminaries establish notation for qubits, hybrid quantum-classical states, density matrices, entropy, and teleportation. They also introduce entropic tools used to bound uncertainty and distinguishability in the security proofs.

  • 2.1 Notation and Terminology: A qubit has state space C2, while an n-qubit system has state space (C2)^⊗n.The computational and Hadamard bases are used throughout the paper.
  • 2.1 Notation and Terminology: Measuring an n-qubit state in basis θ ∈{0,1}^n means measuring each qubit in the computational or Hadamard basis selected by θ_i.The observed string x has probability |⟨ψ|H^θ|x⟩|^2.
  • 2.2 Some Quantum Information Theory: Trace distance measures how distinguishable two density matrices are, with small distance implying indistinguishable behavior under physical processing.The von Neumann entropy and conditional entropy quantify uncertainty in quantum systems.
  • 2.2 Some Quantum Information Theory: A hybrid state combines a classical variable with a quantum system whose conditional state depends on the variable’s value.This formalism extends naturally to multiple classical and quantum subsystems.
  • 2.2 Some Quantum Information Theory: Teleportation transfers an unknown quantum state using classical communication and pre-shared entanglement, with Pauli corrections determined by a Bell-measurement outcome.The receiver applies the corresponding correction after receiving the classical outcome.
  • 2.2 Some Quantum Information Theory: The strong complementary information tradeoff bounds simultaneous information about measurement outcomes in complementary bases.It guarantees that at most one system can have full information about both possible outcomes.

3 Setup and The Task of Position Verification

The paper defines position-verification in a space-time model with quantum-capable verifiers, provers, and communication. Its positive security analysis uses a No-PE restriction forbidding pre-shared entanglement between dishonest provers.

  • 3.1 The Security Model: The standard model allows verifiers, honest provers, and dishonest prover coalitions to perform arbitrary quantum or classical operations and exchange quantum or classical messages.The No-PE model additionally prohibits dishonest provers from entering a round with pre-shared entanglement or carrying it into the next round.
  • 3.1 The Security Model: Messages travel at fixed velocity, positions determine transmission times, and synchronized verifier clocks support precise timing checks.The honest prover’s clock need not be synchronized, but the prover cannot be reset.
  • 3.1 The Security Model: A verifier can infer that a prover lies within distance d(pos0,pos) when a reply arrives within time 2d(pos0,pos).This is the timing basis for distance bounding.
  • 3.2 Secure Position Verification: Position-verification requires acceptance for an honest prover at pos and rejection with high probability for colluding provers located elsewhere.The honest prover has no secret or authentication advantage beyond being at the claimed position, and is enclosed by the verifiers.
  • 3.2 Secure Position Verification: Verifiers send challenges so they arrive at the claimed position simultaneously, then check responses for correctness and arrival time.Soundness bounds acceptance probability by ε for dishonest coalitions at positions different from pos, subject to a minimum distance Δ from pos.

4 Instantaneous Nonlocal Quantum Computation

The paper introduces instantaneous nonlocal quantum computation: shared entanglement lets separated parties implement arbitrary unitaries using local operations and one round of mutual classical communication. Repeated teleportation reduces failure probability, but the construction requires double-exponentially many EPR pairs in the joint qubit size.

  • Task: Instantaneous nonlocal quantum computation applies a known unitary to a state distributed between Alice and Bob without communication, leaving only locally determined corrections.Alice and Bob obtain classical information that determines the local, qubit-wise operations needed to interpret the output.
  • Construction: Sufficiently many shared EPR pairs enable local operations and one round of mutual communication to implement every unitary U except with probability ε.The guarantee holds for every initial tripartite state, including states entangled with an external system E.
  • Construction: The construction extends to families of unitaries U_x,y selected by classical inputs held separately by Alice and Bob.The corresponding local operations A_x and B_y produce classical outputs that determine the remaining corrections, except with probability ε.
  • Construction: The protocol teleports states back and forth without immediately communicating Bell-measurement outcomes, using labeled teleportation channels and local corrections.Alice first teleports the input to Bob, Bob applies input-dependent unitaries and teleports states back, and Alice designates the resulting state as the output.
  • Error reduction: Repeated teleportation rounds preserve the quantum input size and succeed with constant probability per round, yielding arbitrarily small overall failure probability.Each round succeeds when Alice’s teleportation outcome is all zero, with probability 1/4^n; otherwise the procedure is re-applied to a transformed instance.
  • Resource requirements: Double exponentially many EPR pairs are required in the construction as a function of the joint quantum system’s qubit size.Subsequent work reduced this requirement to exponential, while whether exponential entanglement is necessary remains open.

5 Impossibility of Unconditional Position Verification

The paper proves that, in the Vanilla model, two separated quantum adversaries can perfectly simulate an honest prover’s computation and timing. Therefore, verifiers cannot distinguish the honest prover’s position from colluding provers elsewhere.

  • Impossibility result: No position-verification scheme is secure against a coalition of quantum adversaries in the Vanilla model.The stated one-dimensional attack with two verifiers generalizes to higher dimensions and more verifiers.
  • Protocol model: An honest prover’s protocol step consists of applying a fixed unitary U to inputs from both verifiers and a local register R.The verifiers retain a system E, while the prover receives systems A and B and maintains R.
  • Attack: Two dishonest provers can perfectly simulate the honest prover’s actions, making their computation and response timing indistinguishable to the verifiers.The simulation uses instantaneous local operations followed by one mutual round of classical communication.
  • Attack: The adversaries maintain an invariant in which the joint state matches the honest state up to local, qubit-wise operations on the prover’s register R.The correction information is distributed between the dishonest provers as classical values known locally.
  • Attack: After exchanging their classical outputs, the dishonest provers remove corrections from A and B up to residual corrections on R, then return the verifier-bound systems.The resulting state of ABE and the elapsed time are identical to those of an honest prover for the simulated step.

6 Secure Position-Verification in the No-PE model

In the No-PE model, a BB84-based position-verification scheme achieves secure positioning, and sequential repetition reduces its soundness error. The construction extends to higher dimensions, while parallel repetition remains without a security proof.

  • 6.1 Basic Scheme and its Analysis: The basic one-round scheme PVε uses BB84 encoding for position verification in the No-PE model.The verifiers time a qubit and basis challenge to arrive simultaneously at the claimed position, where the prover measures and returns the encoded bit.
  • 6.1 Basic Scheme and its Analysis: Without pre-shared entanglement, dishonest provers must split the received qubit before learning the measurement basis.The resulting bipartite state is independent of the basis, enabling an uncertainty-based bound on their joint ability to recover the encoded bit.
  • 6.1 Basic Scheme and its Analysis: The provers’ acceptance probability is upper bounded by ε, and additional dishonest provers do not improve their success probability.The same argument applies when dishonest provers jointly transform the qubit on one side and distribute the output across the other side.
  • 6.2 Reducing the Soundness Error: Sequentially repeating PVε BB84 n times reduces the soundness error to ε^n in the No-PE model.Each round starts without pre-shared entanglement, so security follows from the one-round scheme.
  • 6.2 Reducing the Soundness Error: Parallel repetition lowers round complexity, but the paper does not prove its security.The parallel protocol sends n BB84 qubits and corresponding basis challenges simultaneously, requiring the prover to return the full list in time.
  • 6.3 Position Verification in Higher Dimensions: The BB84 construction generalizes to d dimensions by using basis shares whose modulo-2 sum reconstructs the measurement basis.Security is argued by reduction to the one-dimensional scheme.

7 Position-Based Authentication and Key-Exchange

The paper defines position-based authentication, constructs weak and strong schemes from position verification, and proves completeness and soundness in the No-PE model. It also derives position-based key exchange from BB84 QKD and position-based authentication.

  • Definition: Position-based authentication verifies that a message originates from a prover at the claimed position, rather than merely verifying the prover’s location.The verifiers compare an input message m′ and claimed position against the prover’s authenticated message m.
  • Weak 1-bit authentication scheme: The weak scheme authenticates a 1-bit message by returning the position-verification response for m = 1 and randomly replacing it with ⊥ for m = 0.The replacement probability is q, while verifiers accept either the correct response or ⊥ when m = 0.
  • Weak 1-bit authentication scheme: The weak scheme has impersonation success at most ε and substitution success δ = 1 − q(1 − ε) < 1 for the specified attack.Dishonest provers can authenticate m′ = 0 by substitution with success probability 1, so the weak scheme is asymmetric.
  • Strong authentication: Bit-wise authentication of a balanced encoding is insufficient because verifier–prover asynchrony lets an adversary shift indices and exploit the honest prover’s responses.The construction therefore uses λ-dominating codes and statistics over received ⊥ symbols.
  • Strong authentication: The generic scheme AUTH is N e^-2qλ-complete and 2^-Ω(λ)-sound in the No-PE model when ε > 0 and 0 < q < (1 − ε)/8.Completeness follows from a Chernoff bound and union bound; soundness is established for λ-dominating encodings.
  • Key exchange: Combining the construction with secure position verification yields position-based authentication in R^d, while BB84 QKD yields position-based key exchange.The key-exchange security follows from BB84 security and the position-based authentication scheme.

8 Conclusion and Open Questions

The paper proves that information-theoretic quantum position verification is impossible against adversaries with arbitrarily large pre-shared entanglement, while secure schemes exist in the No-PE model. The amount of entanglement needed to break position verification remains open.

  • Conclusion: Information-theoretic position-verification quantum schemes are impossible when adversaries may share arbitrarily large entangled states.The proof answers negatively the open question concerning the security of schemes proposed in [KMS10].
  • Conclusion: The paper also provides schemes secure when dishonest provers do not use pre-shared entanglement.The supported constructions include position verification, authentication, and key exchange.
  • Open questions: The threshold amount of pre-shared entanglement that preserves security is unknown.The paper explicitly poses bounded-entanglement and bounded-quantum-storage models as open questions.

A.1 Proof of Lemma 2.1

This appendix proves Lemma 2.1 for tripartite quantum states with a classical register by first analyzing an empty B register and then extending the entropy argument.

  • Lemma statement: Lemma 2.1 is stated for any tripartite state ρ_ABY in which Y is classical.The proof proceeds by examining the structure of the state and its entropy.
  • Proof: When B is empty, the classicality of Y gives ρ_AY a block structure whose eigenvalues are determined by P_Y(y) and the eigenvalues of the conditional states.This decomposition supports the entropy calculation used in the proof.
  • Proof: The resulting entropy inequalities establish the lemma’s claim.The appendix states that the derived relation completes the proof.

A.2 Proof of Corollary 2.5

The appendix applies the complementary information trade-off to measurements in complementary bases and derives a lower bound on the combined conditional entropies.

  • Measurement construction: The proof represents X_E as the outcome of measuring A in basis θ while ignoring F, and X_F as the complementary-basis outcome while ignoring E.These definitions place the two measurement outcomes in the setting required by Theorem 2.4.
  • Entropy bound: Theorem 2.4 yields H(X_F|F) ≥ n and therefore H(X|ΘE) + H(X|ΘF) ≥ n.The displayed bound is the corollary obtained from the two complementary measurements.

B Instantaneous Nonlocal Quantum Computation With N Parties

The paper generalizes instantaneous nonlocal quantum computation to N parties, where local operations and shared EPR pairs implement input-dependent unitaries up to local Pauli corrections, with arbitrarily small failure probability.

  • N-party generalization: The N-party construction lets Alice and users U1,…,U_N−1 apply a unitary Ux,y1,…,yN−1 to a shared state up to local qubit-wise corrections determined by classical outputs.Alice holds system A and input x; each user Up holds system Bp and input yp.
  • Proof strategy: The proof proceeds by induction on the number of parties, reducing the N = c + 1 case to the previously established two-party and c-party cases.The base cases are N = 1, which is trivial, and N = 2, which was already proven.
  • Protocol construction: Alice teleports the input state to U1 through the channel selected by x, while U1,…,Uc run the induction protocol on every candidate channel.The teleportation measurement produces a classical outcome k◦, and the candidate states are indexed by i = 1,…,|X|.
  • Protocol construction: When Alice’s teleportation outcome is all zeroes, the users compute Ux,y1,…,yc on the selected channel and obtain the desired state up to local corrections.The resulting corrections are determined by the users’ classical outputs ℓx1,…,ℓxc and Alice’s later teleportation outcome.
  • Proof strategy: For nonzero teleportation outcomes, the protocol folds the outcomes into new classical inputs and recursively reapplies the procedure to the resulting instance.The transformed state and inputs define another instance of the same distributed-unitary problem.
  • Success guarantee: A constant success probability per round, depending only on dim H_all, means sufficiently many shared EPR pairs reduce the overall failure probability below any ε > 0.Repeated application eventually yields the required state except with arbitrarily small probability.
Loading 1009.2490v4…