3 ms·

I though LWE and SVP were NP-hard. Doesn't breaking them mean NP is in BQP, and thus classical computer encryption is entirely broken with quantum computers ?

I though LWE and SVP were NP-hard. Doesn't breaking them mean NP is in BQP, and thus classical computer encryption is entirely broken with quantum computers ? How would we recover from this back to the drawing board ?

u1hcw9nx 2mo ago
Exact SVP is NP-hard, but LWE is not. Kyber/ML-KEM and Dilithium/ML-DSA) rely on approximate lattice problems, not exact ones.