Hard mathematical problems as basis for new cryptographic techniques

April 1, 2016, Ruhr-Universitaet-Bochum

RUB researchers develop new cryptographic algorithms that are based on particularly hard mathematical problems. They would be virtually unbreakable.

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 base 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.

Lattice problem: finding the optimal difficulty level

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 approx. 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 which could be implemented even in small devices.

Authentication protocols almost finalised

Lattice-based authentication algorithms developed by the team are fairly advanced. "We are about to finalise 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 into -based encryption methods. They are necessary if two parties wish to exchange a secret message. The Ruhr-Universität Bochum's science journal Rubin reports about the mathematicians' work.

Explore further: New algorithm shakes up cryptography

Related Stories

New algorithm shakes up cryptography

May 16, 2014

Researchers at the Laboratoire Lorrain de Recherches en Informatique et ses Applications (CNRS/Université de Lorraine/Inria) and the Laboratoire d'Informatique de Paris 6 (CNRS/UPMC) have solved one aspect of the discrete ...

Surfing over simulated ripples in graphene

September 18, 2015

The single-carbon-atom-thick material, graphene, featuring ripples is not easy to understand. Instead of creating such ripples physically, physicists investigating this kind of unusually shaped material rely on a quantum ...

Recommended for you

1 in 3 Michigan workers tested opened fake 'phishing' email

March 16, 2018

Michigan auditors who conducted a fake "phishing" attack on 5,000 randomly selected state employees said Friday that nearly one-third opened the email, a quarter clicked on the link and almost one-fifth entered their user ...

Origami-inspired self-locking foldable robotic arm

March 15, 2018

A research team of Seoul National University led by Professor Kyu-Jin Cho has developed an origami-inspired robotic arm that is foldable, self-assembling and also highly-rigid. (The researchers include Suk-Jun Kim, Dae-Young ...

Tokyo Tech's six-legged robots get closer to nature

March 12, 2018

A study led by researchers at Tokyo Institute of Technology (Tokyo Tech) has uncovered new ways of driving multi-legged robots by means of a two-level controller. The proposed controller uses a network of so-called non-linear ...


Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.