Multilinear Maps Over the Integers: From Design to Security

on YouTube ↗01h 16m

" summary

Proposes an integer-based multilinear map (CLT-style) that replaces the public modulus for zero-testing with a fresh random modulus and builds a LLL-based lattice gadget to produce a short zero-test vector, aiming to defeat the matrix/GCD attack that recovers secret primes. Implements a proof-of-concept: six levels, 80-bit target security, 66 million-bit encodings, setup taking hours and key-exchange/zero-test around 20 seconds; claims the fix heuristically resists known algebraic attacks but invites further cryptanalysis.

AI-written summary · about

" chapters (10)

1. 0:00Timeline and motivation
2. 3:07Understanding CLT schemes
3. 6:47Multilinear map principles
4. 11:56Zero testing procedure
5. 18:08Security assumptions
6. 20:51Cryptanalytic attacks
7. 27:36New scheme modifications
8. 39:02Implementation and results
9. 46:55Future research directions
10. 50:00Discussion phase

" related talks

• 51mMultilinear Maps and Attacks IISanjam Garg · Cryptography Boot Camp 2015
• 01h 00mMultilinear Maps and Attacks ISanjam Garg · Cryptography Boot Camp 2015
• 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
• 57mEssentially Optimal Interactive Certificates in Linear AlgebraErich Kaltofen · Geometric Complexity Theory 2014
• 31mIdentity-Based EncryptionParhat Abla, Huiwen Jia · RSA Conference 2024
• 01h 04mUsing Lattices for CryptanalysisNadia Heninger · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020