Quantum pseudorandomness in Algorithmica, and its implications to cryptography and complexity
summary
The paper constructs a classical oracle world where P = PH yet t‑forrelation states (Hadamard/phase interleavings of t Boolean functions) remain single‑copy secure PRS, and it reduces security to a concrete hash property called hardness of shifted Forrelation. The proof uses Raz–Tal and Aaronson–Ingram–Kretschmer average‑case hardness for OR∘Forrelation and shows random oracles satisfy the property, yielding EFI, commitments and OT in the black‑box model; multi‑copy security remains conjectural.
AI-written summary · about
chapters (16)
- 0:00Intro
- 2:22The dawn of a new era for quantum cryptography: The experimental prototype is working!
- 4:45Information theoretic security is still unachievable
- 8:30Oracle separations (informal)
- 9:27Pseudorandom States (PRS)
- 13:19Oracle separations (formal)
- 14:49Why isn't K21 conclusive?
- 17:52Quantum cryptography candidates without OWF
- 20:38Starting point: binary phase PRS
- 24:02Hadamard/phase cocktail construction
- 29:49Forrelation problem [Aaronson'09]
- 31:30Hardness of shifted Forrelation
- 34:47Implications for cryptography
- 36:41Does cryptography need complexity assumptions?
- 40:58(Meta-)complexity for quantum tasks
- 44:11Past, present & future of quantum complexity
related talks
59mQuantum cryptography and quantum complexity
01h 08mNew Quantum Cryptographic Primitives II
46mObfuscation of Unitary Quantum Programs
46mCryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity
56mQuantum 4
55mFoundations 2
58mQuantum 2
31mObfuscation of Probabilistic Circuits and Applications