The State of Cryptographic Multilinear Maps

Explore the current state of cryptographic multilinear maps in this comprehensive 49-minute lecture. Delve into fundamental crypto tools and constructions, starting with an introduction to discrete-logarithm and its application in DH Key Exchange. Progress beyond DDH to examine bilinear maps and the crucial concept of testing for zero. Investigate MMAP constructions, including syntax, tag structures, and the GGH13 construction. Analyze the properties and vulnerabilities of GGH13, including "zeroizing" attacks and attempted fixes. Discuss the implications of these security challenges and explore non-linear zero-test methods. Conclude by examining the security landscape of MMAPs, known weak distributions, and performance considerations. Gain a thorough understanding of this complex cryptographic topic and its current challenges.

Intro
Crypto Tools and Constructions
Example: Discrete-Logarithm
Application: DH Key Exchange
Beyond DDH: Bilinear Maps
Main Ingredient: Testing for Zero
MMAP Constructions
Syntax of MMAPS
Restricting Operations
Examples of Tag Structures
The GGH13 Construction
Properties of GGH13
"Zeroizing" Attacks GGH13
An Attempted Fix
Breaking the Fix
The Moral (so far)
Non-Linear Zero-Test (GHL15)
Security Landscape
Thinking About MMAP Security
Known Weak Distributions
Other Attacks
Performance