3 C
Saturday, January 28, 2023
HomeEntertainmentCryptographic techniques that are based on the unpredictable | Coffee and...

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


Related stories

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.

Also Read:

Rosalía already sounds in English with her song “LLYLM (Lie like you love me)” | Entertainment | Th...
Luis Miguel walks through Spain his love with Paloma Cuevas | Entertainment | The USA Print
Walter Mercado's Las Estrellas Horoscope for today Saturday January 28, 2023 | Entertainment | The ...
Jorge Ramos interviewed Don Francisco | Entertainment | The USA Print
Shakira adds another success in 2023 with an exhibition | Entertainment | The USA Print
Rita Ora Confirms She's Married to Taika Waititi | Entertainment | The USA Print
Barcelona extends Marcos Alonso's contract | Entertainment | The USA Print
Will There Be a "The Last of Us" Season 2? | Entertainment | The USA Print
Luis Miguel is caught on a romantic date with Paloma Cuevas, his comadre | Entertainment | The USA ...
Documentaries, drama and movies from Colombia and Brazil. | Entertainment | The USA Print
The first millioncito reached it in 8 minutes. On Shaki's Twitter, the song has had more than 12 mi...
Kate del Castillo changes course and channel in the TV series 'Volver a caer'. A story of love, bet...
J Balvin Is Performing a Futuristic VR Concert | Entertainment | The USA Print
Jennifer Lopez and Jason Duhamel have an explosive wedding in "Shotgun Wedding" | Entertainment | T...
Olga Tañón published a new song | Entertainment | The USA Print
Allu Arjun: UAE Golden Visa for Allu Arjun.. Photos going viral..
Ivana Shaji: Beauty is only beauty, you are beautiful.. Do you know who is Love Today's beauty Ivana...
Tamannaah: An angel-like danger was born.
Mark NT
Mark NT
Mark NT was born and raised in the India. He worked at a literary development company as a publisher. He is a creative website writer for teens and a good book reviewer.


- Never miss a story with notifications

- Gain full access to our premium content

- Browse free from up to 5 devices at once

Latest stories


Please enter your comment!
Please enter your name here

Up to 75% off on Best Web Hosting