Cryptanalysis of the CLT13 Multilinear Map

Jung Hee Cheon, Kyoohyung Han, Changmin Lee, Hansol Ryu, Damien StehléJ. Cryptol 2019 · DOI

Abstract

This paper describes a polynomial-time cryptanalysis of the approximate multilinear map proposed by Coron, Lepoint, and Tibouchi (CLT13). The scheme includes a zero-testing functionality that determines whether the message of a given encoding is zero. While useful for applications, this functionality leaks linear combinations of secret elements. By collecting zero-testing outputs, we construct a matrix containing hidden information as eigenvalues and recover all secret elements via diagonalization. Additionally, we provide polynomial-time algorithms to break security assumptions like subgroup membership, decision linear, and graded external Diffie–Hellman problems using determinant computations and greatest common divisors.

Introduction

Multilinear maps are a powerful cryptographic primitive, enabling advanced applications such as one-round multiparty key exchange and general-purpose program obfuscation. However, constructing secure and efficient multilinear maps is a significant challenge. In 2013, Coron, Lepoint, and Tibouchi proposed CLT13, a construction based on the Chinese Remainder Theorem (CRT) over integers. Unlike earlier lattice-based schemes like GGH13, CLT13 was initially believed to be immune to "zeroizing attacks." This work investigates the security of CLT13, specifically testing whether its underlying hardness assumptions—such as Subgroup Membership and Decision Linear—hold against a polynomial-time adversary.

Methodology

The cryptanalysis introduces two primary techniques to break the CLT13 scheme:

1. The Eigenvalue Technique

This method achieves a "total break" of the system. The authors observe that the zero-testing parameter, intended to verify if an encoding represents zero, inadvertently leaks linear combinations of secret elements. By gathering multiple such outputs, an attacker can construct two matrices, $W$ and $W'$. The matrix $V = W \cdot (W')^{-1}$ possesses eigenvalues that correspond directly to the secret message components. Once these eigenvalues are identified, the secret primes $p_i$ are recovered through Greatest Common Divisor (GCD) calculations.

2. The Determinant Technique

This approach targets specific decision-based security assumptions, such as the Subgroup Membership problem. Rather than recovering the full secret key, the attacker constructs matrices from encodings and computes their determinants. If an encoding belongs to a specific subgroup, its determinant shares a large common factor with the system's public parameters. This allows the attacker to distinguish between distributions in polynomial time, effectively breaking the assumption.

Mathematically, these attacks solve a variant of the CRT-Approximate Greatest Common Divisor (CRT-ACD) problem when provided with auxiliary input from the zero-testing parameter.

Results

The analysis yields several critical results:

  • Total Parameter Recovery: The eigenvalue technique successfully recovers all secret primes $p_i$ of the CLT13 scheme.
  • Efficiency: The attack is highly practical, running in polynomial time $\tilde{O}(n^{\omega+1} \cdot \eta)$, where $n$ is the number of secret primes and $\eta$ is their bit-length.
  • Broad Cryptographic Impact: The paper provides direct algorithms to break Subgroup Membership, Decision Linear (DLIN), and Graded External Diffie-Hellman (GXDH) problems within the CLT13 framework.

Discussion and Limitations

The primary requirement for these attacks is the availability of "low-level encodings of zero." While such encodings are often provided in applications like obfuscation for re-randomization, a version of CLT13 that restricts access to these might resist this specific attack.

Following this work, several "immunization" attempts were proposed for CLT13. However, many were subsequently broken by refinements of the eigenvalue technique described here. The findings underscore that the zero-testing feature, while functional, acts as a significant side channel.

Conclusion

The cryptanalysis presented here demonstrates that the CLT13 multilinear map is insecure in its original form. By reducing complex cryptographic assumptions to standard linear algebra operations—specifically diagonalization and determinant calculation—the authors show that the "approximate" nature of the CRT-based scheme can be bypassed. Finding a truly secure and efficient multilinear map remains one of the most significant open challenges in modern cryptography.

Summary updated

BibTeX
@article{cheon2019cryptanalysis,
  author = {Jung Hee Cheon and Kyoohyung Han and Changmin Lee and Hansol Ryu and Damien Stehlé},
  title = {{Cryptanalysis of the CLT13 Multilinear Map}},
  journal = {J. Cryptol.},
  year = {2019},
  doi = {10.1007/s00145-018-9307-y},
}
Figure