Oddbean new post about | logout
 Well, that's not entirely true. There is such a thing as a type of cryptography that is resistant to attack with quantum computers. It's just, what's the best way to do that? It's just math.

Well, we know what sorts of math we use for encryption now, primarily all cryptography is based on the prime factorization problem, and we know that an algorithm, Shor's algorithm, can do that in less than exponential time on a quantum computer. We know what class of problems that is, and we know that any algorithm that can solve a problem in that class can be modified to solve all problems in that class and then more. So we know what classes of problems cannot be solved using a solution to one of those, and we know enough about the math with quantum computers and those problems that we can say probably some set of math problems cannot be solved efficiently on a quantum computer. So we pick those math problems, develop cryptography based on them and test it out.

Some more information to help you understand it:

https://en.m.wikipedia.org/wiki/NP-completeness

https://en.m.wikipedia.org/wiki/Computational_complexity_theory