What kind of lock could a quantum computer not pick?

A lock that a quantum computer could not pick has to rest on a different kind of problem. Most widely used public-key algorithms rely on integer factorization, the discrete logarithm or the elliptic-curve discrete logarithm, and a sufficiently powerful quantum computer running Shor's algorithm could easily solve all three. Post-quantum cryptography replaces them with algorithms that are currently thought, but not proven, to be secure against a quantum attack.

One leading approach is lattice-based cryptography. Some lattice constructions appear to resist both classical and quantum computers. One of the main ideas is learning with errors: representing a secret as a set of equations with errors, so that the noise hides the value of the secret. In 2005 Oded Regev showed that this problem is as hard to solve as several worst-case lattice problems. In August 2024 the US standards agency NIST released its first three post-quantum standards, and the main one for general encryption, FIPS 203, is based on a lattice algorithm called CRYSTALS-Kyber, now named ML-KEM.

The word to underline is thought. In July 2022 Castryck and Decru published an attack that broke a post-quantum candidate called SIKE: on a single-core computer, its smallest version fell in about an hour. Nobody has a machine that breaks today's cryptography yet, but migrating takes so long that cryptographers are already preparing for the day current algorithms become vulnerable, and rumoured harvest now, decrypt later programs mean data recorded today may still be sensitive many years from now.