Lattice-based cryptography stands as one of the most promising pillars of post-quantum security. Among its various constructions, the NTRU problem and the GGH multilinear map have been central to the development of advanced primitives like fully homomorphic encryption and functional encryption. However, a paper published in the LMS Journal of Computation and Mathematics presents a significant challenge to these foundations. The authors describe a new algorithm that solves the NTRU problem by reducing high-dimensional problems into manageable subfield problems, effectively breaking the GGH multilinear map even in scenarios previously thought to be secure.
The NTRU Problem and the GGH Map
The NTRU problem is a foundational challenge in lattice-based cryptography. It involves finding two "small" polynomials, $\mathbf{a}$ and $\mathbf{b}$, given their ratio $\mathbf{h} = [\mathbf{f}/\mathbf{g}]_q$ in a specific polynomial ring $\mathbb{Z}[X]/\langle X^{n}+1\rangle$. The security of many cryptographic schemes rests on the "NTRU assumption"—the belief that finding these small polynomials is computationally infeasible for large $n$.
A particularly ambitious application of these structures is the GGH multilinear map, proposed by Garg, Gentry, and Halevi. While earlier versions of GGH were compromised by the "Hu–Jia attack," that specific vulnerability relied on the existence of "low-level encodings of zero"—publicly available hints that an attacker could exploit. It was widely hoped that removing these low-level encodings would restore the scheme's security. This research addresses that hope directly, investigating whether the GGH scheme can withstand cryptanalysis without such hints.
Methodology: Subfield Reduction via the Trace Function
The core innovation of this work is a subfield reduction technique. Standard lattice reduction algorithms, such as BKZ, face exponential complexity as the dimension of the lattice grows. The authors bypass this limitation through an iterative algebraic approach:
- Algebraic Mapping: Using the trace function from Galois theory, the algorithm maps a problem defined over a high-dimensional field $K_0$ down to a subfield $K_m$ with a significantly lower dimension.
- Iterative Reduction: The authors demonstrate that if the original polynomials $\mathbf{f}$ and $\mathbf{g}$ are sufficiently small, their traces in the subfield will also remain relatively small. This transformation creates a new, smaller instance of the NTRU problem.
- Lattice Solving: Once the dimension is reduced to a manageable level, standard lattice reduction algorithms (BKZ) are applied to find the short vectors within the subfield.
- Lifting: The solution found in the subfield is then "lifted" back to the original high-dimensional field to solve the initial problem.
While concurrent research explored using the norm function for similar reductions, this paper utilizes the trace function. The authors argue that the trace function provides a clearer path to a quasi-polynomial time attack and slightly more robust results in the context of the GGH map.
Cryptanalysis of the GGH Scheme
For the GGH attack specifically, the authors show that the subfield algorithm can be applied if an attacker possesses a known pair of plaintext and ciphertext along with some "top-level" encodings of zero. By applying their reduction technique, they can construct a "level-0" encoding of zero. This construction effectively re-enables the types of attacks that were previously thought to be blocked by the removal of low-level encodings, compromising the security ground of the scheme.
Key Results and Complexity
The algorithm achieves a quasi-polynomial complexity of $2^{O(\log^2 \lambda)}$, where $\lambda$ is the security parameter. This is a dramatic improvement over the exponential time previously assumed necessary to solve such problems.
The attack is particularly effective in the "overstretched" NTRU setting—where the ratio between the modulus $q$ and the size of the secret polynomials is large. Using the parameters originally suggested by Garg, Gentry, and Halevi, the authors demonstrate that the GGH scheme can be broken in quasi-polynomial time relative to its security parameter.
Implications for Future Cryptography
The findings suggest that the internal structure of the GGH map is more vulnerable than initially realized. The paper proves that "low-level encodings of zero" are not a prerequisite for successful cryptanalysis; as long as top-level zeros and a single plaintext-ciphertext pair are available, the scheme can be compromised.
To defend against this subfield reduction attack, the authors suggest that the dimension $n$ of the ring would need to be increased significantly (to at least $\Omega(\lambda^3)$). However, such an increase would make the resulting cryptographic schemes substantially slower and less practical for real-world use. Consequently, this research highlights the need for new multilinear map candidates that do not rely on these specific, vulnerable ring structures.
Summary updated