Cryptographers Take On Quantum Computers
Researchers prepare for the day when quantum computers can easily crack today's codes
PHOTO: brandon palacio
Software updates, eâ¿¿mail, online banking, and the entire realm of public-key cryptography and digital signatures rely on just two cryptography schemes to keep them secure—RSA and elliptic-curve cryptography (ECC). They are exceedingly impractical for today’s computers to crack, but if a quantum computer is ever built—which some predict could happen as soon as 10 years from now—it would be powerful enough to break both codes. Cryptographers are starting to take the threat seriously, and last fall many of them gathered at the PQCrypto conference, in Cincinnati, to examine the alternatives.
Any replacement will have some big shoes to fill. RSA is used for most of our public-key cryptography systems, where a message is encoded with a publicly available key and must be decrypted with a mathematically related secret key. ECC is used primarily for digital signatures, which are meant to prove that a message was actually sent by the claimed sender. ”These two problems are like the two little legs on which the whole big body of digital signature and public-key cryptography stands,” says Johannes Buchmann, cochair of the conference and professor of computer science and mathematics at Technische Universität Darmstadt, in Germany.
The reason that quantum computers are such a threat to RSA and ECC is that such machines compute using quantum physics. Unlike a classical computer, in which a bit can represent either 1 or 0, in a quantum computer a bit can represent 1 or 0 or a mixture of the two at the same time, letting the computer perform many computations simultaneously. That would shorten the time needed to break a strong 1024-bit RSA code from billions of years to a matter of minutes, says Martin Novotný, assistant professor of electrical engineering at the Czech Technical University, in Prague.
But quantum computers don’t have an advantage over every type of cryptography scheme. Experts say there are four major candidates to replace RSA and ECC that would be immune to a quantum computer attack. One prominent possibility is an ECC digital-signature replacement known as a hash-based signature scheme. A hash function is an algorithm that transforms text into a relatively short string of bits, called the signature. Its security is based on being able to produce a unique signature for any given input. Even inputs that are only slightly different from one another should produce different hashes, says Buchmann.
Error-correcting codes are a potential replacement for public-key encryption, Buchmann says. Such a scheme would introduce errors into a message to make it unreadable. Only the intended receiver of the message would have the right code to correct the error and make the document readable.
Another potential type of public-key cryptography replacement is known as multivariate public-key cryptosystems (MPKC). To crack it, a machine must solve multivariable nonlinear equations. This type of cryptography is extremely efficient and much faster to produce than other schemes, such as RSA, which must use numbers hundreds of digits long to be secure, says Jintai Ding, mathematics professor at the University of Cincinnati and cochair of the cryptography conference. So MPKC could be particularly useful in certain applications like RFID chips. ”RFID chips and sensors have very limited computing power and memory capacity,” says Ding, whose specialty is MPKC. ”But they are also very important in practical applications, so they need to be secure,” he adds.
Cryptographers are also discussing a lattice-based system, where the lattice is a set of points in a many-dimensioned space. Possibly useful for both digital signatures and public-key cryptography, a lattice system would be cracked by finding the shortest distance between a given point in space and the lattice. Buchmann says lattice systems are promising but still need much more research.
For the time being, our cryptosystems are safe, yet both Ding and Buchmann caution that the need to develop alternatives is growing more urgent. As we build more-powerful classical computers, RSA and ECC must become more complex to compensate. In 10 or 20 years, we might need to base RSA on prime numbers thousands of digits long to keep our secrets. That’s long enough to bog down some computers and prompt a replacement, even if quantum computers turn out to be a dead end.