Cloning Games, Black Holes and Cryptography

• URL: http://arxiv.org/abs/2411.04730v3
• Date: Thu, 11 Sep 2025 21:28:57 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>This framework allows us to analyze a new cloning game based on binary phase states.<n>We show that the binary phase variantally optimal bound offers quantitative insights into information scrambling in idealized models of black holes.
• Score: 50.022147589030304
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we introduce a new toolkit for analyzing cloning games, a notion that captures stronger and more quantitative versions of the celebrated quantum no-cloning theorem. This framework allows us to analyze a new cloning game based on binary phase states. Our results provide evidence that these games may be able to overcome important limitations of previous candidates based on BB84 states and subspace coset states: in a model where the adversaries are restricted to making a single oracle query, we show that the binary phase variant is $t$-copy secure when $t=o(n/\log n)$. Moreover, for constant $t$, we obtain the first optimal bounds of $O(2^{-n})$, asymptotically matching the value attained by a trivial adversarial strategy. We also show a worst-case to average-case reduction which allows us to show the same quantitative results for the new and natural notion of Haar cloning games. Our analytic toolkit, which we believe will find further applications, is based on binary subtypes and uses novel bounds on the operator norms of block-wise tensor products of matrices. To illustrate the effectiveness of these new techniques, we present two applications: first, in black-hole physics, where our asymptotically optimal bound offers quantitative insights into information scrambling in idealized models of black holes; and second, in unclonable cryptography, where we (a) construct succinct unclonable encryption schemes from the existence of pseudorandom unitaries, and (b) propose and provide evidence for the security of multi-copy unclonable encryption schemes.

Related papers

• Pseudo-Equilibria, or: How to Stop Worrying About Crypto and Just Analyze the Game [48.93355782581436]
  We consider the problem of a game theorist analyzing a game that uses cryptographic protocols.<n>We propose a new solution concept: the pseudo-Nash equilibrium.
  arXiv  Detail & Related papers  (2025-06-27T10:21:28Z)
• 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)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  Sponge hashing is a widely used class of cryptographic hash algorithms.<n>Intrepid permutations have so far remained a fundamental open problem.<n>We show that finding zero-pairs in a random $2n$-bit permutation requires at least $Omega (2n/2)$ many queries.
  arXiv  Detail & Related papers  (2024-03-07T18:46:58Z)
• A Modular Approach to Unclonable Cryptography [4.336971448707467]
  We propose unclonable puncturable obfuscation (UPO) and study its implications for unclonable cryptography. We present modular (and arguably, simple) constructions of many primitives in unclonable cryptography. We show that any cryptographic functionality can be copy-protected as long as this functionality satisfies a notion of security.
  arXiv  Detail & Related papers  (2023-11-20T16:22:52Z)
• 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)
• Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
  We show that targetcollapsing enables publiclyverifiable deletion (PVD) We build on this framework to obtain a variety of primitives supporting publiclyverifiable deletion from weak cryptographic assumptions.
  arXiv  Detail & Related papers  (2023-03-15T15:00:20Z)
• 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)
• Quantum Proofs of Deletion for Learning with Errors [91.3755431537592]
  We construct the first fully homomorphic encryption scheme with certified deletion. Our main technical ingredient is an interactive protocol by which a quantum prover can convince a classical verifier that a sample from the Learning with Errors distribution in the form of a quantum state was deleted.
  arXiv  Detail & Related papers  (2022-03-03T10:07:32Z)
• 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)
• Hidden Cosets and Applications to Unclonable Cryptography [15.248351992500078]
  We study a generalization of hidden subspace states to hidden coset states (first introduced by Aaronson and Christiano [STOC '12]). We explore unclonable properties of coset states and several applications.
  arXiv  Detail & Related papers  (2021-07-12T19:04:01Z)
• 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)
• Targeted Attack against Deep Neural Networks via Flipping Limited Weight Bits [55.740716446995805]
  We study a novel attack paradigm, which modifies model parameters in the deployment stage for malicious purposes. Our goal is to misclassify a specific sample into a target class without any sample modification. By utilizing the latest technique in integer programming, we equivalently reformulate this BIP problem as a continuous optimization problem.
  arXiv  Detail & Related papers  (2021-02-21T03:13:27Z)
• 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.