Science
Science: physics, biology, chemistry, astronomy and space, neuroscience, and research explained.
-
Practical position-based quantum cryptography (2015) doi.org
Considers the case where the two input bases are related by a unitary $U$.
-
Loss-tolerant position-based quantum cryptography (2015) doi.org
Generalises BB84 QPV to more input bases and notes better loss tolerance properties because of it. Also discusses using decoy states and continuous variables for BB84 QPV.
-
Quantum tagging for tags containing secret classical data (2011) doi.org
Considers QPV in the setting when the verifiers and the prover pre-share a secret. Shows that then QPV is unconditionally secure by indefinitely expanding the secret using QKD.
-
Introduces a rooster of different QPV protocols like BB84 QPV, $f$-routing, $f$-BB84 QPV and variations of them. Mentions entanglement-based attacks on some of them.
-
Insecurity of position-based quantum cryptography protocols against entanglement attacks (2011) doi.org
Proves insecurity of QPV protocols that were previously claimed secure and studies general principle underlying entanglement attacks. Studies variations of QPV protocols based on Bell/GHZ states and shows that using eigenstates other than Pauli $X$, $Y$, $Z$ leads to protocols…
-
Location-dependent communications using quantum entanglement (2010) doi.org
Introduces QPV in the academic literature, but incorrectly claims unconditional security. Studies QPV based on Bell states.
-
Towards experimental demonstration of quantum position verification using single photons (2025) doi.org
A first demonstration experiment of QPV using the SWAP protocol, with single photons from a single semiconductor quantum dot in an optical microcavity.
-
Practically secure quantum position verification (2021) doi.org
Gives an overview over the existing protocols at the time and mixes elements of them to obtain different variations of those protocols.
-
A monogamy-of-entanglement game with applications to device-independent quantum cryptography (2013) doi.org
Shows a tight upper bound for unentangled attacks, parallel repetition and a linear lower bound for the repeated protocol.
-
Provides a general attack on QPV based on port-based teleportation, using an exponential amount of pre-shared EPR pairs in the number of input qubits. Also provides a QPV protocol with a provably linear lower bound.
-
Quantum tasks in Minkowski space (2012) doi.org
Considers more general quantum tasks than QPV.
-
Quantum position verification in bounded-attack-frequency model (2016) doi.org
Considers BB84 QPV with non-simultaneous arrival times of input information at the prover (the basis being encoded in which side arrived first). Discusses the general port-based attack in this setting.
-
Geometry of Banach spaces: A new route towards position based cryptography (2021) doi.org
Provides a new protocol based on applying a phase unitary depending on the classical input information. Shows an exponential lower bound under a regularity assumption on the attack, and an exponential lower bound conditioned on an, as yet, unresolved Banach space geometry…
-
Quantum tasks in holography (2019) doi.org
Connects QPV to the AdS/CFT conjecture by noting that a QPV protocol in the bulk must have an equivalent protocol in the boundary. The boundary implementation turns out to be a valid attack on the bulk QPV protocol, implementing it non-locally.
-
Security of position-based quantum cryptography limits Hamiltonian simulation via holography (2024) doi.org
Connects QPV to Hamiltonian simulation. Shows that if a superlinear lower bound can be shown for QPV attacks, then there are new fundamental lower bounds for resources required for one Hamiltonian to simulate another.
-
Quantum position verification in the random oracle model (2014) doi.org
Considers QPV in higher dimensions carefully and shows unconditional security in the random oracle model.
-
Quantum Secure Key Exchange with Position-based Credentials (2025) arxiv.org
Improved analysis of how to use QPV to provide the authentication within QKD.
-
A complexity theory for non-local quantum computation (2025) arxiv.org
Finds relations between a wide range of different NLQC tasks, including showing that $f$-routing and $f$-BB84 are equivalent, with a constant-overhead reduction between them.
-
Continuous-variable quantum position verification secure against entangled attackers (2024) arxiv.org
Generalises $f$-BB84 QPV to continuous-variable inputs and shows analogous security statements as for finite-dimensional inputs.
-
Linear gate bounds against natural functions for position-verification (2024) arxiv.org
Provides a robust linear lower bound on the number of quantum gates/measurements needed to attack the inner product function.
-
Rank lower bounds on non-local quantum computation (2024) arxiv.org
Provides a lower bound in terms of the Schmidt-rank of the resource state for perfect attacks. Gives linear lower bounds for some concrete functions.
-
Introduces an extra commitment step into QPV and shows that for a class of protocols, involving $f$-BB84 QPV, this makes the transmission loss irrelevant for security. Argues $f$-BB84 is a practical QPV protocol.
-
On the role of quantum communication and loss in attacks on quantum position verification (2022) arxiv.org
Shows that any QPV protocol that can be broken unentangled with quantum communication, but is secure against classical communication attacks, can be transformed into one that is secure against quantum communication attacks. Also notes that if the signal loss is high enough any…
-
Towards practical quantum position verification (2023) arxiv.org
Delves into some technical hardware details of a practical QPV implementation.
-
Security of a continuous-variable based quantum position verification protocol (2023) arxiv.org
Generalises the protocol to continuous variable inputs and shows security against unentangled attacks depending on loss and noise rates.
-
Holography as a resource for non-local quantum computation (2022) arxiv.org
Discusses and fills a loophole in the paper one above. Costructs an attacked based on simulating a holographic CFT and argues that, based on some assumptions, any polynomially complex unitary can be efficiently attacked.
-
On the role of quantum communication and loss in attacks on quantum position verification (2022) arxiv.org
Proves a 3/4 upper bound on the success probability of unentangled attacks.
-
Non-local computation of quantum circuits with small light cones (2022) arxiv.org
Provides a general attack on QPV based on the geometric structure of a circuit decomposition of the task unitary. Is more efficient for certain classes of unitaries than previous general attacks.
-
Towards practical and error-robust quantum position verification (2021) arxiv.org
Defines a new protocol based on the SWAP test and studies it theoretically and practically.
-
Breaking simple quantum position verification protocols with little entanglement (2020) arxiv.org
Considers the case when the input bases are related by different angles and shows dimension-dependent attacks depending on the angle. Notably, they show the angle $\pi/6$ (outside the Clifford hierarchy) can be attacked with a 6-dimensional resource state.
-
Constraining the doability of relativistic quantum tasks (2019) arxiv.org
Generalises the port-based attack to more general quantum tasks and spacetime circuits. Finds that the coarse causal structure of the task is the relevant property determining whether the task is doable non-locally.
-
A tight lower bound for the BB84-states quantum-position-verification protocol (2015) arxiv.org
Gives essentially tight lower bound for attacks with classical communication.
-
Zhou. A Theorist's Toolkit. Illinois yuanz.web.illinois.edu
It covers a large number of the math/CS topics that you need to know for reading and doing research in Computer Science Theory.
-
TCS+ youtube.com
A series of online seminars in theoretical computer science. The goal is to make engaging talks accessible to the widest possible audience.
-
O'Donnell. Great Ideas in Theoretical Computer Science. CMU youtube.com
A series of lectures on selected notable topics in theoretical computer science.
-
O'Donnell. CS Theory Toolkit youtube.com
It covers a large number of the math/CS topics that you need to know for reading and doing research in Computer Science Theory - alternatively: bilibili
-
Uni Paderborn. Quantum Complexity Theory. Winter 2020 youtube.com
CS Masters level lectures on topics including Boson sampling, quantum interactive proofs, and quantum merlin arthur.
-
Anil Ada. Great Ideas in Theoretical Computer Science. CMU youtube.com
A series of lectures on selected notable topics in theoretical computer science.
-
Yanofsky. Theoretical Computer Science youtube.com
undergrad introduction to theory of computation
-
CMU Theory youtube.com
Aims for a mathematical understanding of fundamental issues in Computer Science, and to use this understanding to produce better algorithms, protocols, and systems, as well as identify the inherent limitations of efficient computation.
-
Karp. A Personal View of Computer Science at Berkeley www2.eecs.berkeley.edu
Karp addresses: In 1968 computer science at Berkeley was problematic, with two departments working independently to develop programs, and his personal reflections.
-
Barak. Advice for The Budding Theorist windowsontheory.org
Tips for anyone interested in theoretical computer science.
-
Alon & Spencer. The Probabilistic Method wiley.com
A standard reference for researchers in probabilistic methods in combinatorics. Shows also connections to theoretical computer science.
-
Knuth. Things a Computer Scientist Rarely Talks About web.stanford.edu
A general illustration of relations between faith and science.
-
Intro to Theoretical Computer Science udacity.com
It teaches basic concepts in theoretical computer science, such as NP-completeness, and what they imply for solving tough algorithmic problems.
-
Tim Roughgarden. Foundations of Blockchains timroughgarden.github.io
The science and technology of blockchain protocols and the applications built on top of them, with an emphasis on fundamental principles rather than specific protocols. - See also Lecture Videos.
-
-
Barak. Surveys For Students thmatters.wordpress.com
Surveys for high-school, undergraduate, and even researchers.
-
Omer Reingold. TOC: a Personal Perspective (2021) theorydish.blog
In celebration of 25 years for “TOC: a Scientific Perspective (1996),” by Oded Goldreich and Avi Wigderson. It spots the light on a criticism directed to TCS, that it is not as deep as Math and not as useful as CS.
-
6.893 Philosophy and Theoretical Computer Science. MIT stellar.mit.edu
It examines the relevance of modern theoretical computer science to traditional questions in philosophy, and conversely, what philosophy can contribute to theoretical computer science.
- next page of items loading…
