Quantum Algorithms for Lattice Problems

From the paper:

> Let us remark that the modulus-noise ratio achieved by our quantum algorithm is still too large to break the public-key encryption schemes based on (Ring)LWE used in practice. In particular, we have not broken the NIST PQC standardization candidates. For example, for CRYSTALS-Kyber [BDK+18], the error term is chosen from a small constant range, the modulus is q = 3329, the dimension is n = 256 · k where k ∈ {3, 4, 5}, so we can think of q as being almost linear in n. For our algorithm, if we set αq ∈ O(1), then our algorithm applies when q ∈ Ω^~(n^2), so we are not able to break CRYSTALS-Kyber yet. We leave the task of improving the approximation factor of our quantum algorithm to future work.

If the findings of this paper hold up, I believe it could pretty much undo a decade of NIST's efforts in post-quantum cryptography. a seismic shift in the world of cryptography.

Will be interesting to see how this pans out.

How does this affect these statements on Wikipedia [1]

> some lattice-based constructions appear to be resistant to attack by both classical and quantum computers. Furthermore, many lattice-based constructions are considered to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently.

and [2] ?

> One class of quantum resistant cryptographic algorithms is based on a concept called "learning with errors" introduced by Oded Regev in 2005.

[1] https://en.wikipedia.org/wiki/Lattice-based_cryptography

[2] https://en.wikipedia.org/wiki/Ring_learning_with_errors_key_...

Not entirely true, there are other PKE and DSA algorithms that were/are a part of the competition that used problems not related to lattices. However, the lattice-based options were often among the fastest and smallest.