Published on October 8th, 2019 📆 | 2171 Views ⚑0
New Encryption System Protects Data from Quantum Computers
Once quantum computers become functional, experts warn, they could perform calculations exponentially faster than classical computers—potentially enabling them to destroy the encryption that currently protects our data, from online banking records to personal documents on hard drives. That’s why the National Institute of Standards and Technology is already pushing researchers to look ahead to this “postquantum” era. Most recently, IBM successfully demonstrated a quantum-proof encryption method it developed.
To send secure messages online or encrypt the files on a computer, most modern systems employ asymmetric, or public-key, cryptography. With this technique, data are encoded with a so-called public key, which is accessible to all; decoding that information requires a private key that only one party knows. Although both parts of this system are called “keys,” the public key is more like a slotted lockbox: anyone can drop something in, or encode a secret message, but only the private key’s holder can unlock the box, or decrypt the message. This arrangement makes such asymmetric cryptography more secure than a symmetric system—one that is more like an unlocked lockbox (security depends on keeping the box hidden, because a person who can get to it to drop in a message can also access its contents). Think of symmetric cryptography as a more complex version of a substitution cipher: if the message is encoded by shifting each letter of the alphabet ahead by three places, one can crack the code by simply shifting each letter back by three. That ability means anyone who knows how to put the code in place can also reverse engineer it. In contrast, public-key cryptography uses a mathematical algorithm to generate much more complex keys so the code cannot be run backward in this way. Different public-key systems can utilize different algorithms, as long as they are based on mathematical problems that are easy to put into place but hard to reverse engineer. For instance, any computer can multiply two extremely large prime numbers together, yet factoring the result is nearly impossible—at least, it would be for a classical machine.
“There are a lot of problems that cryptography is based on right now that, actually, we don’t think can be solved by normal computers,” says Vadim Lyubashevsky, a quantum-safe cryptography researcher at IBM Research–Zurich. But many of these encryption algorithms (including those that rely on multiplying two large prime numbers together) were originally developed decades ago, before researchers had developed quantum algorithms that could outperform classical ones. “As it so happens, [quantum computers] can solve the sort of these cryptographic problems upon which we built our cryptography in the 1980s exponentially faster than classical computers,” Lyubashevsky says.
There are, however, still equations that quantum algorithms have not yet managed to solve. “People have kind of assumed that quantum computers are a generalized speedup of conventional computers—that they somehow can do everything a conventional computer can do but much faster. And that’s not actually true,” says Alan Woodward, a professor of computer science at the University of Surrey in England, who is not involved in IBM’s research. “There is quite a limited set—four types of algorithms we know so far—[that] they can do faster than conventional computers.” Unfortunately, though, this limited set is still enough to threaten the current encryption infrastructure to some degree. In particular, a quantum technique called Shor’s algorithm can factor large numbers exponentially faster than classical machines. That ability means a quantum computer could crack systems like RSA, a widely used method for encrypting data.
Rather than waiting for a quantum computer to perform this feat (which may not happen for another decade or longer), teams of researchers, including Lyubashevsky and his colleagues, are scrambling to find new encryption methods that quantum computers cannot manipulate, based on more secure equations. “The working assumption is that if you can find one of these mathematical problems that are easy to do one way but difficult to do the other way—and it’s not solvable as part of the hidden subgroup problem—then it should be capable of withstanding attack by quantum computers,” Woodward says. A “hidden subgroup problem” describes a category that includes the problem of breaking numbers down to their prime factors. “While quantum computers can do some things better against a particular set of problems, there are tons of other things they just do not help with—almost at all,” Lyubashevsky says. “So these are the types of problems that people are trying to build cryptography on.”
Because there are many of these types of problems, organizations such as NIST are trying to narrow down the potential options in order to develop a standardized method for quantum-proof encryption. In 2016 NIST put out a call for potential postquantum algorithms, and earlier this year it announced it had winnowed 69 accepted submissions down to 26 leading candidates. The plan is to select the final algorithms in the next couple of years and to make them available in draft form by 2024. IBM is not waiting for the results of this competition, however. In August the company announced its researchers had used its NIST submission, a system dubbed CRYSTALS (short for Cryptographic Suite for Algebraic Lattices) to successfully encrypt a magnetic-tape storage drive.
CRYSTALS generates its public and private keys with a category of equations called “lattice problems.” Although researchers have studied these equations since the 1980s, they have not developed either classical or quantum algorithms capable of defeating them. According to Lyubashevsky, one simple example of such a problem is to add three out of a set of five numbers together, give the sum to a friend and then ask that second party to determine which three numbers were added. “Of course, with five numbers, it’s not hard,” Lyubashevsky says. “But now imagine 1,000 numbers with 1,000 digits each, and I pick 500 of these numbers.”
IBM submitted CRYSTALS to the NIST contest in 2017. Yet it was not until this summer that the company announced it had used the method in a practical application by encrypting the data on a prototype storage drive. Although NIST may not ultimately select CRYSTALS as its new standardized cryptography technique, IBM still hopes to use the system for its own products. Its summer announcement, presented at the Second PQC Standardization Conference at the University of California, Santa Barbara, also included the news of a CRYSTALS modification that should let it encrypt cloud-based data. IBM hopes to use this improvement to render the IBM Cloud quantum-proof by 2020.
Because IBM has also made the system open-source, Lyubashevsky points out, any people interested in protecting their data can try it. “If they really do need their data to be secure 20 years from now, there really are some good options available for the cryptography that they can use,” he says.