On the Computational Hardness Needed for Quantum Cryptography

on YouTube ↗48m

" summary

Claims that EFI pairs — efficiently samplable states that are statistically far but computationally indistinguishable — are necessary and broadly sufficient for quantum cryptography: the work builds EFI from minimal commitment variants, from semi‑honest oblivious transfer derived from general commitments, and from any nontrivial MPC, and shows how to get QCZK for all of QIP from any EFI. Constructions use canonical commit-by-running-Gb, trace‑distance binding, and MPC composition; several amplification and separations remain open.

AI-written summary · about

" chapters (24)

1. 0:00Intro
2. 0:42One-way functions: A minimal primitive for computational cryptography
3. 3:18A dichotomy for cryptographic primitives
4. 6:00Come quantum information processing...
5. 7:31Quantum information: A brave new world...
6. 11:03Are PRSG's minimal for quantum crypto?
7. 12:58A dichotomy for quantum cryptography?
8. 15:57EFI pairs (of quantum states)
9. 23:41EFI & quantum cryptography
10. 24:52Quantum bit commitment
11. 26:37Bit commitment from EFI [Yan22]
12. 29:02EFI from general commitments
13. 30:28EFI from weak commitment: roadmap
14. 31:28Oblivious transfer (semi-honest receiver)
15. 32:25EFI from semi-honest oblivious transfer
16. 34:30Oblivious transfer from commitment
17. 35:051-round honest oblivious transfer
18. 37:322-round semi-honest oblivious transfer
19. 38:18Secure multiparty computation
20. 39:46From EFIs to Zero knowledge proofs
21. 43:02EFIs from Zero knowledge proofs
22. 44:07Summary: Minimality of EFI
23. 44:33Candidate EFI from random quantum circuits
24. 46:28Open problems / musings

" related talks

• 20mOn the computational hardness needed for quantum cryptographyRan Canetti, Luowen Qian, Zvika Brakerski · ITCS 2023
• 57mThe Cryptographic Lens: Visions of our Past and FutureShafi Goldwasser · Symposium on Visions of the Theory of Computing 2013
• 01h 15mTo interact or not to interact: Cryptographic proof systems and the Fiat-Shamir heuristicAlex Lombardi · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 49mQuantum CryptanalysisRen Taguchi, Jiayu Xu · RSA Conference 2023
• 01h 13mQuantum 3Dakshita Khurana · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 05mNew Quantum Cryptographic Primitives IMark Zhandry · Quantum and Lattices Joint Reunion Workshop
• 25mCrypto's Quantum Leap: Blockchain vs Quantum ComputerHeewon Chung · UDC 2025
• 31mMachine-checking post-quantum cryptographyAndreas Hülsing · Post-Quantum Cryptography Conference Amsterdam 2023