Separating Pseudorandom Generators from Logarithmic Pseudorandom States

arXiv:2510.20131 · cs.CR · Submitted 2025-10-23 · Read on arXiv

cs.CR

Submitted: 2025-10-23

Updated: 2026-09-14

Comments: 25 pages

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Trace — 8× in this paper · explained in 2 episodes
• Trace Distance — 7× in this paper · explained in 3 episodes
• Common Haar Function-Like State — 3× in this paper
• Hilbert Space — 1× in this paper · explained in 2 episodes

Sources

• Pseudorandom Strings from Pseudorandom Quantum States
• Signatures From Pseudorandom States via $\bot$-PRFs
• MicroCrypt Assumptions with Quantum Input Sampling and Pseudodeterminism: Constructions and Separations
• Quantum Pseudorandomness Cannot Be Shrunk In a Black-Box Way
• The power of a single Haar random state: constructing and separating quantum pseudorandomness
• Quantum-Computable One-Way Functions without One-Way Functions

Related papers

• SoK: AI-Augmented Binary Reversing
• Relaxed Sender Anonymity for CBDC Interbank Settlement: A Zero-Knowledge Approach on Permissioned EVM
• Calibration-Family Overfit: Why Trusted Sabotage Monitors Don't Transfer Across Lineages
• Efficient Fuzzy PSI under One-Sided Assumptions
• Sealing the Audit-Runtime Gap for LLM Skills
• Token Composition: A Graph Based on EVM Logs