pith. sign in

arxiv: 2606.29325 · v1 · pith:U2ZH2ACNnew · submitted 2026-06-28 · 🪐 quant-ph · cs.CR

Generic Number-of-Copies Amplification for Pseudorandom States

Zvika Brakerski , Miri Zenilman This is my paper

Pith reviewed 2026-06-30 07:23 UTC · model grok-4.3

classification 🪐 quant-ph cs.CR
keywords quantum pseudorandom statesPRS amplification1-PRS to t-PRSquantum extractorsancilla eliminationcopy securityquantum cryptography
0
0 comments X

The pith

Any quantum pseudorandom state secure against single-copy distinguishers can be amplified to security against any polynomial number of copies without extra assumptions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that a 1-PRS, secure only against single-copy attacks, can be turned into a t-PRS secure against polynomially many copies for any polynomial t. This holds for arbitrary constructions rather than only those using few ancilla qubits. The method works by tracking the randomness in the generator and applying quantum extractors to remove ancilla registers of any length while preserving the pseudorandomness guarantee. A reader would care because the result removes a technical barrier that previously forced specialized constructions in quantum pseudorandom state design.

Core claim

Any 1-PRS can be amplified to a t-PRS for polynomial t in the security parameter by carefully accounting for the randomness used in the construction and then applying quantum extractors to eliminate an ancilla register of arbitrary length, yielding a meaningful t-PRS outcome.

What carries the argument

Quantum extractors applied after randomness accounting, which remove arbitrary-length ancilla registers while preserving t-PRS security.

If this is right

  • Every existing 1-PRS generator immediately yields a t-PRS generator for any polynomial t.
  • Constructions no longer need to be restricted to small ancilla registers to achieve multi-copy security.
  • The amplification requires no additional cryptographic assumptions beyond the original 1-PRS security.
  • The same technique applies uniformly across all polynomial copy numbers rather than fixed t.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Designers of quantum pseudorandom states can now start from the simplest 1-PRS definitions and obtain multi-copy versions mechanically.
  • The result may reduce the number of separate security proofs needed when building protocols that rely on pseudorandom states under multiple copies.
  • Similar randomness-accounting plus extractor techniques could be tested on other quantum primitives whose security definitions involve copy numbers.

Load-bearing premise

Quantum extractors succeed in producing a valid t-PRS even after removing ancilla registers of arbitrary length once randomness has been accounted for.

What would settle it

A concrete 1-PRS construction where applying the randomness-accounting step followed by a quantum extractor fails to yield a t-PRS secure against t-copy distinguishers.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript claims to prove a generic amplification result: any quantum pseudorandom state secure against single-copy distinguishers (a 1-PRS) can be converted into one secure against t-copy distinguishers (a t-PRS) for any polynomial t, without additional assumptions on the original generator. The technique relies on carefully accounting for the randomness used in the construction and then applying quantum extractors to remove an ancilla register of arbitrary length, thereby overcoming the small-ancilla restriction present in prior work (Ananth and Goldin).

Significance. If the central claim holds, the result would be significant for the foundations of quantum pseudorandomness. It supplies a generic, assumption-free amplification procedure that applies to arbitrary 1-PRS constructions, thereby strengthening the security of PRS-based primitives and clarifying the relationship between single-copy and multi-copy security notions.

major comments (2)
  1. [Abstract] Abstract and the technical overview: the claim that quantum extractors can eliminate an ancilla register of arbitrary length after randomness accounting is load-bearing for the generic result. Standard quantum extractor constructions require the source min-entropy to exceed the output length plus the seed length by a sufficient margin; it is not shown that the randomness-accounting step guarantees this margin independently of ancilla size (which may be superpolynomial).
  2. [Technical overview / main theorem] The reduction from t-PRS security to the extractor output: if the accounting step leaks any information about the original 1-PRS generator into the ancilla, the extractor may fail to produce a distribution that is indistinguishable from Haar-random even for polynomial t. A concrete bound relating the ancilla length, the extractor parameters, and the original 1-PRS distinguishing advantage is needed to close the argument.
minor comments (1)
  1. Notation for the randomness accounting step should be introduced with an explicit equation or diagram showing how the seed, the original generator output, and the ancilla are partitioned before the extractor is invoked.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and constructive feedback on the manuscript. We address the major comments point by point below.

read point-by-point responses

  1. Referee: [Abstract] Abstract and the technical overview: the claim that quantum extractors can eliminate an ancilla register of arbitrary length after randomness accounting is load-bearing for the generic result. Standard quantum extractor constructions require the source min-entropy to exceed the output length plus the seed length by a sufficient margin; it is not shown that the randomness-accounting step guarantees this margin independently of ancilla size (which may be superpolynomial).

    Authors: We agree that an explicit verification of the min-entropy margin is required for the claim to hold for arbitrary (including superpolynomial) ancilla length. In the revised manuscript we will insert a new lemma immediately after the randomness-accounting definition that proves the source min-entropy is at least output length + seed length + λ + ω(log ancilla length), where the extra logarithmic term is absorbed by standard extractor parameters; the proof relies only on the fact that accounting isolates the used random bits and that the original 1-PRS generator already produces a state whose conditional min-entropy is high enough to satisfy the PRS security definition. revision: yes

  2. Referee: [Technical overview / main theorem] The reduction from t-PRS security to the extractor output: if the accounting step leaks any information about the original 1-PRS generator into the ancilla, the extractor may fail to produce a distribution that is indistinguishable from Haar-random even for polynomial t. A concrete bound relating the ancilla length, the extractor parameters, and the original 1-PRS distinguishing advantage is needed to close the argument.

    Authors: We accept that a fully explicit reduction bound is needed. The revised proof of the main theorem will contain a new claim (Claim 3.4) that bounds the t-copy distinguishing advantage of the extractor output by Adv_1-PRS + 2^{-Ω(λ)} + ε_ext, where ε_ext is the extractor error; the bound is derived by a hybrid argument that treats the ancilla as part of the source and shows that any leakage from accounting is already captured by the original 1-PRS distinguisher. The dependence on ancilla length appears only inside the extractor error term and remains negligible for polynomial t when the extractor seed is chosen as O(log(ancilla) + λ). revision: yes

Circularity Check

0 steps flagged

No significant circularity in generic PRS amplification

full rationale

The paper's central claim relies on applying quantum extractors after randomness accounting to remove arbitrary-length ancilla registers while preserving t-PRS security. This technique is presented as building on external prior results about extractors (distinct authors) rather than any self-definitional reduction, fitted-parameter renaming, or load-bearing self-citation. No equations or steps in the provided abstract or description equate the output t-PRS security directly to the input 1-PRS by construction. The argument is self-contained against external benchmarks for extractor behavior.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, the central claim rests on the existence and applicability of quantum extractors with suitable parameters for arbitrary ancilla removal; no free parameters or invented entities are mentioned.

axioms (1)
  • domain assumption Quantum extractors exist that can eliminate an ancilla register of arbitrary length while preserving t-PRS security after randomness accounting
    Invoked in the technical step that removes the ancilla restriction present in prior work

pith-pipeline@v0.9.1-grok · 5657 in / 1185 out tokens · 30459 ms · 2026-06-30T07:23:52.925538+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 11 canonical work pages · 1 internal anchor

  1. [1]

    Pseudoran- dom (Function-Like) Quantum State Generators: New Definitions and Applications

    arXiv:2510.04992 [quant-ph].url:https://arxiv.org/abs/ 2510.04992. [AGQY22] Prabhanjan Ananth, Aditya Gulati, Luowen Qian, and Henry Yuen. “Pseudoran- dom (Function-Like) Quantum State Generators: New Definitions and Applications”. In:Theory of Cryptography. Ed. by Eike Kiltz and Vinod Vaikuntanathan. Cham: Springer Nature Switzerland, 2022, pp. 237–265.i...

    work page arXiv 2022

  2. [2]

    Oracle Separation Between Quan- tum Commitments and Quantum One-Wayness

    Ed. by Yevgeniy Dodis and Thomas Shrimpton. Cham: Springer Nature Switzerland, 2022, pp. 208– 236.isbn: 978-3-031-15802-5. [BCN25] John Bostanci, Boyang Chen, and Barak Nehoran. “Oracle Separation Between Quan- tum Commitments and Quantum One-Wayness”. In:Advances in Cryptology – EU- ROCRYPT

    2022

  3. [3]

    On the Computational Hardness Needed for Quantum Cryptography

    Ed. by Serge Fehr and Pierre-Alain Fouque. Cham: Springer Nature Switzerland, 2025, pp. 3–22.isbn: 978-3-031-91098-2. [BCQ23] Zvika Brakerski, Ran Canetti, and Luowen Qian. “On the Computational Hardness Needed for Quantum Cryptography”. In:14th Innovations in Theoretical Computer Science Conference, ITCS 2023, MIT, Cambridge, Massachusetts, USA, January 10- 13,

    2025

  4. [4]

    Quantum to Classical Randomness Extractors

    Ed. by Yael Tauman Kalai. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2023, 24:1–24:21.doi:10 . 4230 / LIPICS . ITCS . 2023 . 24.url:https : //doi.org/10.4230/LIPIcs.ITCS.2023.24. [BFW14] Mario Berta, Omar Fawzi, and Stephanie Wehner. “Quantum to Classical Randomness Extractors”. In:IEEE Trans. Inf. Theory60.2 (2014), pp. 1168–1192.doi:10...

    work page doi:10.4230/lipics.itcs.2023.24 2023

  5. [5]

    [PPTW25] Christophe Paul, Evangelos Protopapas, Dimitrios M

    IEEE, 2024, pp. 1178–1192.doi:10.1109/FOCS61266.2024.00077.url:https://doi.org/10. 1109/FOCS61266.2024.00077. [CCC+25] Bruno Cavalar, Boyang Chen, Andrea Coladangelo, Matthew Gray, Zihan Hu, Zhengfeng Ji, and Xingjian Li.A Meta-Complexity Characterization of Minimal Quantum Cryp- tography

    work page doi:10.1109/focs61266.2024.00077.url:https://doi.org/10 2024

  6. [6]

    In: Computer Vision - ECCV 2024 - 18th European Conference, Milan, Italy, September 29-October 4, 2024, Proceedings, Part I

    arXiv:2510 . 07859 [quant-ph].url:https : / / arxiv . org / abs / 2510.07859. [CCS25] Boyang Chen, Andrea Coladangelo, and Or Sattath. “The Power of a Single Haar Random State: Constructing and Separating Quantum Pseudorandomness”. In:Ad- vances in Cryptology – EUROCRYPT 2025: 44th Annual International Conference on the Theory and Applications of Cryptogr...

    work page doi:10.1007/978- 2025

  7. [7]

    1579–1588.isbn: 9781450399135.doi:10.1145/3564246.3585198.url:https: //doi.org/10.1145/3564246.3585198

    Orlando, FL, USA: Association for Computing Machinery, 2023, pp. 1579–1588.isbn: 9781450399135.doi:10.1145/3564246.3585198.url:https: //doi.org/10.1145/3564246.3585198. [Har13] Aram W. Harrow.The Church of the Symmetric Subspace

    work page doi:10.1145/3564246.3585198.url:https: 2023

  8. [8]

    The Church of the Symmetric Subspace

    arXiv:1308.6595 [quant-ph].url:https://arxiv.org/abs/1308.6595. [JLS18] Zhengfeng Ji, Yi-Kai Liu, and Fang Song. “Pseudorandom Quantum States”. In: Advances in Cryptology – CRYPTO

    work page internal anchor Pith review Pith/arXiv arXiv

  9. [9]

    Quantum Cryptography in Algorithmica

    Ed. by Hovav Shacham and Alexandra Boldyreva. Cham: Springer International Publishing, 2018, pp. 126–152.isbn: 978-3- 319-96878-0. [KQST23] William Kretschmer, Luowen Qian, Makrand Sinha, and Avishay Tal. “Quantum Cryptography in Algorithmica”. In:Proceedings of the 55th Annual ACM Symposium on Theory of Computing. STOC

    2018

  10. [10]

    Quantum Pseudorandomness and Classical Complexity

    Orlando, FL, USA: Association for Comput- ing Machinery, 2023, pp. 1589–1602.isbn: 9781450399135.doi:10.1145/3564246. 3585225.url:https://doi.org/10.1145/3564246.3585225. 24 [Kre21] William Kretschmer. “Quantum Pseudorandomness and Classical Complexity”. In: 16th Conference on the Theory of Quantum Computation, Communication and Cryp- tography, TQC 2021, ...

    work page doi:10.1145/3564246 2023

  11. [11]

    Commitments from Quantum One-Wayness

    Ed. by Min-Hsiu Hsieh. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2021, 2:1–2:20.doi:10. 4230/LIPICS.TQC.2021.2.url:https://doi.org/10.4230/LIPIcs.TQC.2021.2. [KT24] Dakshita Khurana and Kabir Tomer. “Commitments from Quantum One-Wayness”. In:Proceedings of the 56th Annual ACM Symposium on Theory of Computing. STOC

    work page doi:10.4230/lipics.tqc.2021.2 2021

  12. [12]

    A One-Query Lower Bound for Unitary Synthesis and Breaking Quantum Cryptography

    Vancouver, BC, Canada: Association for Computing Machinery, 2024, pp. 968– 978.doi:10.1145/3618260.3649654.url:https://doi.org/10.1145/3618260. 3649654. [LMW24] Alex Lombardi, Fermi Ma, and John Wright. “A One-Query Lower Bound for Unitary Synthesis and Breaking Quantum Cryptography”. In:Proceedings of the 56th Annual ACM Symposium on Theory of Computing. STOC

    work page doi:10.1145/3618260.3649654.url:https://doi.org/10.1145/3618260 2024

  13. [13]

    Quantum Commitments and Signatures Without One-Way Functions

    Vancouver, BC, Canada: Association for Computing Machinery, 2024, pp. 979–990.doi:10.1145/3618260. 3649650.url:https://doi.org/10.1145/3618260.3649650. [MY22] Tomoyuki Morimae and Takashi Yamakawa. “Quantum Commitments and Signatures Without One-Way Functions”. In:Advances in Cryptology – CRYPTO

    work page doi:10.1145/3618260 2024

  14. [14]

    One-Wayness in Quantum Cryptog- raphy

    Ed. by Yevgeniy Dodis and Thomas Shrimpton. Cham: Springer Nature Switzerland, 2022, pp. 269–295.isbn: 978-3-031-15802-5. [MY24] Tomoyuki Morimae and Takashi Yamakawa. “One-Wayness in Quantum Cryptog- raphy”. In:19th Conference on the Theory of Quantum Computation, Communi- cation and Cryptography, TQC 2024, Okinawa, Japan, September 9-13,

    2022

  15. [15]

    Decoupling with unitary approximate two-designs

    Ed. by Fr´ ed´ eric Magniez and Alex Bredariol Grilo. LIPIcs. Schloss Dagstuhl - Leibniz- Zentrum f¨ ur Informatik, 2024, 4:1–4:21.doi:10.4230/LIPICS.TQC.2024.4.url: https://doi.org/10.4230/LIPIcs.TQC.2024.4. [SDTR13] Oleg Szehr, Fr´ ed´ eric Dupuis, Marco Tomamichel, and Renato Renner. “Decoupling with unitary approximate two-designs”. In:New Journal of ...

    work page doi:10.4230/lipics.tqc.2024.4.url: 2024

  16. [16]

    by Reihaneh Safavi-Naini and Ran Canetti

    Ed. by Reihaneh Safavi-Naini and Ran Canetti. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 758–775. isbn: 978-3-642-32009-5. 25

    2012