Grid-based methods are currently raising great expectations in the development of cryptography that is secure from quantum computers. Mathematicians associate grids with a number of difficult tasks involving the measurement of vector spaces. The difficulty of these problems increases exponentially with the complexity of the grid. For cryptographic applications, grids with hundreds of dimensions are used.

One of the first to make mathematical grids usable for cryptography was the Hungarian-American computer scientist Miklós Ajtai, who worked at the IBM research centre in Almaden. In the mid-1990s, he opened the door to a new field of cryptography. Shortly after the turn of the millennium, grid cryptography was still the work of a small group of researchers, reports the Italian-American computer scientist Daniele Micciancio in a YouTube lecture. In the meantime, one has to read more than 100 essays a year to keep track of this rapidly expanding field of research.

Vadim Lyubashevsky is one of the researchers who have excelled here. He worked with Micciancio at the University of California in San Diego as a doctoral student. Today, he conducts research at the IBM research laboratory in Rüschlikon on the Lake Zurich, Switzerland.

The IBM researcher has done much to transform the lattice theory, which has been developed over the past 25 years, into computer software that is relevant to practice. According to Lyubashevsky, a so-called Cryptographic Suite for Algebraic Lattices (Crystals) is already being used internally by IBM, but also by Google and Cisco for testing purposes. It has been shown that these programs work very efficiently, they are faster than conventional cryptographic methods. Only the memory requirements are slightly higher because the keys are longer.

IBM has not only developed software, but also hardware: the prototype of a tape drive can store encrypted data on 20-TByte tape cartridges in a way that cannot be converted into plain text even by quantum computers.

However, such products cannot be commercialised as long as there are no binding standards for post-quantum cryptography that ensure the interaction of hardware and software components from different manufacturers. The computer world is therefore waiting for the American National Institute of Standards (Nist) to complete a long-term evaluation of quantum-safe cryptographic procedures. An important milestone has just been reached in this process: at the end of July, the American authority announced the end of the second round of evaluation.

When the Nist began to deal with quantum-secure cryptography in 2015, 82 proposals were available for selection. After two evaluation rounds, 7 algorithms remained, including several proposals from IBM. According to the latest Nist evaluation report, the grid-based proposals are considered the most promising. After a third round, which is expected to take 12 to 18 months, binding standards should finally be in place by the end of 2021.

In 1994, the American mathematician Peter Shor was able to show that quantum computers, which were still hypothetical at the time, could greatly accelerate the decomposition of prime factors. Thus, the security of asymmetric encryption is no longer guaranteed. New encryption methods have to be developed that can withstand the quantum computers: Post-quantum cryptography is needed.

It is not possible to wait until the new computers are ready for use and then solve the security problems they raise. For one thing, the development of cryptographic procedures takes time. On the other hand, data sometimes have a long life span. If their confidentiality has to be guaranteed for decades, it is essential to develop an idea today of what tools will be available to an attacker in ten or twenty years’ time. Moreover, it cannot be ruled out that malicious actors are already hoarding encrypted data today in order to read them in plain text later, when quantum computers become available.

The fact that the dangers that quantum computers pose to cryptography have been discussed for a long time, and that it may take a long time before these dangers become real, weakens the awareness of the problem in some places; this “long time and not for a long time” lends many people a false sense of security. But the task of dealing with post-quantum cryptography can no longer be put off any longer.

“The danger is acute,” says the introduction to a report published in April by the American consulting firm Rand Corp. “Quantum computers pose a threat to every government agency, all critical infrastructures and all branches of industry.” This is a new type of threat that is not comparable to conventional security problems. It is directed against the very foundations of the Internet. It threatens to be a “quantum disaster”, an author of the study told journalists. The German Federal Office for Information Security (BSI) also sees an “acute need for action” with regard to post-quantum cryptography.

A revolution is imminent: With the help of quantum mechanical effects, new types of computers could one day quickly solve computing tasks that today’s machines cannot cope with. That is good news. On the one hand. On the other hand, it is bad news. Because commercial computer science as we know it today depends on the existence of computing tasks that computers can cope with. The high computational effort forms a protective wall that secures communication channels. Quantum computers could tear down this protective wall.

Around Lake Zurich, researchers are involved in various teams for the development of post-quantum cryptography. The new encryption methods should protect secrets entrusted to the Internet for decades to come.

For centuries, and even in the late 1970s, it seemed inevitable that the sender and recipient of secret messages would use the same key. This form of protected message exchange is called symmetrical. Since then, asymmetric encryption methods have become generally accepted. They enable the secure exchange of information between two communication partners who are facing each other for the first time and have not had the opportunity to agree on a common key beforehand.

The asymmetric encryption methods use mathematical functions that can only be inverted with great effort. These are one-way or trapdoor functions: In one direction, the passage is easy to pass through, but the way back is blocked. A widely used encryption method is based on the multiplication of two large prime numbers. It does not demand much from a calculating machine, but the opposite way, the prime factorization, is too much for common computers.