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

In 1994, the computer scientist Peter Shor discovered that if quantum computers were ever invented, they would decimate much of the infrastructure used to protect information shared online. That frightening possibility has had researchers scrambling to produce new, “post-quantum” encryption schemes, to save as much information as they could from falling into the hands of quantum hackers.

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.

What Shor revealed in his 1994 algorithm was that a quirk of factoring makes it vulnerable to attack by quantum computers. “It’s a very specific, special thing that the quantum computer can do,” said Katherine Stange, a mathematician at the University of Colorado, Boulder. So after Shor, cryptographers had a new job: Find a novel set of mathematical operations that are easy to do but nearly impossible to undo.

Lattice cryptography is one of the most successful attempts so far. Originally developed in the 1990s, it relies on the difficulty of reverse-engineering sums of points.

Here’s one way to describe lattice cryptography: Imagine your friend has a lattice, which is just a bunch of points in a regular, repeating pattern all over the plane. Your friend wants you to name 10 of these points. But he’s being difficult, and he won’t draw the whole lattice. Instead, he lists just two points — the first with an x-value of 101 and a y-value of 19, the other with coordinates [235, 44].

Luckily, it’s easy to find new points on a lattice, because when you add and subtract any two points on a lattice, you get a third point in the same lattice. So all you have to do is add up the points your friend gave you, or multiply them by integers and then add them up, or some combination of the two. Do this eight different ways, and you’ll be able to answer your friend’s question.

But your friend still isn’t satisfied. He gives you the same two starting points, and then asks you if you can find a point near [0, 0] on the same lattice.  To answer this question correctly, you have to find the combination of [101, 19] and [235, 44] that gets you close to [0, 0]. This problem is much harder than the first one, and you’ll probably end up just guessing and checking to get the answer. That asymmetry is what underlies lattice cryptography.

If you actually want to use lattice cryptography to share information, you’d do the following. Imagine that a friend (a nicer one!) wants to send you a secure message. You start with a square grid of numbers. Say it has two rows and two columns, and looks like this:

Now you come up with a private “key” that only you know. In this example, let’s say your private key is just two secret numbers: 3 and −2. You multiply the numbers in the first column by 3, and the ones in the second column by −2. Add up the results in each row to get a third column with two entries.

Stick the new column onto the end of your grid. This new three-column grid is your public key. Share it freely!

(A real-world scenario will be a bit more complicated. To keep hackers from decoding your private key, you have to add a bit of random noise into your final column. But here we’re going to ignore that step for simplicity’s sake.)

Now your friend will use the public key to send you a message. She thinks of two secret numbers of her own: 2 and 0. She multiplies the numbers in the first row by 2, and the ones in the second row by 0. She then adds up the results in each column to get a third row.

She now attaches the new row to the bottom of the grid and sends it back to you. (Again, in a real system, she’d need to add some noise to her row.)

Now you’ll read the message. To do this, you check to see if your friend’s last row is correct. Apply your own private key to the first two entries of her row. The result should match the last entry.

Your friend can also choose to send you a row with a wrong number in the last column. She knows that this number won’t match your calculations.

If your friend sends a row where the last number is correct, you’ll interpret this as a 0. If she sends a row where the number is incorrect, you’ll interpret it as a 1. The row, therefore, encodes a single bit: either 0 or 1.

Note that an outside attacker won’t have access to either your private key or your friend’s. Without those, the attacker will have no idea if the final number is correct or not.

In practice, you’d like to send messages that are longer than one bit long. So people who want to receive, say, a 100-bit message will generate 100 new columns instead of just one. Then the sender of the message will create a single new row, modifying the last 100 entries to encode either a 0 or a 1 for each entry.

If lattice cryptography is actually implemented, it will have countless nuances not covered in this scenario. For instance, if you want the message to be truly safe from prying eyes, the matrix needs to have an unthinkable number of entries, making the whole thing so unwieldy that it’s not worth using. To get around this, researchers use matrices with useful symmetries that can cut down on the number of parameters. Beyond that, there is a whole suite of tweaks that can be applied to the problem itself, to the way errors are incorporated, and more.

Of course, it’s always possible that someone will find a fatal flaw in lattice cryptography, just as Shor did for factoring. There’s no assurance that a particular cryptographic scheme will work in the face of any possible attack. 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. To Stange, the entire project creates an uncomfortable paradox: “What I find so amazing about cryptography is that we’ve built this infrastructure for the human race on the firm belief that our ability as humans is limited,” she said. “It’s so backward.”

Correction: November 9, 2022
The original version of this article said that the hard problem to solve in lattice cryptography is finding a given point on the lattice near the origin. In fact, finding a particular point is relatively straightforward. The hard problem is finding some unknown point that lies near the origin. The article has been changed to reflect this fact.