A full-fledged quantum computer is still years, if not decades, away. But developers have long thought that its killer app will be decoding encrypted messages on the internet and elsewhere, be they state secrets or personal information. That prospect has galvanized cryptographers. At a meeting this week in Santa Barbara, California, they will discuss nearly two dozen schemes for encrypting messages in ways that even quantum computers cannot crack.
The workshop is part of a push by the National Institute of Standards and Technology (NIST) to set standards for so-called postquantum cryptography. The multiyear effort may sound premature and a bit paranoid, as such a quantum computer may never exist. But cryptographers say now is the time to prepare, especially because anybody could record sensitive communications now and decipher them later. “If you wait until we have a quantum computer it’s too late,” says Tanja Lange, a cryptographer at Eindhoven University of Technology in the Netherlands. “Every day that we don’t have postquantum cryptography is a day the data is leaked.”
Hundreds of billions of dollars of e-commerce relies on potentially vulnerable schemes called public key cryptography. They are based on “trap door” calculations, so called because they are much easier to work forward than backward. A receiver, Alice, provides a numerical public key and a recipe that a sender, Bob, uses to scramble a message. An eavesdropper, Eve, cannot easily reverse Bob’s computation to discover the message. However, Alice has also generated a secret private key, mathematically related to the public one, that helps her unscramble the message through computations like Bob’s.
For example, in a popular public key scheme called RSA, Bob scrambles a numerical message by multiplying it by itself a number of times that Alice specifies. He divides the result by the public key, a gigantic number produced by multiplying two prime numbers, and sends Alice the remainder. To reconstruct the message, Alice multiplies the remainder by itself a different number of times—that number is her private key—and divides by the public key. Voila! Bob’s original message pops out in the remainder. It’s as if Alice tells Bob how to obscure a padlock’s setting by turning the dial forward many turns, knowing how to turn the dial farther ahead to recover the original setting. Eve can only struggle to figure out how far to turn the dial back.
RSA also illustrates the threat posed by a quantum computer. If Eve could factor the public key into its component primes, she could steal the private key and crack the code. Factoring large numbers is hard for a classical computer, but would be easier for a quantum computer, as Peter Shor, a mathematician at the Massachusetts Institute of Technology in Cambridge, showed in 1994. A quantum computer running Shor’s algorithm could also defeat newer public key schemes because it excels at finding patterns in repeated divide-and-take-the-remainder operations.
To counter the risk, cryptographers are developing less vulnerable trap door algorithms. Many rely on geometric constructions called lattices, arrays of points that resemble the repeating 3D patterns of atoms in a crystal, except they have hundreds or thousands of dimensions. A lattice is defined by a set of arrows or vectors that can be added in different combinations to make the pattern. For the same lattice, the basis can consist of short, nearly perpendicular vectors that are easy to work with, or long, nearly parallel ones that are harder to handle.
In these schemes, Alice’s private key is a simple lattice basis and her public key is a messy one that defines the same pattern. To transfer each bit of information to Alice, Bob can send her the coordinates of a point in the many-dimensional space that is either close to a point in the lattice to denote zero or farther from a lattice point to denote one. With the messy public key, even a quantum computer couldn’t help Eve tell how close the point is to the lattice. Alice, however, can easily do so because she holds the simple, private key. “Lattice cryptography is a very active area because it’s so versatile,” says Nina Bindel, a computer scientist at the Technical University of Darmstadt in Germany.
Some researchers are dusting off much older algorithms. Suppose you want to transmit a string of bits over the internet but fear that a few zeroes and ones might inadvertently flip. You can guard against that by making a longer string with redundancies that can be used to correct the errors. Such an error-correcting code can be represented by a grid, or matrix, of zeroes and ones, and in the 1970s cryptographers showed they can encrypt messages.
In this type of scheme, Alice’s private key is an error-correcting matrix and her public key is a scrambled version of it. Bob’s message is the string of bits, to which he applies the public matrix to get a different string. He flips a few random bits for good measure and sends the result to Alice. Even knowing Bob’s messy matrix, Eve cannot undo his moves. But with the cleaner one—designed for correcting those flipped bits—Alice can. Error-correcting schemes have been tested more than lattices, Lange says, and can face down Eve even if she has a quantum computer.
Most postquantum algorithms require bigger keys or more computing time than current standards. But Simona Samardjiska, a cryptographer at Radboud University in Nijmegen, the Netherlands, and colleagues are developing a nimble small-key scheme, based on sets of quadratic equations, that could be better suited for digital signatures—the quick handshakes that authenticate websites—than for sending secret messages.
As with any public key system, there’s no proof the postquantum schemes are uncrackable, perhaps even with a conventional computer. So instead of replacing current algorithms, the new ones will likely run in combination with them, says Brian LaMacchia, a cryptographer with Microsoft in Redmond, Washington.
NIST could standardize two or three algorithms each for encryption and digital signatures as early as 2022, says Dustin Moody, a mathematician at NIST in Gaithersburg, Maryland. The agency wants options, he says. “If some new attack is found that breaks all lattices, we’ll still have something to fall back on.” NIST sets standards for the federal government, Moody says, but “much of the world uses the encryption that NIST standardizes.” Cloudflare, an internet security and performance company in San Francisco, California, which serves 20 million businesses and other customers, has already begun to experiment with some of the algorithms in web browsers. But a full migration will take years, cautions Nick Sullivan, an applied cryptographer at Cloudflare.
LaMacchia says that in the past 30 years he’s seen four or five major changes in cryptography, including the push a decade ago to move from RSA to a mathematically related but more secure successor. “This one is qualitatively different. It’s a lot more complicated.” Users of encryption—that is, nearly everyone—will know the change has gone well if they never notice it.
Source: Science Mag