True one-way functions exist if a certain version of complexity is hard to compute, and there is a clear-cut way to build one. One-way functions can't exist if this version of complexity is easy to compute.
The finding suggests that cryptographers could focus on understanding the complexity of Kolmogorov instead of looking for one-way functions. The proof is that there is work on the foundations of cryptography.
Multiple research groups are working to get to the bottom of things after the paper stimulated cryptographers and complexity theorists to work together more closely.
Hard problems are usually obstacles. It's a boon when you can use it against your adversaries. We stand today on the verge of a revolution because of a paper written in 1976 by Martin Hellman and Whitfield Diffie.
In the decades that followed, researchers figured out how to build a wide variety of cryptographic tools out of one-way functions, including private key encryption, digital signatures, pseudorandom number generators and zero-knowledge proof. Pass said that the paper was almost like a prophecy. cryptographers built these super-complex and beautiful creatures from the single building block of one-way functions.
To get a feel for how one-way functions work, imagine someone asked you to multiply two large prime numbers. It is doable if you arrive at the answer of 46,346,213. If someone handed you the number and asked for its prime factors, you might be at a loss. There is no efficient way to find the factors that make up a large number. If you start with large enough prime numbers, multiplication is easy to do, but hard to reverse. We don't know if this is the case. Someone could figure out a way to factor numbers quickly.
There are many one-way functions from different areas of mathematics, but no one function has a higher claim than another. If multiplication were toppled as a one-way function tomorrow, that wouldn't say anything about the validity of the other candidate one-way functions. Cryptographers have been asking if there is a quintessential one-way function which would pull all the other candidates down with it.
In 1985, a computer scientist at Boston University named Leonid Levin answered the question in a formal way, showing a one-way function that is guaranteed to be a one-way function. Eric Allender, a computer scientist at Rutgers University, said that his construction was very artificial. It's not something anyone would have studied to get a result like that.
cryptographers were looking for a universal one-way function that would give them insight into whether one-way functions exist. The problem of randomness that originated in the 1960s is a problem that researchers have been thinking about for a long time. Its connection with one-way functions was not obvious.
Pass was fascinated by that connection as a graduate student. He toyed with the problem for a long time. He was certain that there was something there, and a burst of activity over the past five years only increased his interest.
Pass tried to get several graduate students to explore the question with him, but they were unwilling to take on the project. Pass wrote in an email thatYanyi was fearless. They plunged in together.
It is difficult to pin down the concept of randomness. A Dilbert comic strip has an office tour guide showing Dilbert the accounting department, and it turns out to be a monster who just keeps repeating.
If someone shows you the number strings 999999999999 and 03729563829603547134 and says they were chosen randomly, you can't completely debunk that claim. The second string feels random.
We think that we know what we mean when we say it.
To get at the idea of a random string of numbers, the 1960's was when Andrey Kolmogorov decided to focus on the ease with which it can be described. The string 999999999999 can be concisely described as 20 9s, but it might not have any description shorter than the string itself.
The complexity of a string is the length of the shortest program that produces the string as an output. If we are dealing with thousand-digit strings, there are some programs that are very short. Some strings have programs that are in the middle.
One of the core concepts of computer science was complexity. The idea was discovered multiple times in the 1960s. Pass said it was a deep problem, not just about randomness and mathematics, but also about science.
There is no program that can calculate the complexity of every string because it is incomputable. We know this because we would end up with a contradiction if there were such a program.
Imagine a program that can compute the complexity of a string. Let's call the program S, whose complexity is double that of K.
We can use program K to calculate S in a new program called P. The program outputs S, and we defined it as a string with 2 million characters. There is a contradiction.
If we look for the shortest program that outputs a string, we can specify what we mean. The program P has to check so many strings that it takes a lot of time to run. If we forbid slow programs, we end up with a concept called time bounded complexity. We can calculate the time bounded complexity for every possible string, at least in principle. It is as natural a concept as the original one. Pass said what we really care about is, can you actually generate the string while we live on Earth, or while the universe still exists?
How hard it is to compute is a natural next question since complexity is computable. Allender said that this is the question that was proved to be the key to whether one-way functions exist.
If you have set your sights on a less lofty goal than calculating the exact time-bounded complexity of every possible string, then you are content to calculate it approximately. True one-way functions cannot exist if there is an efficient way to do this. Pass said that all candidate one-way functions would be breakable in practice.
The true one-way functions must exist if calculating the approximate time-bounded complexity is too hard. The paper provides a specific way to make one if that is the case. Ishai said that the one-way function that they describe in their paper is too complicated to use in real-world applications. He said that the impracticality of the one-way function is not a fundamental limitation.
If their function can be made practical, it should be used in preference to the candidate one-way functions based on multiplication and other mathematical operations. If we can break a scheme like that, all other schemes can also be broken.
The paper set off a cascade of new research at the interface of complexity theory. While both disciplines investigate how hard computational problems are, they come at the question from different mindsets, according to a complexity theorist at the University of Oxford. He said that complexity theory is conservative and that it is fast- moving. There are long-standing open questions in the latter field, and once in every dozen years, something happens. The questions are very difficult.
Cryptographers have powerful reasons to think that one-way functions exist, and complexity theorists have different reasons to think that time-bounded Kolmogorov complexity is hard. The two hypotheses are stronger because of the new results.
If you believe that the problem is difficult, then you believe in one-way functions. If you think that this version of time-bounded Kolmogorov complexity must be hard, then you must be a believer in cryptanalysis.
Cryptographers are trying to make the one-way function more practical. They are starting to look into the existence of one-way functions and more sophisticated ciphers. The complexity theorists are starting to understand the complexity better.
Ishai said that the discovery might be a seed of a much richer theory.
All Rights Reserved © 2024
