On the Structural Solvability of MLWE with Rank-Deficient Public Matrices

The security of Module Learning With Errors (MLWE) relies on the assumption that the public matrix is sampled uniformly and forms a full-rank operator. In this work, we examine the structural consequences of relaxing this assumption by considering public matrices that demonstrate slot-wise rank deficiency under the Number Theoretic Transform (NTT). Focusing on the case where each NTT slot matrix has rank 1, we show that this leads to enlarged left nullspace, which allows the elimination of the secret component s1, reducing the original relation to a linear system consisting only of s2. Given partial knowledge of s2, this projected system admits a unique solution once a sufficient number of independent constraints is available. After recovering s2, the problem of determining s1 reduces to solving a bounded linear system, which can be viewed as a structured instance of the Short Integer Solution (SIS) problem. These results provide a dimension-based characterization of solvability under slot-wise rank-deficient public matrices. Using ML-DSA as a concrete instantiation, we illustrate how such structural deviations affect the behavior of the system and discuss simple safeguards, such as rank verification during key generation, to mitigate these issues.