Multilinear maps are often described as the "holy grail" of modern cryptography. If they could be built securely, they would enable transformative applications like general-purpose program obfuscation, multiparty non-interactive key exchange, and highly efficient broadcast encryption. However, as Waters et al. and Zhandry noted in Low Overhead Broadcast Encryption from Multilinear Maps, these maps are complex primitives that often face significant noise and security challenges.
The central problem in this field is a recurring cycle: new candidate constructions are proposed, only to be systematically dismantled by structural cryptanalysis. This research direction focuses on understanding these vulnerabilities and finding ways to build advanced cryptography on more stable foundations.
The Zeroizing Attack
The most devastating class of attacks on multilinear maps is known as the "zeroizing attack." To understand why this works, we must look at how these maps handle data. Multilinear maps allow users to perform algebraic operations on "encodings" of values without revealing the values themselves. To make these maps useful, they typically include a zero-testing parameter, which allows anyone to check if an encoding represents the value zero.
In Cryptanalysis of the Multilinear Map over the Integers, Lee et al. demonstrated that this zero-testing feature is a double-edged sword. By collecting several "low-level encodings of zero," an attacker can exploit the interaction between the underlying mathematical structures—such as the Chinese Remainder Theorem (CRT) and Approximate Greatest Common Divisor (ACD) problems—to recover the scheme's secret parameters in polynomial time.
This vulnerability is not limited to public zero-encodings. Jeong et al. showed in An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low-level encoding of zero that even if these encodings are withheld, an attacker can still reconstruct the secret internal structure using only top-level information and plaintext-ciphertext pairs.
The Cat-and-Mouse Game of CLT Maps
The history of the Coron-Lepoint-Tibouchi (CLT) multilinear map illustrates the fragility of these constructions. After the original CLT13 map was broken, researchers proposed a patched version known as CLT15. However, Lee et al. achieved a "total break" of CLT15 in Cryptanalysis of the New CLT Multilinear Map over the Integers using eigenvalue and determinant attacks.
The authors demonstrated that the fundamental linearity of these maps allows attackers to transform cryptographic encodings into linear algebra problems. As Han et al. explained in their 2019 cryptanalysis, these attacks scale efficiently with matrix multiplication, meaning that even increasing security parameters may not provide long-term protection against a determined adversary.
Impact on Indistinguishability Obfuscation
The instability of multilinear maps has direct consequences for Indistinguishability Obfuscation (iO), a technique that aims to hide the internal logic of a program while keeping it functional. As Brakerski et al. argued in Obfuscating Conjunctions, there is a significant gap between theoretical security proofs and the practical robustness of these schemes. Even if the high-level logic of an obfuscator is sound, the failure of the underlying multilinear map compromises the entire system.
This vulnerability was further highlighted by Hhan et al. in Cryptanalyses of Branching Program Obfuscations over GGH13 Multilinear Map from the NTRU Problem, which showed that even iO schemes using "recommended" parameters were insecure against new lattice-based attacks.
Pathways to Robustness
Faced with the persistent failure of high-degree multilinear maps, the research community has pivoted toward three main strategies:
- Reducing Complexity: Early iO constructions required maps of degree 30 or higher, which are mathematically fragile. In Projective Arithmetic Functional Encryption and Indistinguishability Obfuscation From Degree-5 Multilinear Maps, Ananth et al. slashed this requirement to degree-5 maps, which are significantly more stable.
- New Abstractions: Some researchers seek to fix the maps themselves. Kim et al. proposed the Ring Encoding System (RES) in Multilinear Map via Scale-Invariant FHE, which uses scale-invariant Fully Homomorphic Encryption to resist zeroizing attacks while improving efficiency.
- Eliminating Multilinear Maps: Perhaps the most promising direction is building advanced primitives from standard, battle-tested assumptions. Ananth et al. demonstrated in Indistinguishability Obfuscation Without Multilinear Maps that iO can be achieved using low-degree pseudorandomness and security amplification. Similarly, Francati et al. showed in Multi-key and Multi-input Predicate Encryption from Learning with Errors how to perform complex tasks like matchmaking encryption using only the standard Learning with Errors (LWE) assumption.
By moving away from fragile, non-standard mathematical structures, the field is gradually bridging the gap between theoretical "holy grails" and secure, implementable cryptographic tools.
Key Foundational Work
Obfuscating Conjunctions (2013) — contributed 2 concept elements to this direction.
Cryptanalysis of the Multilinear Map over the Integers (2014) — contributed 2 concept elements to this direction.
Obfuscation for Evasive Functions (2013) — contributed 1 concept elements to this direction.