Computing on Encrypted Data via Secret Dual Codes
summary
Claim: a secret-key scheme lets a client upload an encrypted large X and issue unbounded hidden queries q with sublinear download and only a short secret key. Construction encodes X and q with secret dual codes plus noise (mixture and planting noise) and uses a trapdoor matrix so client work is tiny. Security relies on LPN or a new Learning Subspace with Noise assumption; concrete implementations show overheads like 10–25% (practical widths ~10k) and PIR communication down to n^ε, so the builds are efficient and empirically workable.
AI-written summary · about
chapters (15)
- 0:00Introduction and motivation
- 1:09Why new assumptions?
- 5:22The searchable encryption story
- 8:33Modeling the problem
- 12:55Core functionalities
- 18:06Applications and existing work
- 22:16Building EMVP constructions
- 25:51Field-agnostic protocols
- 29:02Main research results
- 33:45Secret dual codes approach
- 37:25Efficiency and protocol details
- 41:56Security through noise
- 45:42Learning subspace with noise
- 53:27Cryptanalysis and attacks
- 57:03Conclusion and future outlook
related talks
43mCode-based Cryptography
01h 04mHow to Encrypt a Functionality
01h 00mSecure Computation 3
01h 07mLattices and Encrypted Computation
58mObfuscation 2
01h 05mObfuscation from Noisy Linear FE
01h 09mNoisy Connections: A Survey of Interactive Coding and Its Borders with Other Topics
01h 06mSecure Computation and Low-Complexity Cryptography