Exploring Post-Quantum Cryptography

Cryptographers are professionally paranoid, so they want their encryption systems to be resistant to attacks by exotic machines that do not exist yet: quantum computers.

By the most optimistic estimate, quantum physicists might be able to build a functional prototype in 10 years. If that happens, the security of the Internet will be destroyed, because each secure connection needs to start with either the Diffie-Hellman protocol or another public-key encryption system, RSA, both of which can be broken by a quantum computer. If that initial part is broken, security goes down the drain.

Safety From Eavesdroppers

RSA or Diffie-Hellman is used each time your browser surfs to an https web site (showing the little lock before the address). The browser and the Website engage in a 'handshake' by which they agree on a shared, secret key for encrypting all the data that will go back and forth. Remarkably, in the Diffie-Hellman protocol, neither side needs to send the actual key to the other side, so it is safe from eavesdroppers.

At the root of every modern encryption scheme is a mathematical problem that is extremely hard to solve (for a classical, non-quantum computer). For Diffie-Hellman, this is the so-called discrete logarithm problem, basically the problem of finding a number R if you know g and only the N last digits of the huge number g^R (for a sufficient level of security, N needs to be very large, and R needs to be at least a few hundred bits). Ironically, this is one of the few mathematical problems for which an algorithm is known, Shor's algorithm, which is exponentially faster on a quantum computer than on a classical computer.   

There is no need to panic; other encryption systems exist for which there is no known quantum attack. In 2015, cryptographers Erdem Alkin, Leo Ducas, Thomas Pöppelmann and Peter Schwabe published their system for post-quantum key exchange, New Hope, which uses an entirely different mathematical structure, Ring Learning With Errors (RLWE). It is unusual in the sense that it deliberately mixes noise—carefully tailored error terms—with the data that go back and forth during the 'handshake.' Each side then employs a clever trick to get rid of the other side's errors, and thus agree on the secret key.

RLWE was proposed some years ago by others, but these four cryptographers made several improvements to the protocol. Explained Schwabe, of Radboud University in the Netherlands, "We demonstrated how this system can be practically applied."

In the original RLWE, a certain number, A, had to be chosen once for all users. Then, Schwabe said, "When you walk into a room full of cryptographers, they will all say, 'How are you going to choose an A so that everybody can believe there's no backdoor?' " 

Closing Backdoors

Backdoors are an infamous weakness in encryption systems. A system may work fine for almost every key and system parameter, but sometimes special key numbers or parameter values exist for which cracking the encryption is easy, creating a backdoor into the system.

Schwabe and his colleagues addressed this concern by modifying RLWE in such a way that New Hope can choose a new, random 256-bit A every time the browser makes contact with an https website.    

Other improvements to RLWE are a more convenient way of adding errors to the data, and carefully fine-tuning some system parameters, making New Hope a lot faster without compromising security.

Co-author Leo Ducas of Centrum Wiskunde & Informatica (CWI) in Amsterdam said, "The possibility of building a quantum computer is by no means an established fact yet, but considering the enormous amount of infrastructure that depends on cryptography, even the slightest chance that this will happen warrants taking countermeasures now."

First Prize

Some very large data-driven companies have taken notice of this development.

When the researchers presented New Hope at the USENIX Security conference in Texas, in June 2016, they were awarded the $100,000 Internet Defense Prize sponsored by Facebook.

By July, software engineers at Google announced they would implement New Hope alongside Diffie-Hellman to secure part of the traffic between Chrome browsers and Google servers. Using a double handshake protocol will about double the time it takes to establish a secure connection, but this hardly matters, as this still takes less than a second.

Tanja Lange, a professor of cryptography at Eindhoven Technical University in the Netherlands, said, "I think Google's move is very timely: they are checking the practicality of New Hope for today's networks. There are good chances that the large parameters of New Hope hold up also against quantum computers." 

Lange was not personally involved in New Hope, but she chairs the EU-funded project PQCRYPTO that co-funded its development. PQCRYPTO explores options for post-quantum cryptography, and has already made recommendations for best practices. New Hope is not the only candidate for post-quantum key exchange, said Lange; "I think it's too early to fix one candidate, and I don't want to speculate on what systems will win. RLWE in particular needs more research so that people get more comfortable with the security assumptions."

PQCRYPTO tries to make financial and government institutions aware of the impending quantum revolution. Are they sufficiently worried? Said Lange, "Not yet, but we're working on it, and by now companies come to contact us. Silicon Valley got very nervous about quantum computers a few months ago. I don't see healthcare providers or lawyers coming to us, yet."   

Added Schwabe, "Big security agencies, in the U.S. and probably in China and Russia as well, are already archiving encrypted messages, even though they cannot be cracked yet. If, in 30 years, quantum computers exist, they will break these codes and look back. Human rights activists in China should already be worrying about that."

Arnout Jaspers is a freelance science writer based in Leiden, the Netherlands.