Quantum cryptography and quantum complexity

on YouTube ↗59m

" summary

Constructs a standard classical oracle where P = NP yet quantum‑computable one‑way functions and even trapdoor variants exist, using a forrelation encoding of a random oracle fed into a PH-to-F̄ oracle. Proof combines Raz–Tal style quantum vs. PH separation, BBBV limitations, and a new AC0 distributional sensitivity concentration bound to justify resampling hybrids. The built oracle O = PH^{F̄} yields candidate quantum one‑way functions and the security proof succeeds relative to O.

AI-written summary · about

" chapters (7)

1. 0:00Introduction and overview
2. 1:52Computational hardness review
3. 8:50Four types of hardness
4. 11:08Defining the four hardness buckets
5. 20:11Main results and open questions
6. 25:53Oracle construction strategy
7. 34:20Proof technicalities and intuition

" related talks

• 46mQuantum pseudorandomness in Algorithmica, and its implications to cryptography and complexityLuowen Qian · Minimal Complexity Assumptions for Cryptography 2023
• 01h 06mQuantum Advantage Without StructureMark Zhandry · Quantum and Lattices Joint Reunion Workshop
• 37mQuantum Pseudorandomness and Classical ComplexityWilliam Kretschmer · Quantum Wave in Computing Reunion 2021
• 59mAn Introduction to Quantum ObfuscationJames Bartusek · Obfuscation
• 56mQuantum 4Dakshita Khurana · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 26mQuantum FHEUrmila Mahadev · Lattices: New Cryptographic Capabilities 2020
• 21mQuantum versus Randomized Communication Complexity, with Efficient PlayersUma Girish, Ran Raz, Avishay Tal · ITCS 2021
• 01h 08mNew Quantum Cryptographic Primitives IIMark Zhandry · Quantum and Lattices Joint Reunion Workshop