The issue is that finding a class of sparse matrices that don't ruin the security guarantees is really tricky. This more or less is the approach that ring-lwe t

The issue is that finding a class of sparse matrices that don't ruin the security guarantees is really tricky. This more or less is the approach that ring-lwe takes - the matrices can be represented as polynomials and therefore are only linear in the security parameter, not quadratic (it also speeds up all the other operations via FFT-type techniques). But even there you have to be really careful about how you're constructing these polynomials, which boils down to a bunch of fancy algebraic number theory.