Cloning Games, Black Holes and Cryptography

• URL: http://arxiv.org/abs/2411.04730v2
• Date: Fri, 04 Apr 2025 16:48:23 GMT
• Title: Cloning Games, Black Holes and Cryptography
• Authors: Alexander Poremba, Seyoon Ragavan, Vinod Vaikuntanathan,
• Abstract summary: We introduce a new toolkit for analyzing cloning games.<n>These games capture more quantitative versions of no-cloning and are central to unclonable cryptography.
• Score: 53.93687166730726
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum no-cloning is one of the most fundamental properties of quantum information. In this work, we introduce a new toolkit for analyzing cloning games; these games capture more quantitative versions of no-cloning and are central to unclonable cryptography. Previous works rely on the framework laid out by Tomamichel, Fehr, Kaniewski and Wehner to analyze both the $n$-qubit BB84 game and the subspace coset game. Their constructions and analysis face the following inherent limitations: - The existing bounds on the values of these games are at least $2^{-0.25n}$; on the other hand, the trivial adversarial strategy wins with probability $2^{-n}$. Not only that, the BB84 game does in fact admit a highly nontrivial winning strategy. This raises the natural question: are there cloning games which admit no non-trivial winning strategies? - The existing constructions are not multi-copy secure; the BB84 game is not even $2 \mapsto 3$ secure, and the subspace coset game is not $t \mapsto t+1$ secure for a polynomially large $t$. Moreover, we provide evidence that the existing technical tools do not suffice to prove multi-copy security of even completely different constructions. This raises the natural question: can we design new cloning games that achieve multi-copy security, possibly by developing a new analytic toolkit? We study a new cloning game based on binary phase states and show that it is $t$-copy secure when $t=o(n/\log n)$. Moreover, for constant $t$, we obtain the first asymptotically optimal bounds of $O(2^{-n})$. We also show a worst-case to average-case reduction for a large class of cloning games, which allows us to show the same quantitative results for Haar cloning games. These technical ingredients together enable two new applications which have previously been out of reach; one in black hole physics, and one in unclonable cryptography.

Related papers

• Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback [60.610120215789976]
  We show that when a pure strategy Nash equilibrium exists, $c$ becomes zero, leading to an optimal instance-dependent regret bound. Our algorithm also enjoys last-iterate convergence and can identify the pure strategy Nash equilibrium with near-optimal sample.
  arXiv  Detail & Related papers  (2025-02-24T20:20:06Z)
• Best of Both Worlds: Regret Minimization versus Minimax Play [57.68976579579758]
  We show that our results allow us to guarantee to risk at most $O(1)$ loss while being able to gain $Omega(T)$ from exploitable opponents.
  arXiv  Detail & Related papers  (2025-02-17T11:04:01Z)
• The Aldous--Lyons Conjecture II: Undecidability [3.8370118222043694]
  We show that given a tailored non-local game $G$, it is undecidable to distinguish between the case where $G$ has a special kind of perfect strategy, and the case where every strategy for $G$ is far from being perfect. Using a reduction introduced in the companion paper [BCLV24], this undecidability result implies a negative answer to the Aldous--Lyons conjecture.
  arXiv  Detail & Related papers  (2024-12-30T22:59:56Z)
• Revocable Encryption, Programs, and More: The Case of Multi-Copy Security [48.53070281993869]
  We show the feasibility of revocable primitives, such as revocable encryption and revocable programs. This suggests that the stronger notion of multi-copy security is within reach in unclonable cryptography.
  arXiv  Detail & Related papers  (2024-10-17T02:37:40Z)
• A bound on the quantum value of all compiled nonlocal games [49.32403970784162]
  A cryptographic compiler converts any nonlocal game into an interactive protocol with a single computationally bounded prover. We establish a quantum soundness result for all compiled two-player nonlocal games.
  arXiv  Detail & Related papers  (2024-08-13T08:11:56Z)
• Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
  Self-play via online learning is one of the premier ways to solve large-scale two-player zero-sum games. We show that OMWU offers several advantages including logarithmic dependence on the size of the payoff matrix. We prove that a broad class of algorithms that do not forget the past quickly all suffer the same issue.
  arXiv  Detail & Related papers  (2024-06-15T13:26:17Z)
• Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography [5.360892674012226]
  We present a new approach to unclonable encryption via a reduction to a novel question about nonlocal quantum state discrimination. Our main technical result is showing that the players cannot distinguish between each player receiving independently-chosen Haar random states versus all players receiving the same Haar random state. We also show other implications to single-decryptor encryption and leakage-resilient secret sharing.
  arXiv  Detail & Related papers  (2024-05-16T17:30:55Z)
• Photonic implementation of the quantum Morra game [69.65384453064829]
  We study a faithful translation of a two-player quantum Morra game, which builds on previous work by including the classical game as a special case. We propose a natural deformation of the game in the quantum regime in which Alice has a winning advantage, breaking the balance of the classical game. We discuss potential applications of the quantum Morra game to the study of quantum information and communication.
  arXiv  Detail & Related papers  (2023-11-14T19:41:50Z)
• Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learning [105.7510838453122]
  We examine online safe multi-agent reinforcement learning using constrained Markov games. We develop an upper confidence reinforcement learning algorithm to solve this Lagrangian problem. Our algorithm updates the minimax decision primal variables via online mirror descent and the dual variable via projected gradient step.
  arXiv  Detail & Related papers  (2023-05-31T22:09:24Z)
• Revocable Cryptography from Learning with Errors [61.470151825577034]
  We build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities. We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.
  arXiv  Detail & Related papers  (2023-02-28T18:58:11Z)
• Photon-phonon quantum cloning in optomechanical system [5.317893030884531]
  cloning of flying bits for further processing from the solid-state quantum bits in storage is an operation frequently used in quantum information processing. We propose a high-fidelity and controllable quantum cloning scheme between solid bits and flying bits.
  arXiv  Detail & Related papers  (2023-02-11T10:09:53Z)
• Cloning Games: A General Framework for Unclonable Primitives [8.140799273465545]
  cloning games captures fundamental unclonable primitives such as quantum money, copy-protection, unclonable encryption, single-decryptor encryption, and many more. We construct unclonable encryption in the quantum random oracle model based on BB84 states, improving upon the previous work, which used coset states. We establish a relationship between different challenge distributions of copy-protection schemes and single-decryptor encryption schemes.
  arXiv  Detail & Related papers  (2023-02-03T17:24:38Z)
• Nonlocal games with noisy maximally entangled states are decidable [5.076419064097734]
  This paper considers a special class of nonlocal games $(G,psi)$, where $G$ is a two-player one-round game. In the game $(G,psi)$, the players are allowed to share arbitrarily many copies of $psi$. It is feasible to approximately compute $omega*(G,psi)$ to an arbitrarily precision.
  arXiv  Detail & Related papers  (2021-08-20T12:25:55Z)
• Practical parallel self-testing of Bell states via magic rectangles [0.0]
  Self-testing is a method to verify that one has a particular quantum state from purely classical statistics. We use the $3 times n$ magic rectangle games to obtain a self-test for $n$ Bell states where the one side needs only to measure single-qubit Pauli observables.
  arXiv  Detail & Related papers  (2021-05-09T23:07:18Z)
• Unclonable Encryption, Revisited [7.129830575525267]
  Unclonable encryption, introduced by Broadbent and Lord (TQC'20), is an encryption scheme with the following attractive feature. We construct unclonable encryption schemes with semantic security. We show that unclonable encryption implies copy-protection for a simple class of unlearnable functions.
  arXiv  Detail & Related papers  (2021-03-27T22:37:59Z)
• Limitations on Uncloneable Encryption and Simultaneous One-Way-to-Hiding [17.660958043781154]
  We study uncloneable quantum encryption schemes for classical messages. We focus on the information-theoretic setting and give several limitations on the structure and security of these schemes.
  arXiv  Detail & Related papers  (2021-03-26T15:12:10Z)
• 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)

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.