Lattice Assumptions with Hints: Succinct LWE and its Applications

on YouTube ↗57m

" summary

Proposes a family of succinct LWE assumptions and shows how a public trapdoor yields a practical matrix commitment that compresses n×L matrices to n×m commitments; from that it builds distributed broadcast encryption with polylog-size ciphertexts and key-policy ABE with succinct ciphertexts by committing the attribute encoding. Construction uses Merkle-style recursion to make the public trapdoor size independent of L (critical bound 2 m^2), and the main open goal is basing decomposed LWE on plain LWE or a worst-case lattice problem.

AI-written summary · about

" chapters (8)

1. 0:00Lattice assumptions and LWE
2. 4:18Succinct LWE overview
3. 16:42Hardness axes and trade-offs
4. 21:38Matrix commitment scheme
5. 27:39Distributed broadcast encryption
6. 37:12Succinct attribute-based encryption
7. 44:17Matrix commitments from LWE
8. 52:52Summary and open problems

" related talks

• 01h 04mThe Mathematics of Lattices IIVinod Vaikuntanathan · Cryptography Boot Camp 2015
• 46mOptimal Broadcast Encryption and More from Evasive LWEHoeteck Wee · Quantum and Lattices Joint Reunion Workshop
• 01h 29mLattices, Multilinear Maps and Program ObfuscationYilei Chen · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 21mLattice-Inspired Broadcast Encryption and Succinct Ciphertext-Policy ABEVinod Vaikuntanathan, Zvika Brakerski · ITCS 2022
• 01h 40mHistorical Talk on Lattice-Based CryptographyDaniele Micciancio · The Mathematics of Modern Cryptography
• 01h 07mLattices and Encrypted ComputationVinod Vaikuntanathan · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 39mLattice Based Cryptography PrimerBob Relyea · DevConf.CZ 2021
• 57mTutorial: Encrypted Computation from LatticesHoeteck Wee · Lattices: New Cryptographic Capabilities 2020