New Lattice Cryptanalytic Technique

2024-04-15 11:04

A new paper presents a polynomial-time quantum algorithm for solving certain hard lattice problems.

This could be a big deal for post-quantum cryptographic algorithms, since many of them base their security on hard lattice problems.

As this comment points out: "We had already some cases where efficient quantum algorithms for lattice problems were discovered, but they turned out not being correct or only worked for simple special cases."

Two, this is a quantum algorithm, which means that it has not been tested.

There is a wide gulf between quantum algorithms in theory and in practice.

Until we can actually code and test these algorithms, we should be suspicious of their speed and complexity claims.

News URL

https://www.schneier.com/blog/archives/2024/04/new-lattice-cryptanalytic-technique.html