Multilinear Maps and Attacks II

on YouTube ↗51m

" summary

Describes concrete breaks of candidate multilinear maps: publishing encodings of zero and a zero-test value lets an attacker recover short CRT components (a weak discrete log giving C' ≈ C mod Q of size about sqrt(Q)), which already breaks DDH-style hardness; for CLT a matrix construction over many samples yields diagonal entries and allows matrix eigenvalue extraction to recover hidden factors and fully break schemes. Presents the CLT fix that adds noise and nonlinearity, notes quantum/subexponential lattice attacks, and distinguishes obfuscation use cases where zero encodings are not required.

AI-written summary · about

" chapters (13)

1. 0:00Intro
2. 0:20Problem with the scheme
3. 4:37Encoding
4. 10:20Discrete Log
5. 11:48Level 1 Encoding
6. 16:25CLT Scheme
7. 22:29CLT Construction
8. 27:45CLT Engine
9. 28:20CLT Samples
10. 29:58CLT Zero Test
11. 31:11CRT Zero Test
12. 36:45Encodings
13. 42:02Summary

" related talks

• 01h 16mMultilinear Maps Over the Integers: From Design to SecurityTancrède Lepoint · 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)
• 54mGraph-Induced Multilinear Maps from LatticesShai Halevi · The Mathematics of Modern Cryptography
• 01h 04mHow to Encrypt a FunctionalityAmit Sahai · Quantum Games and Protocols
• 01h 04mCryptanalysis of Candidate Program ObfuscatorsYilei Chen · Lattices: New Cryptographic Capabilities 2020
• 01h 07mLattices and Encrypted ComputationVinod Vaikuntanathan · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 46mIndistinguishability Obfuscation from Bilinear Maps and LPN VariantsNeekon Vafa · Obfuscation