PaperlayerView exact revision on arXiv

Source-linked AI summary

Insecurity of position-based quantum cryptography protocols against entanglement attacks

Hoi Kwan Lau, Hoi Kwong Lo

arXiv:1009.2256v3quant-ph

TL;DR

The paper asks whether position-based quantum cryptography remains unconditionally secure against entangled adversaries. It shows that existing protocols can be broken using teleportation and related techniques, then proposes a modified scheme whose analyzed cheating rate is bounded while security is proved for limited shared resources.

  • Problem

    Existing position-based quantum cryptography protocols were claimed to be unconditionally secure, but their security against adversaries sharing entanglement requires examination.

    Source: §I · pp. 1–2

  • Method

    The paper constructs teleportation-, quantum-secret-sharing-, and cluster-state-based attacks, then modifies the protocol so Pauli operators no longer preserve its code space.

    Source: §I · p. 2, B. Cheating against Protocol B in N >… · p. 7, §V · p. 8

  • Results

    Existing protocols are insecure against shared-entanglement attacks, while the modified protocol’s cheating rate is at most 85% and security is proved for shared entangled qubits or qutrits.

    Source: §I · p. 2, §VI · p. 9, §VII · p. 11

  • Takeaways & Limitations

    Pauli-preserving codewords create the common loophole, whereas non-Clifford encoding removes the certainty of the demonstrated cheating strategy within the proved resource scope.

    Source: §V · p. 8, §VII · p. 11, §VIII · p. 11

    The proof covers shared entangled qubits or qutrits, while more complicated resources such as entangled four-level systems are not covered.

    Source: §VII · p. 11

Abstract

from arXiv · show

Recently, position-based quantum cryptography has been claimed to be unconditionally secure. In contrary, here we show that the existing proposals for position-based quantum cryptography are, in fact, insecure if entanglement is shared among two adversaries. Specifically, we demonstrate how the adversaries can incorporate ideas of quantum teleportation and quantum secret sharing to compromise the security with certainty. The common flaw to all current protocols is that the Pauli operators always map a codeword to a codeword (up to an irrelevant overall phase). We propose a modified scheme lacking this property in which the same cheating strategy used to undermine the previous protocols can succeed with a rate at most 85%. We conjecture that the modified protocol is unconditionally secure and prove this to be true when the shared quantum resource between the adversaries is a two- or three- level system.

I. INTRODUCTION

Position-based cryptography uses spatial timing and quantum information to authenticate a prover’s location, but the paper shows that existing PBQC proposals fail against shared entanglement. It introduces the protocols’ procedures and the paper’s two-part agenda: expose the attacks and develop a modified scheme.

I. INTRODUCTION

  • Position-based cryptography aims to prove that a prover occupies a particular location to spatially separated verifiers, with applications including automatic road tolling.Classical position-based cryptography is impossible to secure unconditionally because classical messages can be copied and broadcast by cheaters.Source: §I · p. 1
  • Existing quantum proposals were claimed to be unconditionally secure, but both Protocol A and Protocol B are insecure when cheaters share entanglement.The paper identifies entanglement-enabled non-local operations as the reason cheaters can reproduce the honest response.Source: §I · pp. 1–2
  • The paper aims first to demonstrate entanglement attacks on existing protocols and second to propose and analyze a modified protocol.Its analysis covers two and more reference stations, using teleportation, quantum secret sharing, and cluster-state quantum computation in the cheating constructions.Source: §I · p. 2

II. PBQC PROTOCOLS

  • PBQC sends divided quantum information from separated reference stations so that only the intended position can receive, measure, and answer within the required time.Verification uses the response’s arrival time and error rate, since outsiders lacking complete information should otherwise measure imperfectly or respond too late.Source: §II · p. 2

A. Protocol A

  • Protocol A separates a Hadamard-encrypted qubit from the classical basis bits, while Protocol B distributes locally encrypted qubits from an encoded GHZ state.Protocol A decrypts with H^q and measures in the Z basis; Protocol B decrypts all qubits and performs an N-qubit GHZ measurement.Source: A. Protocol A · p. 2

B. Protocol B

  • Both protocols authenticate the prover by checking whether the announced measurement result is correct and arrives at the expected time.Protocol A relies on missing a classical basis bit causing a wrong basis with half probability, while Protocol B relies on premature measurement likely producing a wrong result.Source: A. Protocol A · p. 2, B. Protocol B · pp. 2–3

C. Dimensionality of PBQC scheme

The paper explains that PBQC’s geometric timing constraints do not prevent attacks: existing protocols can be cheated by entangled adversaries, beginning with a two-station teleportation attack. The claimed security proof for Protocol A fails because it implicitly excludes prior entanglement.

C. Dimensionality of PBQC scheme

  • PBQC verifies higher-dimensional position only when the reference-station geometry surrounds the prover with a suitable polyhedron.The paper notes that four reference stations are necessary when their locations are constrained, and illustrates the condition using a triangle and an interior alternative position.Source: C. Dimensionality of PBQC scheme · p. 3, Figure 1 · p. 3

III. CHEATING IN THE N = 2 CASE

  • Two cheaters positioned just outside the restricted region can reproduce the correct response by the honest deadline, defeating both existing protocols in the N = 2 case.The cheaters occupy positions d−l and d+l while the reference stations expect a response at t = 2d/c.Source: §III · p. 3, Figure 2 · p. 4

A. Flaw in claimed security proof

  • Protocol A’s security proof implicitly assumes that cheaters share no prior entanglement, an assumption invalidated by teleportation-based attacks.The original intuition was that measuring an encrypted qubit necessarily disturbs it, but shared entanglement lets cheaters perform the needed non-local operation.Source: A. Flaw in claimed security proof · p. 4
  • The teleportation circuit transfers an unknown qubit with a Pauli byproduct UΣ determined by random measurement outcomes s1 and s2.The byproduct is UΣ = X^(1−s2)/2 Z^(1−s1)/2.Source: Figure 3 · p. 4

B. Cheating against Protocol A in the N = 2 case

In Protocol A’s N = 2 case, entangled cheaters teleport the encrypted qubit, measure it in the correct basis, and combine their outcomes to answer on time. This succeeds with certainty because Pauli byproducts preserve the X- and Z-eigenstate codewords up to phase or relabeling.

B. Cheating against Protocol A in the N = 2 case

  • The strategy assumes perfect quantum memory so that the cheaters’ qubits remain coherent until measurement.The protocol-facing discussion also emphasizes that exchanging B2’s result does not enable superluminal communication because B1 cannot choose the Bell-measurement outcome deterministically.Source: B. Cheating against Protocol A in the… · pp. 4–5
  • B1 Bell-measures the captured qubit with a shared Bell pair and sends outcomes s1 and s2 to B2, who receives the teleported state immediately.The teleported state is X^(1−s2)/2 Z^(1−s1)/2|u⟩.Source: B. Cheating against Protocol A in the… · p. 4
  • Knowing the basis, B2 measures perfectly because the teleported state remains an eigenstate of the relevant Pauli operator.For the Z basis the outcome is (−1)^(u s2), while for the X basis it is (−1)^(u s1).Source: B. Cheating against Protocol A in the… · p. 4
  • The cheaters complete the entire attack in the honest protocol’s time, so Protocol A is insecure in one dimension.B1 and B2 exchange their outcomes and send the recovered message to the two reference stations at t = 2d/c.Source: B. Cheating against Protocol A in the… · p. 5
  • The attack succeeds with certainty because Protocol A uses only X- and Z-basis codewords, which Pauli operators map to the same or orthogonal code states up to phase.Equivalently, the cheaters can perform the required parity check through a Bell measurement because XX and ZZ commute.Source: B. Cheating against Protocol A in the… · p. 5

C. Cheating against Protocol B in the N = 2 case

In Protocol B with two reference stations, entangled cheaters capture encrypted qubits, decrypt them when transformations arrive, teleport one qubit, and recover the Bell-state message in the honest-case time.

C. Cheating against Protocol B in the N = 2 case

  • The two-station attack uses a Bell-state encoding of 2 bits, with the encoded state represented by one of four Bell states.The message labels are denoted by a and b.Source: C. Cheating against Protocol B in the… · p. 5
  • Cheaters capture and store both encrypted qubits, apply the inverse transformations when received, and use teleportation to bring both encoded qubits together for Bell measurement.The shared Bell state supplies the entanglement needed for teleportation while preserving coherence until decryption information arrives.Source: C. Cheating against Protocol B in the… · p. 5
  • Stabilizer measurements and the communicated outcomes allow the first cheater to reconstruct the original Bell-state labels from the Bell measurement results.The measured outcomes s2 and s3 update the Bell-state labels, enabling recovery of a and b.Source: C. Cheating against Protocol B in the… · p. 5
  • At t = 2d/c, the cheaters deliver the correct results to the reference stations, matching the honest-case completion time and defeating PBQC authentication.The cheating succeeds without requiring a faster response than the protocol expects.Source: C. Cheating against Protocol B in the… · p. 5

IV. CHEATING IN N > 2 CASE

With more than two reference stations, entanglement lets cheaters reproduce the required responses using quantum secret sharing and coordinated measurements, while preserving or shortening the honest timing.

A. Cheating against Protocol A in N > 2 case

  • Three cheaters perfectly defeat the three-station Protocol A attack by sharing a GHZ state, measuring according to received basis bits, and combining the outcomes with a Bell measurement.For an equilateral triangle, the cheaters occupy positions at distance l from P and d − l from the reference stations.Source: §IV · p. 6, A. Cheating against Protocol A in N >… · p. 6
  • The three-cheater Protocol A attack finishes at t = (2d + (3 − 2)l)/c, earlier than the honest time 2d/c, and can be delayed to match the expected response time.The shortcut arises because information travels between cheaters along triangle edges rather than through P.Source: A. Cheating against Protocol A in N >… · pp. 6–7
  • For N > 3, at most N cheaters share an N-particle GHZ state and use basis-dependent measurements to determine the state of one remaining qubit.Parity and stabilizer relations preserve the information needed for the final Bell measurement.Source: A. Cheating against Protocol A in N >… · p. 7
  • The GHZ-based strategy completes in fewer than or the same time as the honest protocol, so increasing the number of reference stations does not restore security.The slowest information arrives no later than the corresponding honest-case timing.Source: A. Cheating against Protocol A in N >… · p. 7

B. Cheating against Protocol B in N > 2 case

For Protocol B with more than two reference stations, three cheaters teleport the encrypted qubits to one location and perform a GHZ-state measurement to recover the encoded message.

B. Cheating against Protocol B in N > 2 case

  • The Protocol B encoding uses three bits represented by one of eight tripartite GHZ-type states.The message bits b1, b2, and b3 determine the phase and correlations among the three qubits.Source: B. Cheating against Protocol B in N >… · p. 7
  • Three cheaters suffice to defeat the three-station Protocol B by capturing encrypted qubits, decrypting them, teleporting two qubits, and concentrating the state at one cheater.The strategy begins with Bell pairs shared between the cheaters and uses the received local transformations to recover the encoded qubits.Source: B. Cheating against Protocol B in N >… · p. 7
  • Teleportation outcomes modify the GHZ-state labels predictably, allowing the first cheater to perform a GHZ measurement and reveal the residual encoded state exactly.The corrected labels depend on the teleportation outcomes and the original message bits.Source: B. Cheating against Protocol B in N >… · p. 7
  • In the equilateral geometry, the cheating process can finish at t = (2d + (3 − 2)l)/c, earlier than the honest completion time 2d/c.For non-equilateral station arrangements, the attack is slower but remains faster than 2d/c in the stated three-station scenarios.Source: B. Cheating against Protocol B in N >… · p. 7

V. PRINCIPLE OF THE CHEATING SCHEMES

The cheating schemes work because Clifford transformations preserve Pauli-basis structure, while Bell measurements reveal parity between qubits in the same basis.

V. PRINCIPLE OF THE CHEATING SCHEMES

  • Teleportation applies Pauli byproducts that leave X-, Y-, and Z-basis eigenstates unchanged up to sign and an irrelevant phase.Thus, encoded eigenstates remain in the same basis after teleportation, enabling exact cheating.Source: §V · p. 8
  • For more than three stations, cluster-state quantum computation generalizes secret sharing and teleportation by implementing the required rotations through local measurements.The cheaters use a 4N − 3-particle chain cluster state, and measurement order is irrelevant because the operations are local.Source: §V · p. 8
  • When all induced rotations are Clifford operators, the cluster-state output differs from the encoded state only by a Pauli product and phase, preserving the exploitable basis structure.The Pauli product can flip |0⟩ to |1⟩ or leave it unchanged, apart from phase.Source: §V · p. 8
  • Bell measurement reveals whether two same-basis qubits have equal or opposite eigenvalues, allowing cheaters to infer the unknown encoded qubit from parity.For X- or Z-basis states, even- and odd-parity states occupy disjoint Bell-measurement outcomes.Source: §V · p. 8

B. Protocol B

Protocol B is insecure because teleportation byproducts preserve its GHZ code space, enabling perfect decoding. The modified scheme uses more general encoded qubit states to block this strategy, but its practical security depends on noise remaining below the cheating rate.

B. Protocol B

  • Teleportation byproducts map Protocol B’s GHZ codewords to other codewords, so standard decoding recovers the teleported state perfectly.The relevant byproducts are single-particle X and Z operators, while the GHZ encoding differs only by bit and phase flips.Source: B. Protocol B · p. 8

VI. MODIFIED PBQC SCHEME

  • The modified protocol encodes messages as ±1 eigenstates of arbitrary Pauli directions n(θ, φ)·σ rather than only X- or Z-eigenstates.The rotation parameters satisfy 0 ≤ θ ≤ π and 0 ≤ φ ≤ 2π.Source: §VI · p. 9
  • For the modified one-dimensional protocol, teleportation cannot make the received state parallel or antiparallel to the original, preventing perfect measurement before the first cheater’s outcomes arrive.The resulting response would reach the verifiers no earlier than 2(d + l)/c, later than the honest timing constraint.Source: §VI · p. 9
  • With more reference stations, non-Clifford rotations prevent the encrypted state from transforming between the relevant code states, so cluster-state cheating requires too much time.The paper concludes that the cheaters cannot obtain the correct result within the honest-case timing.Source: §VI · p. 9
  • In practice, the honest system’s total error rate must remain below the successful cheating rate, or cheating failures may be mistaken for operational noise.The qualification applies to quantum operations, channels, and measurements, which are not noiseless.Source: §VI · p. 9
  • The teleportation strategy succeeds at about 85% in the one-dimensional modified protocol, and numerical checks identify this as the highest rate over measurement bases.Simpler strategies achieve 50% or 75%, while the multi-station case is anticipated to have a lower rate because it requires more measurements.Source: §VI · pp. 9–10

VII. SECURITY OF MODIFIED PROTOCOL

The modified protocol resists perfect cheating for arbitrary shared 2-qubit resources and strategies, and extends this security to more than two reference stations. Its general unconditional security remains open for higher-dimensional entangled resources.

One-dimensional case

  • Cheaters can distinguish the encoded qubit only when each measurement state superposes at most two basis states with the required codeword associations.If both encoded states contribute to the same measurement component, the cheaters cannot identify which state was sent.Source: §VII · pp. 10–11
  • Perfect cheating is impossible for the modified protocol with any shared 2-qubit state and any strategy, except the special θ = π/2 encoding case associated with Pauli X, Y, and Z eigenstates.The analysis identifies the measurement constraints that prevent cheaters from distinguishing encoded states for general θ.Source: §VII · p. 11

More than two reference stations

  • For N > 2 reference stations, no perfectly successful cheating strategy exists because setting U3, ..., UN to identity reduces the problem to the secure one-dimensional case.The contradiction uses the two maximally separated stations and the minimum communication time between cheaters.Source: §VII · p. 11

Scope of security proof

  • The proof covers shared two- and three-level systems, but more complicated resources such as entangled four-level systems are outside the analytic proof.The authors conjecture that higher-level entanglement remains secure because its measurements should yield more random outcomes, but leave this unproved.Source: §VII · p. 11

VIII. SUMMARY

The paper explains that existing PBQC protocols are broken by entanglement-based nonlocal operations, then modifies the encoding so Pauli byproducts leave the code space. The modified protocol is secure for qubits and qutrits, while the broader security question remains open.

Summary

  • Teleportation, quantum secret sharing, and CSQC let cheaters distribute quantum information before all basis information arrives, then correct random measurement outcomes through classical communication.The one-dimensional and higher-dimensional attacks differ operationally but share this underlying mechanism.Source: §VIII · p. 11
  • The modified protocol uses non-Clifford encoding so Pauli byproducts no longer preserve the code space; cheating succeeds at most 85%.The reported highest average cheating rate is 75% without entanglement and 85% when the cheating scheme is employed.Source: §VIII · p. 11
  • Security is proved when each cheater shares entangled qubits or a qutrit, while security against more general entangled resources is conjectured rather than proved.The paper also identifies finite entanglement and private shared secrets as open directions.Source: §VIII · p. 11

Practical considerations

  • For reference-station separations of about 100 km, the assumed fast-operation regime is considered compatible with nanosecond-scale optical quantum computation.The paper estimates a round-trip signal time of about 100 µs and a cheating-induced deviation on the µs scale.Source: §VIII · pp. 11–12

Appendix A: Security of shared 3-level system

Appendix A proves security against a shared entangled three-level system by constraining the possible measurement basis and showing that a complete orthogonal basis satisfying those constraints cannot exist.

Conclusion

  • Therefore the modified protocol is secure when two cheaters share an entangled three-level system, extending the claimed security to the N > 2 reference-station setting.The one-dimensional case is treated as a special case of the multi-station argument.Source: Appendix A · p. 12

General n-level analysis

  • The appendix studies certainty cheating in an n-level system by representing basis-dependent states with an n×n unitary transformation and imposing constraints on the cheaters’ measurement states.Each measurement state must avoid containing both |φ_j⟩|0⟩ and |φ_j⟩|1⟩ for the same j.Source: Appendix A · p. 12

Three-level proof

  • Successful cheating requires the absolute-square coefficients associated with |0⟩ in every measurement state to sum to 1.This restriction limits the measurement structures available to the first cheater.Source: Appendix A · p. 12
  • For a three-level shared system, no complete orthogonal measurement set can satisfy the required component structure and orthogonality relations.The proof shows that states sharing the same three components cannot supply the required additional orthogonal state.Source: Appendix A · pp. 12–13
Loading 1009.2256v3…