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 (Formula presented.), reducing the original relation to a linear system consisting only of (Formula presented.). Given partial knowledge of (Formula presented.), this projected system admits a unique solution once a sufficient number of independent constraints is available. After recovering (Formula presented.), the problem of determining (Formula presented.) 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.

Text 126472.pdf - Published Version Available under License Creative Commons Attribution. Download (388kB) Official URL or Download Paper: https://www.mdpi.com/2227-7390/14/10/1749

Actions (login required)

View Item