A couple of people are asking in the comments for further elaboration, so here we go:
When quantum computers factor numbers or compute discrete logarithms, the thing the quantum part of the algorithm solves is the Abelian Hidden Subgroup Problem. It's not super important what this is, other than the fact that "abelian" means commutative and is a very important qualifier.
Lattice cryptography on the other hand can be reduced to the Dihedral Hidden Subgroup Problem. (The Dihedral Coset Problem is a variation thereof). On the other other hand, lattice cryptography is, when it comes to cryptography, the closest to what we can consider complexity theoretically secure. There are hard case to average case reductions, randomized reductions to NP-hard, and in general lots of reductions to known hard problems.
So a quantum algorithm that promises to solve the dihedral hidden subgroup problem in polynomial time would as a first order effect destroy all lattice schemes in one go. (The reality is a bit more complex and it turns out some details do matter as to just how many lattices can be solved with a given algorithm, but any such algorithm would be a major blow and likely lead to further results). And given the complexity theoretical results on lattices, we would at least have some doubts as to whether public key encryption can exist at all. After all that isn't just an NP problem, it's a specific subset of NP problems and that subset could very well be empty.
Mastodon Feed
