Code-routing: a new attack on position verification

• URL: http://arxiv.org/abs/2202.07812v5
• Date: Fri, 28 Jul 2023 19:00:23 GMT
• Title: Code-routing: a new attack on position verification
• Authors: Joy Cree, Alex May
• Abstract summary: A popular verification scheme known as $f$-routing involves requiring the prover to redirect a quantum system. We give a new cheating strategy in which the quantum system is encoded into a secret-sharing scheme. This strategy completes the $f$-routing task using $O(SP_p(f))$ EPR pairs.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The cryptographic task of position verification attempts to verify one party's location in spacetime by exploiting constraints on quantum information and relativistic causality. A popular verification scheme known as $f$-routing involves requiring the prover to redirect a quantum system based on the value of a Boolean function $f$. Cheating strategies for the $f$-routing scheme require the prover use pre-shared entanglement, and security of the scheme rests on assumptions about how much entanglement a prover can manipulate. Here, we give a new cheating strategy in which the quantum system is encoded into a secret-sharing scheme, and the authorization structure of the secret-sharing scheme is exploited to direct the system appropriately. This strategy completes the $f$-routing task using $O(SP_p(f))$ EPR pairs, where $SP_p(f)$ is the minimal size of a span program over the field $\mathbb{Z}_p$ computing $f$. This shows we can efficiently attack $f$-routing schemes whenever $f$ is in the complexity class $\text{Mod}_p\text{L}$, after allowing for local pre-processing. The best earlier construction achieved the class L, which is believed to be strictly inside of $\text{Mod}_p\text{L}$. We also show that the size of a quantum secret sharing scheme with indicator function $f_I$ upper bounds entanglement cost of $f$-routing on the function $f_I$.

Related papers

• Linear gate bounds against natural functions for position-verification [0.0]
  A quantum position-verification scheme attempts to verify the spatial location of a prover. We consider two well-studied position-verification schemes known as $f$-routing and $f$-BB84.
  arXiv  Detail & Related papers  (2024-02-28T19:00:10Z)
• Rank lower bounds on non-local quantum computation [0.0]
  A non-local quantum computation (NLQC) replaces an interaction between two quantum systems with a single round of communication and shared entanglement. We study two classes of NLQC, $f$-routing and $f$-BB84, which are of relevance to classical information theoretic cryptography and quantum position-verification.
  arXiv  Detail & Related papers  (2024-02-28T19:00:09Z)
• A Construction of Evolving $k$-threshold Secret Sharing Scheme over A Polynomial Ring [55.17220687298207]
  The threshold secret sharing scheme allows the dealer to distribute the share to every participant that the secret is correctly recovered from a certain amount of shares. We propose a brand-new construction of evolving $k$-threshold secret sharing scheme for an $ell$-bit secret over a ring, with correctness and perfect security.
  arXiv  Detail & Related papers  (2024-02-02T05:04:01Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum Security of iMHFs [6.305950347749109]
  We introduce a new parallel reversible pebbling game which captures additional restrictions imposed by the No-Deletion Theorem in Quantum Computing. We apply our new reversible pebbling game to analyze the reversible space-time complexity of several important graphs.
  arXiv  Detail & Related papers  (2021-10-08T15:24:31Z)
• The Power of Subsampling in Submodular Maximization [51.629656762796564]
  We show that this approach leads to optimal/state-of-the-art results despite being much simpler than existing methods. We empirically demonstrate the effectiveness of our algorithms on video summarization, location summarization, and movie recommendation tasks.
  arXiv  Detail & Related papers  (2021-04-06T20:25:57Z)
• An Efficient Simulation of Quantum Secret Sharing [7.195824023358536]
  We propose a secure $d$-level $QSS$ protocol for sharing a secret with efficient simulation. It does not disclose any information about the secret to players. Its security analysis shows that the intercept-resend, intercept, entangle-measure, forgery, collision and collusion attacks are not possible in this protocol.
  arXiv  Detail & Related papers  (2021-03-20T16:42:02Z)
• Nearly Minimax Optimal Reward-free Reinforcement Learning [88.75843804630772]
  We study the reward-free reinforcement learning framework, which is particularly suitable for batch reinforcement learning and scenarios where one needs policies for multiple reward functions. We give a new efficient algorithm, textbfStaged textbfSampling + textbfTruncated textbfPlanning (algoname), which interacts with the environment at most $Oleft( fracS2Aepsilon2textpolylogleft(fracSAHepsilon2
  arXiv  Detail & Related papers  (2020-10-12T17:51:19Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs" We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM) As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
  arXiv  Detail & Related papers  (2020-09-29T08:41:53Z)
• On the Modularity of Hypernetworks [103.1147622394852]
  We show that for a structured target function, the overall number of trainable parameters in a hypernetwork is smaller by orders of magnitude than the number of trainable parameters of a standard neural network and an embedding method.
  arXiv  Detail & Related papers  (2020-02-23T22:51:52Z)

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.