On the computational hardness needed for quantum cryptography

on YouTube ↗20m

" summary

Defines EFI pairs (efficiently sampleable, statistically far but quantumly indistinguishable mixed states) and shows they imply commitments, oblivious transfer, quantum MPC, and quantum computational zero‑knowledge; conversely, weakened versions of those primitives (no statistical security, semi‑honest only, nontrivial functionality) imply EFI. Uses mixed‑state trace distance, quantum pseudorandomness and oracle separations to argue EFI does not black‑box yield classical one‑way functions, and leaves open constructing pseudorandom states from EFI and comparing EFI to quantum one‑wayness.

AI-written summary · about

" chapters (10)

1. 0:00Intro
2. 0:20Root of classical crypto: one-way functions
3. 1:40Landscape of classical cryptography
4. 3:38Quantum changes landscape dramatically
5. 7:12Goldreich EFID pairs: non-trivial computational indistinguishability
6. 9:16EFI pairs (of quantum states)
7. 10:30What is so different about EFI vs EFID?
8. 14:10Minimality of EFI in a quantum world
9. 16:03Summary
10. 17:56Open questions

" related talks

• 48mOn the Computational Hardness Needed for Quantum CryptographyRan Canetti · Minimal Complexity Assumptions for Cryptography 2023
• 48mBlack-Box Separations in Quantum CryptographyMohammad Mahmoody · Minimal Complexity Assumptions for Cryptography 2023
• 01h 26mQuantum FHEUrmila Mahadev · Lattices: New Cryptographic Capabilities 2020
• 01h 13mQuantum 3Dakshita Khurana · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 59mAn Introduction to Quantum ObfuscationJames Bartusek · Obfuscation
• 57mThe Cryptographic Lens: Visions of our Past and FutureShafi Goldwasser · Symposium on Visions of the Theory of Computing 2013
• 34mQuantum MinimalismMark Zhandry · Minimal Complexity Assumptions for Cryptography 2023
• 12mOne-Way Functions Imply Secure Computation in a Quantum WorldAndrea Coladangelo · Meet the Fellows Welcome Event