3 ms·
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 k
by wish5031 8y ago
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 8y agoThe 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 8y agoHm, I see. Thanks!