Lattice-based cryptography is said to be the main contender for a post-quantum cryptography framework. It's thought that instead of having to switch everything over to QKD, post-quantum algorithms can instead be used that use a harder problem to solve than the typical RSA.

But is there any general understanding why lattice-based cryptography is actually a hard problem for quantum computers? An answer from the cryptography stack exchange suggests that this is simply because an algorithm hasn't been developed for it yet. This hardly seems like reassurance. Of course a new problem will take time for people to develop a quantum algorithm for.

Is there something about the lattice based method that makes it less susceptible to quantum computers? For example, I believe parallelization to often be a important factor to a problem being speedy on a quantum computer. Perhaps lattice-based methods are less parallelizable?

  • 2
    $\begingroup$ A solution to the Hidden Subgroup Problem for dihedral groups would crack many lattice-based crypto systems, so another question is why could the HSP for dihedral groups not be in BQP while for abelian groups it most certainly is. I think it has something to do with characters of irreps being too close to each other... <mumble mumble don't understand> $\endgroup$ Apr 15, 2022 at 1:02


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.