Multilinear Maps and Attacks I

on YouTube ↗01h 00m

" summary

Describes lattice-based multilinear maps built over R = Z[x]/(x^n+1) with encodings as short numerators modulo an ideal generated by a small g and masked by powers of a secret Z (level‑k encodings ~ C / Z^k), sampling from wide Gaussians to get uniform cosets, and equality via a zero‑testing parameter H·Z^k·g that yields CH/Z small iff g divides C. Presents the GGH scheme and CLT variants, notes concrete attacks that recover structure for many parameters, and cites Coron et al. as a recent fix resilient to known attacks.

AI-written summary · about

" chapters (7)

1. 0:00Start
2. 2:16Cryptographic Bilinear Maps
3. 2:48Bilinear Maps – Definitions
4. 14:46Multilinear Maps: Classical Notion
5. 19:44Bilinear Maps: Our visualization
6. 35:50Background
7. 54:58Equality Checking - Correctness II

" related talks

• 01h 16mMultilinear Maps Over the Integers: From Design to SecurityTancrède Lepoint · The Mathematics of Modern Cryptography
• 54mGraph-Induced Multilinear Maps from LatticesShai Halevi · The Mathematics of Modern Cryptography
• 01h 29mLattices, Multilinear Maps and Program ObfuscationYilei Chen · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 06mObfuscation: Past, Present, and Possible FuturesAmit Sahai · Securing Computation (Simons Institute, June 2015)
• 01h 04mHow to Encrypt a FunctionalityAmit Sahai · Quantum Games and Protocols
• 01h 04mUsing Lattices for CryptanalysisNadia Heninger · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 57mTutorial: Encrypted Computation from LatticesHoeteck Wee · Lattices: New Cryptographic Capabilities 2020
• 01h 07mLattices and Encrypted ComputationVinod Vaikuntanathan · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020