How can we guarantee that our information is well protected? If someone tries to access our data, how can we trust their attacks to be unsuccessful? Ideally, you would have proof that all you can see are nonsense words, collections of random zeros and ones from which you cannot extract any information. He does the provable security theory, a branch of mathematical cryptography that looks for formal proofs that relate the difficulty of cracking a cryptographic construct—like the one that protects our online banking transactions—to the solution of a specific mathematical problem—for example, the difficulty very large numbers to be factored into their prime divisors. Proving this relationship is no easy challenge.
One of the main objects of this theory are the so-called Disposable works or functions disposable. These are functions that are easy to evaluate – that is, they can be easily applied to a given object – but for which the reverse way – given a value, computing an element that converts the function exactly into that – a very is a complex task. A classic example of a process of this kind might be the one based on factoring integers; With two prime numbers it is very easy to multiply them, but a given number is not really readily known – not even using the most powerful computers – to decompose it into the product of two prime numbers (i.e. which two numbers “comes out”). Even with relatively small numbers, the difference in difficulty between multiplication and its reverse process is observed: for example, when considering the prime numbers 7919 and 541 and their product 4,284,179.
Many other mathematical problems are good “candidates” for one-way functions: the computation of discrete logarithms, the shortest vector problems on lattices, etc. But how can we ensure that the resulting functions are really one-way functions? Can you rule out that someone later finds an easy way to reverse the processes? For example, how to guarantee that an efficient integer factorization algorithm can never be designed with new ideas? Is it possible that there really isn’t a one-way function, but we didn’t find the right methods for some functions?
Cryptographers have always longed to solve the general problem and irrefutably argue for the existence of these objects. If this result were obtained, we would know that it is possible to design a large number of cryptographic constructs: pseudo-random number generators, encryption, signature, identification, commitment schemes… If we knew that they did not exist, none of these constructs would be completely secure : In the future, a method to do this might appear break them. Furthermore, proving that there are one-way functions would solve one of the so-called million-dollar problems and would provide proof that the complexity class P is distinct from the class NP.
So far nobody has managed to solve the problem, but YanyiLiu Y Raffael PassTwo researchers from Cornell University (USA) were able to quantify to some extent how difficult this is. In a recent work succeeds in quantifying the difficulty of proving the existence of one-way functions using a famous complexity-theoretical problem, which deals with the so-called Kolmogorov complexity (either K complexity). That K complexity of a sequence is the length of the shortest algorithm needed to create it. This concept was introduced by the Russian mathematician in the 1960s Andrei Kolmogorov, can be interpreted as a measure of the computational resources required to describe any given object. For example, it allows to quantify the difficulty of recognizing patterns in any binary sequence: the simpler the pattern that a sequence follows, the more difficult it is short will be its Kolmogorov complexity.
The result of Liu and Pass also includes a fundamental ingredient in cryptography: time as a relevant factor in measuring the difficulty of a task. This is reflected by a function She, this limits the computation time necessary to describe the studied sequence. And that’s how it happened Kolmogorov t complexity is the length of a program capable of constructing any binary sequence of a given length, time-limited by a function she, which is time dependent. The result of Liu and Pass states precisely that the existence of one-way functions is equivalent to the fact that the she-Kolmogorov complexity is GreatIn a certain sense.
Consequently, we can only guarantee that current cryptography has a sound foundation if it is not possible to design a foolproof algorithm to compute this complexity. In other words, if the most accurate algorithm for calculating the she-Kolmogorov’s complexity is doomed to fail, at least in a not inconsiderable number of sequences. That said, much of our crypto will only remain valuable if that complexity is unpredictable.
In addition to the prestige, Liu and Pass have also received recognition from the international crypto community for this result NSA Best Cybersecurity Research Paper. Without a doubt, his work brings us a step closer to understanding what types of processes can elude algorithmic scrutiny and therefore help us protect our data.
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 arises, coordinated by the Institute of Mathematical Sciences (ICMAT), in which researchers and members of the center describe the latest advances in this discipline and meeting points between mathematics and others share social networks and cultural expressions and remember those who shaped its evolution and knew how to turn coffee into theorems. The name recalls the definition of the Hungarian mathematician Alfred Rényi: “A mathematician is a machine that converts coffee into theorems”.
Editing and coordination: Agate A. Timón G Longoria (ICMAT).