[da-bacon]

People seemed to be focusing on the fact that this wouldn’t break the NIST leading PQC public key cryptosystem, but I think that misses the point. This takes a problem at the core of this security, which previously only had an exponential approximation, and finds a polynomial approximation. Sure that polynomial is too high O(n^4.5) to break the leading proposed systems, but I mean are you really feeling safe when an exponential just changed to a polynomial?

An analogy would be something like this. Factoring is hard. We base RSA on the hardness of this problem and there we use numbers that are the product of two primes. Someone just found an algorithm that doesn’t work to find the product of two primes, but can take a product of four primes and return two products of two primes. Do you feel safe with RSA?

Anyway the paper could be wrong or it could be right, it will take a while for those in the field to dig through this. As a cautionary tale, there have been a few extra good quantum people who have proposed quantum attacks on lattice problems that have later been shown to have bugs.

[Ar-Curunir]

The running time of attacks hasn't suddenly become O(n^4.5). The latter figure describe the noise ratio for which the LWE assumption becomes broken in quantum polynomial time.

The proposed post-quantum encryption schemes use a much smaller noise ratio which (at the moment) is not affected by these attacks.

[da-bacon]

I didn’t say the runtime did I? The approximation ratio went from exponential to polynomial noise ratio. This just went from 2^n to n^4.5 and everyone seems to say “oh this is fine”.