Crypto Is Far More Than Currencies

Lately, the prefix "crypto" has been mostly associated with cryptocurrencies, but while the latter appeared just a few years ago, cryptography has thousands of years of history. In fact, the need to hide valuable information from third-party intrusions has accompanied mankind since antiquity. Ancient civilizations resorted to basic substitution ciphers, such as the Atbash cipher, originally used to encrypt the Hebrew alphabet, or the Caesar cipher, employed in ancient Rome. More recently, mechanical and electromechanical cipher machines, such as the famous Enigma machine, played an important role in World War II, as represented in the movie "The Imitation Game", based on the biography of Alan Turing, famous mathematician, cryptographer and pioneer of computer science.

Illustration by Weiwei Chen
It's no chance that, after World War II, the evolution of cryptography went hand in hand with the development of computer science and with the study of computational complexity. Cryptography and computational complexity are also the main fields of interest of professor Alon Rosen, who recently joined Bocconi Department of Decision Sciences. He is the recipient of an ERC Advanced Grant on these topics, namely on the study of new measures for computational hardness.

"Computational complexity is crucial for cryptography," explains Rosen, "and computationally hard problems have been one of the building blocks of cryptography for decades. One example 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 (recall that a prime number is a natural number greater than 1 – for example 2, 3, etc. – that is divisible only by 1 and itself). Cryptography leverages the following computational asymmetry: it is easy and fast to multiply together two large prime numbers, thus obtaining a very large semiprime, but it is very hard to factorize a very large semiprime which is the product of two primes that are distinct but approximately of the same size. By 'hard' we mean that it requires a lot of computational resources and a lot of time – even years – thus making this task possible in principle but unfeasible in practice. This is why these two hard-to-find primes can be used as the key to decipher a code."

"Prime factorization is just an example of a hard problem that can be leveraged in cryptography. Cryptographers are always in search of new hard problems, but the definition of a 'hard problem' is itself non-trivial. Traditional definitions tag a problem as hard if it requires a computational time that grows exponentially with the size of the input (in the prime factorization example, the size of the input is the number of digits of the number to factorize). However, this definition may be too restrictive, and a large-degree polynomial growth may be enough for cryptographic purposes."

This could open up new avenues for cryptography, which not only has a long history, but also a crucial role in the here and now. In fact, end-to-end encryption for emails and chats, digital signatures, electronic payments, and cryptocurrencies themselves, all rely on good, old – but always evolving – cryptography.

Find out more

Ball, M., Rosen, A., Sabin, M., Vasudevan, P. N. "Average-case fine-grained hardness." In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (2017). DOI: https://doi.org/10.1145/3055399.3055466.