Geometry of Banach spaces: a new route towards Position Based Cryptography

• URL: http://arxiv.org/abs/2103.16357v3
• Date: Fri, 15 Apr 2022 18:13:06 GMT
• Title: Geometry of Banach spaces: a new route towards Position Based Cryptography
• Authors: Marius Junge, Aleksander M. Kubicki, Carlos Palazuelos and David P\'erez-Garc\'ia
• Abstract summary: We study Position Based Quantum Cryptography (PBQC) from the perspective of geometric functional analysis and its connections with quantum games. The main question we are interested in asks for the optimal amount of entanglement that a coalition of attackers have to share in order to compromise the security of any PBQC protocol. We show that the understanding of the type properties of some more involved Banach spaces would allow to drop out the assumptions and lead to unconditional lower bounds on the resources used to attack our protocol.
• Score: 65.51757376525798
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work we initiate the study of Position Based Quantum Cryptography (PBQC) from the perspective of geometric functional analysis and its connections with quantum games. The main question we are interested in asks for the optimal amount of entanglement that a coalition of attackers have to share in order to compromise the security of any PBQC protocol. Known upper bounds for that quantity are exponential in the size of the quantum systems manipulated in the honest implementation of the protocol. However, known lower bounds are only linear. In order to deepen the understanding of this question, here we propose a Position Verification (PV) protocol and find lower bounds on the resources needed to break it. The main idea behind the proof of these bounds is the understanding of cheating strategies as vector valued assignments on the Boolean hypercube. Then, the bounds follow from the understanding of some geometric properties of particular Banach spaces, their type constants. Under some regularity assumptions on the former assignment, these bounds lead to exponential lower bounds on the quantum resources employed, clarifying the question in this restricted case. Known attacks indeed satisfy the assumption we make, although we do not know how universal this feature is. Furthermore, we show that the understanding of the type properties of some more involved Banach spaces would allow to drop out the assumptions and lead to unconditional lower bounds on the resources used to attack our protocol. Unfortunately, we were not able to estimate the relevant type constant. Despite that, we conjecture an upper bound for this quantity and show some evidence supporting it. A positive solution of the conjecture would lead to stronger security guarantees for the proposed PV protocol providing a better understanding of the question asked above.

Related papers

• Classical Commitments to Quantum States [5.6739502570965765]
  We define the notion of a classical commitment scheme to quantum states. It allows a quantum prover to compute a classical commitment to a quantum state, and later open each qubit of the state in either the standard or the Hadamard basis.
  arXiv  Detail & Related papers  (2024-04-19T22:31:18Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Entropy Accumulation under Post-Quantum Cryptographic Assumptions [4.416484585765028]
  In device-independent (DI) quantum protocols, the security statements are oblivious to the characterization of the quantum apparatus. We present a flexible framework for proving the security of such protocols by utilizing a combination of tools from quantum information theory.
  arXiv  Detail & Related papers  (2023-07-02T12:52:54Z)
• Single-qubit loss-tolerant quantum position verification protocol secure against entangled attackers [0.0]
  We study the exact loss-tolerance of the most popular protocol for QPV, which is based on BB84 states. We show how these results transfer to the variant protocol which combines $n$ bits of classical information with a single qubit.
  arXiv  Detail & Related papers  (2022-12-07T14:39:56Z)
• Commitments to Quantum States [11.217084610985674]
  A commitment to quantum messages is binding if, after the commit phase, the committed state is hidden from the sender's view. We show that hiding quantum state commitments (QSCs) are implied by any commitment scheme for classical messages. Commitments to quantum states open the door to many new cryptographic possibilities.
  arXiv  Detail & Related papers  (2022-10-11T04:34:36Z)
• Is Vertical Logistic Regression Privacy-Preserving? A Comprehensive Privacy Analysis and Beyond [57.10914865054868]
  We consider vertical logistic regression (VLR) trained with mini-batch descent gradient. We provide a comprehensive and rigorous privacy analysis of VLR in a class of open-source Federated Learning frameworks.
  arXiv  Detail & Related papers  (2022-07-19T05:47:30Z)
• Succinct Classical Verification of Quantum Computation [30.91621630752802]
  We construct a classically succinct interactive argument for quantum computation (BQP) Our protocol is secure assuming the post-quantum security of indistinguishability obfuscation (iO) and Learning Errors (LWE)
  arXiv  Detail & Related papers  (2022-06-29T22:19:12Z)
• Tight Exponential Analysis for Smoothing the Max-Relative Entropy and for Quantum Privacy Amplification [56.61325554836984]
  The max-relative entropy together with its smoothed version is a basic tool in quantum information theory. We derive the exact exponent for the decay of the small modification of the quantum state in smoothing the max-relative entropy based on purified distance.
  arXiv  Detail & Related papers  (2021-11-01T16:35:41Z)
• Shannon theory for quantum systems and beyond: information compression for fermions [68.8204255655161]
  We show that entanglement fidelity in the fermionic case is capable of evaluating the preservation of correlations. We introduce a fermionic version of the source coding theorem showing that, as in the quantum case, the von Neumann entropy is the minimal rate for which a fermionic compression scheme exists.
  arXiv  Detail & Related papers  (2021-06-09T10:19:18Z)
• Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's Post-Quantum Security [67.06003361150228]
  A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task. In this work, we examine the hardness of finding such chain of PoWs against quantum strategies. We prove that the chain of PoWs problem reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity.
  arXiv  Detail & Related papers  (2020-12-30T18:03:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.