Defusing Tomorrow’s Dangers Today
Berlin researchers headed by mathematician Marian Margraf study encryption methods that cannot be cracked even by future quantum computers.
Apr 15, 2019
The quest to ensure the utmost in digital security is a common thread running through Marian Margraf’s life.
These days, he is focusing on what many people view as the biggest threat to digital security to have emerged to date: quantum computers. Margraf, a mathematician, is well equipped for the task.
In his role as an employee of the German Federal Ministry of the Interior, he was responsible for introducing the online function of the German federal personal ID card, and he also worked as an encryption expert at the German Federal Office for Information Security. Now at Freie Universität Berlin, he holds a professorship endowed by the Bundesdruckerei, a position in which he has been dedicated to fighting dangers from the realm of atoms, electrons, and light particles since 2014.
Most people use encrypted Internet connections every day. You can tell when a connection is encrypted because the browser’s address bar shows “https.” Encryption is also used when writing e-mails, in online banking, and when making card payments.
The fact that an update really does come from the authentic sender, not from a malicious attacker, is guaranteed by a digital signature that uses the same cryptographic methods. Billions of these transactions are secured each and every day by “asymmetrical” encryption methods, so called because they work without partners having to exchange a secret code beforehand. That makes them ideal for Internet traffic, which spans the globe and is often impersonal.
But all that could collapse like a house of cards if there were someone who had a powerful quantum computer today. Little is known yet about what kinds of tasks these computers of the future will perform much faster than even the largest conventional supercomputers known today. But there is one mathematical problem researchers are already certain they will one day solve: breaking numbers down into prime factors.
For small numbers like 15 or 21, that’s easy enough to do in your head: The prime factors of 15 are 3 and 5, and those of 21 are 7 and 3. There is no formula for this. You just figure it out, in these simple cases. But what if you want to find the prime factors for a number that runs to hundreds of decimal places? There are algorithms that can accomplish that faster than a person could by simply trying out possibilities, but even so, it would still take a conventional computer billions of years to come up with a solution. The practical insolubility of this problem serves as the basis for the asymmetric encryption method.
For a quantum computer, though, the “factorization problem,” as it is called, is quite easy to solve. The laws of quantum physics allow tiny particles like atoms or electrons to take on two states at once, rotating both counterclockwise and clockwise simultaneously, for example. Experts call the basic unit of quantum information a “quantum bit,” or “qubit,” as opposed to the “bit” used in a conventional computer, which can only store 0’s and 1’s in sequence.
A quantum computer with thousands of qubits could possess vast numbers of states simultaneously, using all of them to perform computations. That’s why it could factorize a large number in just minutes, thereby cracking asymmetrical encryption. Experts believe this kind of computer will exist in ten to 15 years.
“We have to get ready now,” Margraf warns. There are mathematical problems that will be just as hard for a quantum computer to solve as they are for traditional computers. Cryptographers are working now to develop methods that use these problems for encryption. But it will take some time before this “post-quantum cryptography” is ready to use and has been standardized.
As a result, the quantum future is already here, in a way. The asymmetrical encryption methods that are standard today will still be built into software and hardware for years to come. Because these products will last a long time, they may still be in use well after quantum computers have been developed. Margraf says, “Things could get sticky in terms of security at that point. So we need to design products in such a way today that the encryption method can be replaced easily, at the point of use.”
This “crypto-agility” is essential, he says. Margraf believes programmers should be trained accordingly now, not later. “We are helping the industry deploy quantum computer-resistant methods early on,” says Margraf, who also serves as the head of the Secure System Engineering unit at the Fraunhofer Institute for Applied and Integrated Security in Berlin in addition to his work as a professor at Freie Universität Berlin. He points out that secure signature methods that “only have to be installed” already exist.
The threat concerns not just hardware and software, but also data that are collected today, but are supposed to be stored securely for a long time. As examples, Margraf points to health data and classified government documents from diplomatic or military circles. The U.S. National Security Agency (NSA), for example, stores vast amounts of data that it could decrypt retroactively ten or 15 years from now, Margraf warns. He believes the development of quantum computer-resistant encryption methods is an urgent matter.
Not every alternative encryption method that does not rely on the factorization problem is automatically secure against a quantum computer. Nor can it automatically be assumed to withstand an attack from a traditional computer. That’s where the Berlin research team comes in. “We’re trying out new cryptographic methods by studying how they could be attacked,” he explains.
But we shouldn’t imagine that Margraf’s associates are sitting in front of their computers like hackers, trying to crack an encryption method by hook or by crook. Instead, the researchers in Berlin are performing mathematical analyses. Are there algorithms that undermine the method?
Even quantum computers don’t just guess blindly at prime factors, Margraf says. Instead, they use an algorithm developed by Peter Shor, an American mathematician, more than 20 years ago. Another research question is if this kind of decryption method exists, how much time does it take to run? Would it take a supercomputer years to execute it, or could even a smartphone do it in minutes?
Searching for attacks like these is a tough task, but that isn’t all. “We also have to be very creative,” says Margraf. After all, hackers are inventive. In most cases, the new method is assumed to be secure. The more attacks thought up by researchers like Margraf that the new method has withstood, the more reliable that assumption is.
“Of course, it’s better if we can prove a method’s security,” the researcher says. The team of researchers in Berlin try to achieve that with mathematical methods. Margraf’s team has been working on quantum computer-resistant cryptology for about a year now.
“We have to focus more on quantum computers,” he says with conviction. With that in mind, the researchers have applied for several grants from the German Federal Ministry of Education and Research. The body that endowed his professorship at Freie Universität Berlin, the Bundesdruckerei, gives him complete freedom to choose his research subjects, Margraf says. In quantum computers, he has chosen one of the most highly charged.