A Tricky Path to Quantum-Safe Encryption

It is now clear that current Internet security measures and the cryptography behind them will not withstand the new computational capabilities that quantum computers will bring.

Quantum computers, once seen as a remote theoretical possibility, are now widely expected to work within five to 30 years. By exploiting the probabilistic rules of quantum physics, the devices could decrypt most of the world’s “secure” data, from NSA secrets to bank records to email passwords. Aware of this looming threat, cryptographers have been racing to develop “quantum-resistant” schemes efficient enough for widespread use.

The most promising schemes are believed to be those based on the mathematics of lattices — multidimensional, repeating grids of points. These schemes depend on how hard it is to find information that is hidden in a lattice with hundreds of spatial dimensions, unless you know the secret route.

[Interest in quamtum computing surged] in 1994 when Shor, who is now at MIT, devised a quantum computer algorithm capable of efficiently computing both prime factors and discrete logarithms, and thus of breaking both RSA encryption and the Diffie-Hellman key exchange.""

As for why extreme efficiency and perfect security appear to be so diametrically opposed, Hoffstein said: “The universe is an irritating place, and this is just another example of it.”