Florian Speelman

Location can be strongly correlated to trust and identity: For example, when visiting a bank, you might trust the teller just by virtue of her position behind the counter. We would like to be able to use position as a cryptographic credential, being able to encrypt messages that can only be read at a certain location, or signing messages so that we are sure that they are sent from a promised spot. In this tutorial, we will study the task of quantum position verification (QPV) - where an untrusted party uses quantum information to prove their location, which enables more advanced tasks such as encrypting messages to be only read at a certain location. This is impossible to achieve if all communication and computation is classical, even under computational assumptions, and is an exciting possible use of quantum communication. In the session, we will start with an overview of basic protocols, inspired by BB84 quantum key distribution, and their security proofs. We will then go over some experimental obstacles on implementing such protocols in practice, and how to modify the protocols to overcome them. On the theoretical side, the QPV task turns out to be connected to the AdS/CFT correspondence, and to various topics in quantum communication and cryptography, because attacks require a form of non-local quantum computation (NLQC). We will go over these connections, and survey open questions on this topic.

Signal loss poses a significant threat to the security of quantum cryptography when the chosen protocol lacks loss-tolerance. In quantum position verification (QPV) protocols, even relatively small loss rates can compromise security. The goal is thus to find protocols that remain secure under practically achievable loss rates. In this work, we modify the usual structure of QPV protocols and prove that this modification makes the potentially high transmission loss between the verifiers and the prover security-irrelevant for a class of protocols that includes a practically-interesting candidate protocol inspired by the BB84 protocol. This modification, which involves photon presence detection, a small time delay at the prover, and a commitment to play before proceeding, reduces the overall loss rate to just the prover’s laboratory. The adapted protocol then becomes a practically feasible QPV protocol with strong security guarantees, even against attackers using adaptive strategies. As the loss rate between the verifiers and prover is mainly dictated by the distance between them, secure QPV over longer distances becomes possible. We also show possible implementations of the required photon presence detection, making the adapted protocol a protocol that solves all major practical issues in QPV. Finally, we discuss experimental aspects and give parameter estimations.

We provide a generic construction to turn any classical Zero-Knowledge (ZK) protocol into a composable (quantum) oblivious transfer (OT) protocol, mostly lifting the round-complexity properties and security guarantees (plain-model/statistical security/unstructured functions…) of the ZK protocol to the resulting OT protocol. Such a construction is unlikely to exist classically as Cryptomania is believed to be different from Minicrypt. In particular, by instantiating our construction using Non-Interactive ZK (NIZK), we provide the first round-optimal (2-message) quantum OT protocol secure in the random oracle model, and round-optimal extensions to string and k-out-of-n OT. At the heart of our construction lies a new method that allows us to prove properties on a received quantum state without revealing additional information on it, even in a non-interactive way and/or with statistical guarantees when using an appropriate classical ZK protocol. We can notably prove that a state has been partially measured (with arbitrary constraints on the set of measured qubits), without revealing any additional information on this set. This notion can be seen as an analog of ZK to quantum states, and we expect it to be of independent interest as it extends complexity theory to quantum languages, as illustrated by the two new complexity classes we introduce, ZKstatesQIP and ZKstatesQMA.

We give a tight characterization of the relation between loss-tolerance and error rate of the most popular protocol for quantum position verification (QPV), which is based on BB84 states, and generalizations of this protocol. Combining it with classical information, we show for the first time a fault-tolerant protocol that is secure against attackers who pre-share a linear amount of entanglement (in the classical information), arbitrarily slow quantum information and that tolerates a certain amount of photon loss. We also extend this analysis to the case of more than two bases, showing even stronger loss-tolerance for that case. Finally, we show that our techniques can be applied to improve the analysis of one-sided device-independent QKD protocols.

We give a tight characterization of the relation between loss-tolerance and error rate of the most popular protocol for quantum position verification (QPV), which is based on BB84 states, and generalizations of this protocol. Combining it with classical information, we show for the first time a fault-tolerant protocol that is secure against attackers who pre-share a linear amount of entanglement (in the classical information), arbitrarily slow quantum information and that tolerates a certain amount of photon loss. We also extend this analysis to the case of more than two bases, showing even stronger loss-tolerance for that case. Finally, we show that our techniques can be applied to improve the analysis of one-sided device-independent QKD protocols.

While it is known that unconditionally secure position-based cryptography is impossible both in the classical and the quantum setting, it has been shown that some quantum protocols for position verification are secure against attackers which share a quantum state of bounded dimension. In this work, we consider the security of the qubit routing protocol. The protocol has the advantage that an honest prover only has to manipulate a single qubit and a classical string of length 2n. We show that the protocol is secure if each of the attackers holds at most n/2 - 3 qubits. With this, we show for the first time that there exists a quantum position verification protocol where the ratio between the quantum resources an honest prover needs and the quantum resources the attackers need to break the protocol is unbounded. The verifiers need only increase the amount of classical resources to force the attackers to use more quantum resources. Finally, we show that the qubit routing protocol is robust with respect to noise, making it appealing for applications.

The strong exponential-time hypothesis (SETH) is a commonly used conjecture in the field of complexity theory. It states that CNF formulas cannot be analyzed for satisfiability with a speedup over exhaustive search. This hypothesis and its variants gave rise to a fruitful field of research, fine-grained complexity, obtaining (mostly tight) lower bounds for many problems in P whose unconditional lower bounds are hard to find. In this work, we introduce a framework of Quantum Strong Exponential-Time Hypotheses, as quantum analogues to SETH. Using the QSETH framework, we are able to translate quantum query lower bounds on black-box problems to conditional quantum time lower bounds for many problems in BQP. As an example, we illustrate the use of the QSETH by providing a conditional quantum time lower bound of $\Omega(n^{1.5})$ for the Longest Common Subsequence and Edit Distance problems. We also show that the $n^2$ SETH-based lower bound for a recent scheme for Proofs of Useful Work, based on the Orthogonal Vectors problem, holds for quantum computation assuming QSETH, maintaining a quadratic gap between verifier and prover.

We introduce Port-Based State Preparation (PBSP), a teleportation task where Alice holds a complete classical description of the target state and Bob's correction operations are restricted to only tracing out registers. We show a protocol that implements PBSP with error decreasing exponentially in the number of ports, in contrast to the polynomial trade-off for the related task of Port-Based Teleportation, and we prove that this is optimal when a maximally entangled resource state is used.

Motivated by the fact that coherent states may offer practical advantages it was recently shown that a continuous-variable (CV) quantum position verification (QPV) protocol using coherent states could be securely implemented if and only if attackers do not pre-share any entanglement. In the discrete-variable (DV) analogue of that protocol it was shown that modifying how the classical input information is sent from the verifiers to the prover leads to a favourable scaling in the resource requirements for a quantum attack. In this work, we show that similar conclusions can be drawn for CV-QPV. By adding extra classical information of size $n$ to a CV-QPV protocol, we show that the protocol, which uses a coherent state and classical information, remains secure, even if the quantum information travels arbitrarily slow, against attackers who pre-share CV (entangled) states with a linear (in $n$) cutoff at the photon number. We show that the protocol remains secure for certain attenuation and excess noise.

Extended non-local games are a generalization of monogamy-of-entanglement games, played by two quantum parties and a quantum referee that performs a measurement on their local quantum system. Along the lines of the NPA hierarchy, the optimal winning probability of those games can be upper bounded by a hierarchy of semidefinite programs (SDPs) converging to the optimal value. Here, we show that if one extends such games by considering constraints and loss, motivated by experimental errors and loss through quantum communication, the convergence of the SDPs to the optimal value still holds. We give applications of this result, and we compute SDPs that show tighter security for certain protocols in quantum cryptography such as relativistic bit commitment, quantum key distribution and quantum position verification.

In this work, we study loss-tolerant quantum position verification (QPV) protocols. We propose a new fully loss-tolerant protocol, based on the SWAP test, with several desirable properties. The task of the protocol, which can be implemented using only a single beam splitter and two detectors, is to estimate the overlap between two input states. By formulating possible attacks as a semi-definite program (SDP), we prove full loss tolerance against unentangled attackers restricted to local operations and classical communication (LOCC), and additionally show that the attack probability decays exponentially under parallel repetition of rounds. Furthermore, we investigate the role of loss and quantum communication attacks in QPV in general. A protocol that is provably secure against unentangled attackers restricted to LOCC, but can be perfectly attacked by local operations and a single round of simultaneous quantum communication, is constructed. However, we show that any protocol secure against classical communication can be transformed into a protocol secure against quantum communication. Finally, we observe that any QPV protocol can be attacked with a linear amount of entanglement if the loss is high enough.