Quantum Proofs of Deletion for Learning with Errors

on YouTube ↗21m

" summary

Constructs LWE-based public-key and homomorphic encryption schemes that produce a single quantum ciphertext whose Fourier-basis measurement yields a classical short-SIS preimage pi that verifies deletion publicly. Builds on coherent Ajtai hashing and Dual-Regev / Dual-GSW style encodings and introduces a provable property called Gaussian-collapsing under LWE; security for certified deletion requires a stronger conjecture (Strong Gaussian-collapsing). Implements public verification directly; homomorphic variant works with one extra round but relies on the unproven strong collapse.

AI-written summary · about

" chapters (10)

1. 0:00Quantum Encryption with Certified Deletion
2. 2:08Fully Homomorphic Encryption with Certified Deletion
3. 3:36Learning with Errors (Regev '05)
4. 5:16Short Integer Solution (Ajtai '96)
5. 6:33Gaussian superpositions
6. 8:05Duality of Gaussian states
7. 9:58Dual-Regev public-key encryption with certified deletion
8. 14:03Gaussian-Collapsing Hash Functions
9. 16:08Strong Gaussian-Collapsing Conjecture
10. 19:20Summary

" related talks

• 46mCryptography with Certified DeletionDakshita Khurana · Minimal Complexity Assumptions for Cryptography 2023
• 01h 28mThe Learning With Errors Problem and Cryptographic ApplicationsChris Peikert · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 58mQuantum 2Mark Zhandry · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 13mQuantum 3Dakshita Khurana · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 15mAlgebraic Lattices and Ring Learning with ErrorsChris Peikert · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 07mLattices and Encrypted ComputationVinod Vaikuntanathan · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 32mBeating Classical Impossibility of Position VerificationJiahui Liu, Qipeng Liu, Luowen Qian · ITCS 2022
• 01h 08mNew Quantum Cryptographic Primitives IIMark Zhandry · Quantum and Lattices Joint Reunion Workshop