Ruhr-Uni-Bochum
HGI

Post-Quantum Cryptography: CASA scientists successfully work on algorithms for the future

Most of the finalists in the NIST PQC standardizing process are members of CASA.

Post-Quantum Cryptography: CASA scientists successfully work on algorithms for the future. December 2020

Copyright: Roberto Schirdewahn

Whether online shopping, home banking or surfing the net: In our everyday lives, we use numerous digital services in which sensitive information is exchanged. They are all based on complex cryptographic processes that are designed to secure data exchange and thus protect it from unauthorized access. With current technical requirements, these encryptions and protocols are considered unbreakable. But with the development of quantum computers, this security could be threatened: Cyber attackers would have the capacity to crack standards used today and possibly disclose sensitive data.

Four of seven finalists with CASA participation

The answer to this problem is the further development of cryptographic algorithms and protocols, which is currently being driven forward by scientists of the Cluster of Excellence CASA. Their proposals are now in the final round of the process for standardization of post-quantum cryptography at the US National Institute of Standards and Technology (NIST). There are seven final submissions in total, four of which involve CASA Professors Daniel Bernstein, Tim Güneysu, Eike Kiltz and Tanja Lange as well as postdoctoral fellow Ming-Shing Chen. The standards certified by the authority are adopted by numerous companies in their technology, as they are considered extremely safe.

Eike Kiltz explains why cryptographers have to work today on algorithms for tomorrow: "If we send ourselves encrypted e-mails these days, they could be intercepted and stored by secret services or cybercriminals. They can't be decrypted with the current techniques. But with quantum computers, this could happen. Depending on the security relevance of the data, they could still be relevant years from now.

Data already encrypted by the Romans

Encrypting information is not a modern invention. Even in ancient times, Greeks and Romans used secret signs to pass on their messages in a secure way. The Enigma encryption machine, which was used by the Germans during the Second World War, has also become well known. It was considered secure but was cracked unnoticed by the British Alan Turing. Thus numerous German radio messages could be intercepted.

However, all this can no longer be compared with today's encryption methods in IT security. Through the use of powerful computers and complex mathematical methods, cryptographic procedures help to ensure that communication between sender and receiver is sent securely through the Internet. One of the established methods exploits a mathematical problem that has not yet been solved: "The RSA-based method is based on the fact that it is difficult to factorize large numbers," explains Eike Kiltz. "Prime numbers can be multiplied efficiently, but it is difficult to reverse the direction. For a small product, for example 35, it still works. Here, you can quickly find out by trial and error which prime numbers were used for the calculation: The product of the two prime numbers 7 and 5 is 35, but with large numbers, classical computers would need exponentially more time to try out all the prime factors". In mathematics, this is called a hard problem. "But quantum computers can solve precisely this problem very quickly," continues Kiltz.

Quantum computers are not one step ahead of classical computers in general. "They can actually only solve very specific types of problems. These include everything that has a kind of cyclic structure, such as the factorization problem and also the calculation of discrete logarithms," says the scientist.

Quantum computers can hardly be compared with classical computers

Quantum computers are conceived on the basis of quantum mechanics, one of the most complex physical theories of our time. Classical computers work with the states 1 and 0, i.e. the state "on" or "off". Quantum computers, on the other hand, do not work according to the laws of classical physics, but according to quantum physics. The "qubits" acting there can not only assume the states 1 or 0 but also both simultaneously and all states in between. This is one of the reasons why they are so efficient.

But this is still a dream of the future. Although Google has already made headlines with its so-called quantum superiority, the current processors are still far from functioning perfectly, explains Eike Kiltz. "In theory, we know everything about how quantum computers work. But the implementation is still an extremely challenging engineering problem. It is unclear whether it can ever be solved," the researcher continues.

Different approaches are important for safety

However, it is not only technical progress that could endanger the current encryption methods. "Of course, it could just as well be that tomorrow a talented doctoral student or postgraduate student suddenly solves the factorization problem with a conventional computer. It's all conceivable," says the scientist. This leads to the importance of developing many different approaches to encryption.

Eike Kiltz is therefore working on another method that he submitted to the competition together with other scientists: a grid-based method based on another hard problem in mathematics. The submission by Dan Bernstein and Tanja Lange, also members of CASA, on the other hand, is based on a problem of coding theory. Ming-Shing Chen is working on a procedure based on a difficult problem of so-called multivariate cryptography.

Within the Cluster of Excellence, they and other scientists in the Research Hub "Cryptography of the Future" are generally working on developing sustainable, secure solutions in the field of encryption. They analyze existing algorithms for their security and at the same time research advanced concepts such as quantum-resistant cryptography. Because, as is well known, the future lies directly ahead of us - so it is all the more important to always think one step ahead.

General note: In case of using gender-assigning attributes we include all those who consider themselves in this gender regardless of their own biological sex.