> "what is the definition of post quantum" where a lot of people call 1995 or so after Shor "PQ" I use the term quantum-resistant, which I think is more clear:

> "what is the definition of post quantum" where a lot of people call 1995 or so after Shor "PQ" I use the term quantum-resistant, which I think is more clear: crypto for which Grover's algorithm or Shor's algorithm cannot efficiently break it. > The algo in your linked paper is very convenient. However its newer and not as seasoned Totally agree, but it does show that you shouldn't just assume quantum-resistant crypto is necessarily computationally expensive. > I'd like to see a proof that there exists no possible theoretical quantum speedup against LWE. Don't hold your breath :). We don't even have a proof that integer factoring can't be broken in polynomial time in classical computers. We don't even know if one can make public key crypto unbreakable to classical computers (equivalent to P vs. NP problem). And the relationship of BQP (problems solvable in polynomial time on a quantum computer) to P and NP is still an open problem. It could turn out BQP=P, and quantum computers don't even give an asymptotic speedup over classical computers (I don't think that's likely, but it hasn't been proven one way or the other).