Paper 2026/2443

Worst-Case Hardness for Succinct and Decomposed Learning with Errors

Abstract

The succinct LWE (CRYPTO~'24) and decomposed LWE (CRYPTO~'25) assumptions are two recently introduced variants of the celebrated LWE problem, known to imply the existence of numerous new cryptographic primitives. Yet, the hardness of these problems has thus far remained poorly understood, since there is no known reduction to LWE. In this work, we study these lattice problems from a foundational perspective. Our main technical contribution is a worst-case-to-average-case reduction from \emph{superlattice SVP} (SuperSVP) to succinct SIS. We introduce SuperSVP as a variant of SVP for general lattices in which the solver is additionally given, as a hint, a short basis for a related superlattice. Combining this result with our quantum reduction from succinct SIS to succinct LWE, which is an analog of Regev's SIS-to-LWE reduction, and with our search-to-decision reduction establishes worst-case hardness for succinct LWE. Finally, we show that succinct and decomposed LWE are equivalent, extending this conclusion to decomposed LWE. Overall, our work places succinct and decomposed LWE on firmer theoretical ground and, as a direct consequence, establishes the \emph{worst-case} hardness of a variety of cryptographic primitives, known to be implied by these assumptions.