Generic Number-of-Copies Amplification for Pseudorandom States

• URL: http://arxiv.org/abs/2606.29325v1
• Date: Sun, 28 Jun 2026 10:36:34 GMT
• Title: Generic Number-of-Copies Amplification for Pseudorandom States
• Abstract summary: We show that any quantum pseudorandom state that is secure against single-copy distinguishers, i.e. a $1$-PRS, can be amplified to $t$-copy security.<n>We show that by carefully accounting for the randomness that is used in the construction, and using quantum extractors, it is possible to eliminate an ancilla register of any length and obtain a meaningful $t$-PRS outcome.
• Score: 3.5551093158690037
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show that any quantum pseudorandom state that is secure against single-copy distinguishers, i.e. a $1$-PRS, can be amplified to $t$-copy security, i.e. to a $t$-PRS, without additional assumptions, for any polynomial $t$ in the security parameter. Prior work (Ananth and Goldin, arXiv 2025) was only able to show this for a restricted class of $1$-PRS constructions, namely ones whose generators only use a small number of ancilla qubits. Technically, we show that by carefully accounting for the randomness that is used in the construction, and using quantum extractors, it is possible to eliminate an ancilla register of any length and obtain a meaningful $t$-PRS outcome.

Related papers

• On the Limits of Stretching Quantum Pseudorandomness [7.528006499174231]
  Pseudorandom states are quantum analogues of classical pseudorandom generators.<n>We prove the first black-box separation between single-copy secure pseudorandom states with different output lengths.
  arXiv  Detail & Related papers  (2026-06-23T16:00:17Z)
• LoRA and Privacy: When Random Projections Help (and When They Don't) [55.65932772290123]
  We introduce the (Wishart) projection mechanism, a randomized map of the form $S mapsto M f(S)$ with $M sim W_d (1/r I_d, r)$ and study its differential privacy properties.<n>For vector-valued queries $f$, we prove non-asymptotic DP guarantees without any additive noise, showing that Wishart randomness alone can suffice.<n>For matrix-valued queries, however, we establish a sharp negative result: in the noise-free setting, the mechanism is not DP, and we demonstrate its vulnerability.
  arXiv  Detail & Related papers  (2026-01-29T13:43:37Z)
• Less is More: On Copy Complexity in Quantum Cryptography [6.034518754132198]
  Making definitional changes to the number of copies accessible to an adversary can drastically affect various aspects.<n>We present a generic approach to boost single-copy security to multi-copy security and apply this approach to many settings.
  arXiv  Detail & Related papers  (2025-10-06T16:28:23Z)
• Cloning Games, Black Holes and Cryptography [50.022147589030304]
  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.
  arXiv  Detail & Related papers  (2024-11-07T14:09:32Z)
• Rényi divergence-based uniformity guarantees for $k$-universal hash functions [53.80737717363129]
  Universal hash functions map the output of a source to random strings over a finite alphabet.<n>We show that it is possible to distill random bits that are nearly uniform, as measured by min-entropy.
  arXiv  Detail & Related papers  (2024-10-21T19:37:35Z)
• Pseudorandom and Pseudoentangled States from Subset States [49.74460522523316]
  A subset state with respect to $S$, a subset of the computational basis, is [ frac1sqrt|S|sum_iin S |irangle. We show that for any fixed subset size $|S|=s$ such that $s = 2n/omega(mathrmpoly(n))$ and $s=omega(mathrmpoly(n))$, a random subset state is information-theoretically indistinguishable from a Haar random state even provided
  arXiv  Detail & Related papers  (2023-12-23T15:52:46Z)
• Pseudorandom Isometries [6.0709446838151715]
  We introduce a new notion called $cal Q$-secure pseudorandom isometries (PRI) PRIs are efficient quantum circuits that map an $n$-qubit state to an $(n+m)$-qubit state. We demonstrate many cryptographic applications of PRIs, including, length extension theorems for quantum pseudorandomness notions.
  arXiv  Detail & Related papers  (2023-11-06T06:27:14Z)
• Signatures From Pseudorandom States via $\bot$-PRFs [0.11650821883155184]
  We introduce new definitions for $bot$-PRG and $bot$-PRF. Our main application is a (quantum) digital signature scheme with classical public keys and signatures.
  arXiv  Detail & Related papers  (2023-11-01T20:54:50Z)
• A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points [50.90125395570797]
  This nearly establishes a conjecture ofciteSaundersonCPW12, within logarithmic factors. The latter conjecture has attracted significant attention over the past decade, due to its connections to machine learning and sum-of-squares lower bounds for certain statistical problems.
  arXiv  Detail & Related papers  (2022-12-21T17:48:01Z)
• 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)
• Scalable Pseudorandom Quantum States [14.048989759890476]
  In existing constructions of PRS generators, security scales with the number of qubits in the states, i.e. the (statistical) security parameter for an $n$-qubit PRS is roughly $n$. We show that any quantum-secure one-way function implies scalable PRS. We follow the paradigm of first showing a emphstatistically secure construction when given oracle access to a random function, and then replacing the random function with a quantum-secure (classical) pseudorandom function to achieve computational security.
  arXiv  Detail & Related papers  (2020-04-04T17:15:03Z)

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.