Cryptographic methods are typically created following the ad-hoc principle: somebody comes up with an algorithm; others attempt to break it — if they don’t succeed, it means that the algorithm is secure. The team headed by Prof. Dr. Eike Kiltz, who holds the Chair for Cryptography at the Ruhr-Universität Bochum, opted for a different approach. They based their security algorithms on hard mathematical problems.
“If somebody succeeded in breaking those algorithms, he would be able to solve a mathematical problem that the greatest minds in the world have been poring over for 100 or 200 years,” compares Kiltz. The mathematicians make the algorithms so efficient that they can be implemented into microdevices, such as electric garage openers.
The algorithms are based, for example, on the hardness of the following lattice problem: imagine a lattice to have a zero point in one specific location. The challenge is to find the point where two lattice lines intersect and that is closest to zero point. In a lattice with approximately 500 dimensions, it is impossible to solve this problem efficiently.
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 even in small devices.
Lattice-based authentication algorithms developed by the team are fairly advanced.
“We are about to finalize them,” says Eike Kiltz.
Authentication protocols are necessary whenever an object has to prove its identity; for example, an electric garage opener at the respective door. This is how it could work in the protocol: the opener authenticates itself at the garage door by proving that it knows an internal secret, for example an intersection point close to the zero point in the lattice.
Kiltz’s group is currently also researching lattice-based encryption methods. They are necessary if two parties wish to exchange a secret message.
A detailed article including an interview with Eike Kiltz can be found in Ruhr-Universität Bochum’s science journal Rubin
