Efficient algorithms Hard mathematical problems as basis for new cryptographic techniques

For many people, their holidays start with a challenge: how is all that stuff supposed to fit into the suitcase, bag or rucksack? From the mathematical point of view, it is anything but trivial to find an algorithm for packing a rucksack in such a manner that, taken together, the items inside offer optimal benefit.

“The decision to bring a toothbrush is certainly an easy one,” says Prof Dr Eike Kiltz from the Chair for Cryptography. “It is small and offers great benefit. But what about the hairdryer? Do I bring that, too?”

The rucksack problem – since more than 100 years unsolved

The rucksack example is based on a hard mathematical problem. Researchers have been attempting to find an efficient solution for it for over one hundred years. However, in their variant of the problem, the rucksack would be much larger than in real life.

This is precisely the kind of hard mathematical problem that Eike Kiltz studies. He has developed new encryption and authentication algorithms that are virtually unbreakable. “If somebody succeeded in breaking those algorithms, he would be able to solve a mathematical problem that the greatest mathematical minds have been poring over for 100 or 200 years,” compares Kiltz.

Based on this notion, the researcher has opted for an unconventional approach. New cryptographic algorithms are typically created following the ad-hoc principle. Kiltz explains: “Somebody comes up with an algorithm, and others then attempt to break it. If they don’t succeed, it means that it is secure.”

The mathematicians from Bochum rather base their security algorithms on problems which have remained unsolved for more than one hundred years. The algorithms prove to be so efficient that they can be implemented in microdevices, such as electric garage door openers. “This was thought to be impossible, because the chips in those devices are not powerful enough,” says Kiltz. However, his group released a prototype algorithm in 2011 boasting that precise capacity.

Efficient algorithms for small devices

Now, the researchers are striving to render the algorithms more efficient and usable in cryptographic applications. A promising approach is lattice-based cryptography. It is rooted in the following hard mathematical problem. Imagine a lattice to have a zero point. Other points lie at the intersections of two lines, to which we refer as intersection points. Question: which intersection point is closest to zero point?

In a two-dimensional lattice, the problem can be easily solved; in a three-dimensional lattice, we can also identify the solution with relative ease. But the more dimensions are added, the more difficult the task becomes. With approx. 500 dimensions, the problem can no longer be efficiently solved.

Depending on which parameters are selected, the lattice problem will be categorised as a so-called NP-hard problem. This category describes the hardest problems in mathematics, which also includes the rucksack problem delineated above, as well as many others. They would constitute the ideal basis for new cryptographic techniques, ensuring the utmost in security.

For their project, the mathematicians chose a slightly simplified version of the lattice problem. The task is not finding the intersection point in the lattice that is closest to zero point, but rather finding a random intersection point that is within a close radius of zero point.

The researchers test various parameters that render the lattice problem simpler or harder, and use it as basis for developing a cryptographic algorithm which could be implemented in small devices.

Almost in the final stage

As far as lattice-based authentication processes are concerned, the methods developed by the RUB researchers are fairly advanced. “We have almost reached the final stage,” concludes Eike Kiltz.

Authentication protocols are required whenever an object has to verify its identity, for example an electric garage door opener. This is because it is necessary to ensure that one specific opener unlocks the door to which it belongs. In the protocol, it might work like that: the opener authenticates itself at the garage door by proving that it knows an internal secret, for example an intersection point close to zero point in the lattice.

Authentication is not the only field where cryptographic protocols are required; encryptions are used in everyday applications all the time. If, for example, two people wish to exchange a secret message via the Internet, or if a Smartcard wants to communicate with a card reader, the message has to be encrypted to prevent third parties reading it.

Lattice-based processes highly versatile

This is an area of application where lattice-based processes might likewise be of use. However, the encryption protocols based thereon are not yet efficient enough to be implemented in small devices. Researchers will have to invest another few years to optimise them, as Eike Kiltz estimates.

Because of their outstanding versatility, the mathematician compares lattice-based algorithm to a virtual Swiss Army knife. They can be used for encryption as well as for authentication, run on small devices, and would even offer protection from quantum computer attacks, should they exist one day.

In addition to conducting application-oriented projects, the RUB mathematicians also carry out basic research. They attempt to understand lattices in mathematical terms. “What, exactly, renders the lattice problem so uniquely difficult that all techniques applied to solve it have failed?” is one of the questions that the researchers investigate. Their findings might one day be implemented into their application-oriented projects.