An Efficient Quantum Algorithm for a Variant of the Closest Vector Problem

Shor has done it again!

I'm not an expert on quantum algorithms, but if you're wondering what the implications of this are, here's what I understand as a cryptographer: a lot of post-quantum cryptography (i.e., not anything we use now like RSA or ECC) relies on the hardness of the closest vector problem (given a real-valued vector, what is the closest vector in a discrete lattice to that real vector?).

This algorithm gets really close to invalidating the security assumption of this problem, which is the basis for a lot of modern post-quantum crypto (like a lot of fully homomorphic encryption schemes), so we might expect it to fall soon.

Also: this does not affect the security of symmetric schemes like AES at all, those are still safe in a quantum world.