Refueling the Cryptography Tank

Public-key cryptography risks running out of steam and it could need an alternative source of energy. Alon Rosen, Full Professor at Bocconi Department of Computing Sciences, obtained a €2.49mln ERC Advanced Grant to try and find this new source.

The fuel cryptography runs on is computationally hard problems, i.e. problems that are difficult and time-consuming. A cryptographer seeks problems so hard that they can't be solved, on average, in reasonable time, without a hint in the form of a key, i.e. a piece of information (usually a string of bits) which, when processed through a cryptographic algorithm, can encode or decode data.

Cryptography relies on computational asymmetry. It needs problems with an easy direction (the problem the "good guy", i.e. the encryptor, must solve) and a hard one (the problem the "bad guy" should solve to decrypt information).

In public-key cryptography, in particular, the encrypting side uses a publicly known key to encrypt its information, while the decrypting side uses a secret, and different, key. Its counterpart is private-key cryptography, where both sides use the same secret key. Public-key cryptography is extremely useful in many applications, but it comes with two downsides: it is a painfully slow process and finding hard problems for it is much more difficult than finding hard problems for private-key cryptography.

"The kind of computational hardness we need for public-key cryptography is hard to come by," Professor Rosen says, "and in 45 years we only have found a handful of candidate hard problems."

A classic case of this type of structured computational asymmetry is prime factorization, that is the problem of breaking a number into the unique set of (smaller) prime numbers that multiplied together give back that number. Multiplying two prime numbers is easy, even when the numbers are very large, while going back to two prime numbers starting from their product is much harder.

Professor Rosen's ERC project (FGC – Fine-Grained Cryptography) aims to find new hard problems for public-key encryption and make it faster.

Traditionally, cryptography has been based on problems for which there is a conjectured exponential complexity gap between the easy and hard directions, where complexity can be considered a measure of the computational power needed to solve a problem.

Infographics by Weiwei Chen
Let's consider a 128 bit string as our key and use 128 as our parameter. An exponential complexity gap means that while the good guy has to face, for example, complexity equal to 128 raised to the power of two (=16,384), the bad guy faces complexity equal to two raised to the power of 128 (getting close to the number of particles in the world) – which makes it very unlikely they will crack the code.

Professor Rosen is exploring a new avenue, where the complexity gap is not exponential, but "only" polynomial. Following the example above, he wants to find problems where, if the complexity faced by the good guy is 128 raised to the power of two, the bad guy also faces 128 raised to a power. If the power is sufficiently high, the code is as secure as with an exponential complexity gap: 128 raised to a power of 20, for example, is roughly equal to 2 raised to a power of 140 and thus comparable to the exponential gap case.

"We have some suspects out there," Prof. Rosen says, "problems we can conjecture having a hard direction. Counterintuitive as it may seem, the hard thing for us is to show there is also an easy direction."