Position-based quantum cryptography and its attacks

Short answer: Position-based quantum cryptography aims to use a party's geographical position as its only credential. A 2010 arXiv paper shows that proposals then claimed to be unconditionally secure are insecure if two adversaries share entanglement, a 2014 SIAM paper proves that secure position verification is impossible if adversaries can share an arbitrarily large entangled state, and a 2022 arXiv paper studies how quantum communication affects attacks. These are theory results, with no deployed system.

The Core Security Challenge

The fundamental objective of position-based cryptography is to leverage the physical location of a party as its only credential. The 2010 paper says position-based quantum cryptography had recently been claimed to be unconditionally secure, and shows that the existing proposals are in fact insecure if entanglement is shared among two adversaries. The authors say the common flaw is that Pauli operators always map a codeword to another codeword, up to an irrelevant overall phase. This structural weakness allows adversaries to incorporate ideas from quantum teleportation and quantum secret sharing to compromise the security with certainty.

Impossibility Results with Entanglement

The 2014 SIAM paper reports a negative result: if adversaries are allowed to share an arbitrarily large entangled quantum state, the task of secure position-verification is impossible. The authors prove a general result about how many rounds of communication are needed to compute a unitary on a shared state. Specifically, if Alice and Bob hold subsystems of an unknown quantum state and share enough entanglement to start with, they can perform tasks that would otherwise require multiple rounds of communication using only a single round of classical communication. In fact, a relaxed version of the task can be done with no communication at all if the goal is to compute a state that coincides with the target up to local operations determined by classical information. They derive a generic attack that breaks any position-verification scheme, and say the results generalize to more players.

Constraints on Communication Resources

The 2022 authors study the role of quantum communication in attacks. They construct what they describe as the first known example of a quantum position verification (QPV) protocol that is provably secure against unentangled attackers restricted to classical communication. However, this same protocol can be perfectly attacked if local operations and a single round of simultaneous quantum communication are allowed. They say this indicates that allowing quantum communication may break security. They also show that any protocol secure against classical communication can be transformed into one secure against quantum communication.

Loss-Tolerant Tasks and Bell State Discrimination

Using arguments based on the monogamy of entanglement, the 2022 authors show that the task of Bell state discrimination cannot be done locally with a single round of quantum communication. This holds true even probabilistically, when attackers are allowed to say "loss" sometimes. They say this makes it the first fully loss-tolerant position-verification task secure against quantum communication attacks. The proof relies on bounding the squashed entanglement of the state on which the honest Bell measurement is applied. They also observe that any multi-round position-verification protocol can be attacked with a linear amount of entanglement if the loss is high enough.

FAQ

Can adversaries break PBQC with shared entanglement?

According to the 2014 paper, if adversaries can share an arbitrarily large entangled state, secure position verification is impossible. The 2010 paper shows that cheaters can use entanglement for non-local operations that reproduce the honest response.

Why were early PBQC protocols considered insecure?

The 2010 authors say the common flaw was that Pauli operators always map a codeword to a codeword, which let adversaries use ideas from quantum teleportation and quantum secret sharing to compromise security with certainty.

Does restricting communication to classical channels ensure security?

Not for quantum attacks. The 2022 authors construct a protocol secure against unentangled attackers limited to classical communication that can be perfectly attacked with local operations and a single round of simultaneous quantum communication.

Is Bell state discrimination secure against quantum communication attacks?

The 2022 authors show that Bell state discrimination cannot be done locally with a single round of quantum communication, even probabilistically, using monogamy of entanglement arguments, and call it the first fully loss-tolerant task of this kind.

What happens if loss is high in multi-round protocols?

The 2022 authors observe that any multi-round position-verification protocol can be attacked with a linear amount of entanglement if the loss is high enough.