Overstretch everything?

While a well-established fact for NTRU, it is widely believed that other lattice-based primitives such as MLWE and NTWE do not suffer from overstretching, a phenomenon where discovering a lattice vector strictly longer than the secret key(s) in a dense sublattice spanned by the secrets results in a substantially easier attack than the conventional secret key recovery attack. Nevertheless, MLWE and NTWE, similarly to NTRU, yield q-ary lattices that have a relatively dense sublattice spanned by the secrets, which makes it possible that an overstretched regime could exist for all three of the above-mentioned primitives. We generalise and apply the methodology developed in the work of Ducas and van Woerden in 2021 to MLWE and NTWE to investigate the possibility of an overstretched regime. We discover that any lattice with this structure is expected to suffer from the dense sublattice attack. For MLWE, the asymptotic fatigue point is predicted to be so large that it is not of practical concern. For NTWE, we predict it may be of practical concern and demonstrate the attack experimentally, providing the first evidence for a dense sublattice attack on NTWE.