Cryptographic techniques that are based on the unpredictable | Coffee and theorems | Science | The USA Print


Programming code on a computer.
Programming code on a computer.KACPER PEMPEL (REUTERS)

How can we guarantee that our information is well protected? If someone tries to access our data, how can we trust that their attacks will be unsuccessful? Ideally, you would have proof that all you can see are nonsense words, collections of arbitrary zeroes and ones, from which you will not be able to extract any information. This is what he does the provable security theory, a branch of mathematical cryptography that seeks formal proofs that relate the difficulty of breaking a cryptographic construction —such as those that protect our online banking transactions— with that of solving a specific mathematical problem —for example, the difficulty of factoring very large numbers into their prime divisors. Demonstrating this relationship is not an easy challenge.

One of the essential objects of this theory are the so-called one way functions or functions one way. These are functions that are easy to evaluate —that is, it is easy to apply them to a given object—, but for which doing the opposite path —given a value, calculating an element that the function transforms into precisely that— is a very complex task. A classic example of a process of this type could be the one based on the factorization of integers; given two prime numbers it is very easy to multiply them, but, given a number, no really fast method is known —not even using the most powerful computers— to decompose it into the product of two prime numbers (that is, to know from which two numbers “comes ”). Already with relatively small numbers, the difference in difficulty between multiplication and its inverse process is observed: for example, when considering the primes 7919 and 541 and their product, 4,284,179.

Many other mathematical problems pose good “candidates” for one-way functions: the computation of discrete logarithms, the shortest vector problems on lattices, etc. However, how can we ensure that the resulting functions are really one-way? Is it possible to rule out that someone later finds a simple way to reverse the processes involved? For example, how to guarantee that an efficient algorithm for factoring integers with new ideas can never be designed? Could it be that there is actually no one-way function, but for some functions, we haven’t found the right methods?

Cryptographers have always longed to solve the general problem, irrefutably arguing for the existence of these objects. If this result were obtained, we would know that it is possible to design a huge number of cryptographic constructions: pseudo-random generators, encryption, signature, identification, commitment schemes… If we knew that they did not exist, none of these constructions would be completely secure: in the future a method could appear to break them. Furthermore, proving that there are one-way functions would solve one of the so-called million-dollar problems, providing evidence that the complexity class P is distinct from the class NP.

So far, no one has managed to solve the problem, but YanyiLiu Y Raphael Passtwo researchers from Cornell University (USA), have been able to quantify, to a certain extent, how difficult it is to do so. In a recent work, manage to quantify the difficulty of proving the existence of one-way functions, using a famous complexity theory problem, which deals with the so-called Kolmogorov complexity (either K-complexity). The K-complexity of a sequence is the length of the shortest algorithm needed to build it. This notion, introduced in the sixties of the last century by the Russian mathematician Andrey Kolmogorov, can be interpreted as a measure of the computational resources that are necessary to describe any object. It allows, for example, to quantify the difficulty of detecting patterns in arbitrary binary sequences: the simpler the pattern that a sequence follows, the more short will be its Kolmogorov complexity.

Liu and Pass’s result also involves a fundamental ingredient in cryptography: time, as a relevant factor when measuring the difficulty of a task. This is reflected through a function you, that limits the calculation time necessary to describe the sequence under study. Thus, the Kolmogorov t-complexity is the length of a program capable of constructing any binary sequence of a certain length, in time bounded by a function you, which depends on time. Liu and Pass’s result says precisely that the existence of one-way functions is equivalent to the fact that the you-Kolmogorov complexity is greatin a certain sense.

Consequently, we can only guarantee that current cryptography is solidly grounded if it is not possible to design a foolproof algorithm to calculate this complexity. In other words, if the most accurate algorithm for calculating the you-complexity of Kolmogorov is doomed to fail, at least in a not insignificant number of sequences. That is, much of our crypto will remain valuable only if this complexity is unpredictable.

Liu and Pass have received recognition from the international crypto community for this result, in addition to the prestigious NSA Best Cybersecurity Research Paper. Without a doubt, his work brings us a little closer to understanding what kinds of processes slip past the scrutiny of algorithms and can therefore help us keep our data safe.

Maria Isabel Gonzalez Vasco She is Professor of Applied Mathematics at the King Juan Carlos University.

Agate Timón García-Longoria is coordinator of the Mathematical Culture Unit of the ICMAT.

Coffee and Theorems is a section dedicated to mathematics and the environment in which it is created, coordinated by the Institute of Mathematical Sciences (ICMAT), in which researchers and members of the center describe the latest advances in this discipline, share meeting points between mathematics and other social and cultural expressions and remember those who marked their development and knew how to transform coffee into theorems. The name evokes the definition of the Hungarian mathematician Alfred Rényi: “A mathematician is a machine that transforms coffee into theorems”.

Edition and coordination: Agate A. Timón G Longoria (ICMAT).

You can follow MATERIA on Facebook, Twitter and Instagramor sign up here to receive our weekly newsletter.


Please enter your comment!
Please enter your name here