[wish5031]

Talking about LWE, the author says:

> A major problem with this system is that it has very large keys. To encrypt just one bit of information requires public keys with size n^2 in the security parameter.

Can't this be solved by e.g. forcing some kind of random sparsity structure on the matrix and then compressing with a format like CSC or CSR? (probably just not understanding LWE completely)

[blperez]

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.

[wish5031]

Hm, I see. Thanks!