‘Cryptography’s Future Will Be Quantum-Safe. Here’s How’

Fearing the possibility of encryption-cracking quantum computers, Quanta magazine reports that researchers are “scrambling to produce new,’post-quantum’ encryption scheme.” Earlier this year, the National Institute of Standards and Technology revealed four finalists in its search for a post-quantum cryptography standard. Three of them use “lattice cryptography” — a scheme inspired by lattices, regular arrangements of dots in space.

Lattice cryptography and other post-quantum possibilities differ from current standards in crucial ways. But they all rely on mathematical asymmetry. The security of many current cryptography systems is based on multiplication and factoring: Any computer can quickly multiply two numbers, but it could take centuries to factor a cryptographically large number into its prime constituents. That asymmetry makes secrets easy to encode but hard to decode…. A quirk of factoring makes it vulnerable to attack by quantum computers…. Originally developed in the 1990s, [lattice cryptography] relies on the difficulty of reverse-engineering sums of points…

Of course, it’s always possible that someone will find a fatal flaw in lattice cryptography… Cryptography works until it’s cracked. Indeed, earlier this summer one promising post-quantum cryptography scheme was cracked using not a quantum computer, but an ordinary laptop.

At a recent panel discussion on post-quantum cryptography, Adi Shamir (the S in RSA), expressed concern that NIST’s proposed solutions are predominantly based on lattice cryptography. “In some sense, we are putting all eggs in the same basket, but that is the best we have….

“The best advice for young researchers is to stay away from lattice-based post-quantum crypto,” Shamir added. “What we really lack are entirely different ideas which will turn out to be secure. So any great idea for a new basis for public-key cryptography which is not using lattices will be greatly appreciated.”