Encryption—the process of sending a scrambled message that only the intended recipient’s device can decode—allows private and public sectors alike to safeguard information. Traditional encryption uses schemes based on complex mathematics such as factoring (breaking an integer down to its prime factors) or discrete logarithm. Classical computers would require billions of years to crack these codes. Quantum computers, however, won’t be stumped by such hard problems; their exponential leaps in processing power will render classical cyphers obsolete, potentially exposing troves of sensitive data across commercial entities, healthcare providers, government institutions, and billions of individual users.
Experts are working to devise cryptographic schemes that can run on today’s computers, but that can also be used in ciphers to protect data against quantum attackers.
Quantum computers can perform certain functions that ordinary computers simply can’t; in part, this is because qubits (the way information is encoded on quantum computers) adopt the properties of quantum mechanics, using individual atoms, ions, photons, or electrons to take on a combination of various states at once. This gives quantum computers—once little more than a laboratory curiosity—access to a larger space of values than conventional computers, with their binary 0’s and 1’s. Someday, quantum computers will be able to perform a vast number of calculations almost instantaneously, breaking the ciphers that protect personal data.
“We need to identify alternative problems we can use as the foundation for quantum-secure cryptosystems,” says Chris Peikert, professor of computer science and engineering at the University of Michigan. “What hard problem are we going to use? How do we use that problem to encrypt messages securely?”
Enter lattices. Abstract algebraic structures, lattices are enormous grids with many individual points across two, three, or potentially hundreds of dimensions. In a high enough dimension, for instance, a bounded-distance decoding problem—a type of lattice-based conundrum—should be able to flummox these machines (see sidebar). “The best algorithms we come up with still fail miserably,” says Peikert.
Lattices are infinitely large objects, but traditional computers only have a finite amount of memory to work with. So mathematicians need a succinct way to represent lattices if they’re to use them in cryptography: what’s called a lattice basis.
“IN SMALL DIMENSIONS, LATTICE PROBLEMS ARE EASY FOR EVEN ORDINARY COMPUTERS TO SOLVE. BUT AS THE DIMENSIONS GROW, THESE PROBLEMS QUICKLY APPEAR TO BECOME INTRACTABLE.”
A lattice basis is a finite collection of points that can be used to reproduce any point in the grid that forms the lattice. In two dimensions, any given point has two coordinates—an x and a y value. Lattices used to create ciphers, however, are orders of magnitude higher in dimension. Points in these lattices might have 10,000 coordinates, rather than two. In small dimensions, lattice problems are easy for even ordinary computers to solve. But as the dimensions grow, these problems quickly appear to become intractable.
This curse of dimensionality confuses both traditional and quantum computers, particularly when they are trying to decode a location that’s near—but not on—a lattice point.
Let’s say we plan to encrypt a single bit of data. Selecting a lattice point that corresponds to our data, we add a bit of random noise—that is, we slightly perturb the point, traveling a small distance so that we end up not on a lattice point, but close by, in the ambient space between lattice points; our target is no longer a lattice point. Where we’ve ended up becomes the ciphertext: the encrypted version of the data. In essence, bounded-distance decoding is the problem of recovering the original lattice point from this ciphertext.
Bounded-Distance Decoding, Visualized
“[This] figure depicts the bounded-distance decoding (BDD) problem on a two-dimensional lattice,” explains Chris Peikert (lattices used for encryption can have thousands of dimensions). The green points are some of the lattice points and the red point is the BDD “target.”
“To solve the BDD problem,” Peikert says, “the attacker must find the closest lattice point to any given target point.” In other words, decoding the lattice (being able to map all its points and crack the encryption, in this case) requires finding the bounded distance between the target point and the closest lattice point. Peikert adds: “If we place equal-sized blue discs centered at every lattice point, then the target [point] must be inside one of them. The goal is to identify the lattice point at the center of that disc.”
Next, we send our ciphertext to the recipient, who will only be able to decrypt it on their device with a secret key—some special information about the original lattice. Without this key, experts believe that neither quantum nor classical computers will be able to decode the target point back to the original lattice point. The lattice is thus an ideal mechanism to devise encryption schemes for both traditional computers and quantum machines.
With quantum computing on the horizon, long-term security is paramount. Companies like Google and Cloudflare have already started to deploy lattice-based cryptography within traditional internet protocols. Startups are banking on quantum technology to improve advances in finance, drug and materials discovery, data mining, and more. Unless cybersecurity can outpace the technology, however, quantum poses a risk for us all.
“Quantum computers will be able to retroactively break currently used codes, making them a threat not only to the future but to the past and present, as well,” says Peikert. “The reality is sobering.”