For centuries, people have been searching for ways to keep information from getting into the hands of the public. Cryptography gave them an answer to that. Cryptography has been used, both in its basic and sophisticated forms to hide sensitive information. Egyptian hieroglyphics contain the first known and verified example of ancient cryptography. In our age where internet is so rampant and people want to keep their personal information private, cryptography is gaining traction. But one cycle exists for all cryptography. First, someone finds a good code and starts using it, it becomes effective for some time and eventually someone somewhere breaks the code, rendering it ineffective. Because of this, people ask: Is there such a thing as an unbreakable code?
To help them answer this question and solve it, scientists came up with the concept of one-way functions. One-way functions are functions that are easy to compute on the given inputs but hard to invert. That is, you cannot get the inputs from the output when reversing it. One-way functions could make good candidates for code that cannot be easily broken. That is, it would be close to impossible to find an algorithm that would revert the output. Unfortunately, one-way functions are just a conjecture. But that conjecture has been behind much tools that have been built in cryptography, authentication, personal identification, and other data security applications.
Getting a one-way function that is feasible has huge ramifications in the internet age. It could solve the Internet security problem for good. Industries such as banking, telecommunications, and e-commerce would be in a hurry to apply it. Yes, it has been elusive but that is not to say that there have not been candidates.
One well known candidate for one-way functions involves the multiplication and factoring of prime numbers. To get the outputs, two prime numbers are given to a function and their product is computed. This function takes a quadratic time complexity. It is really hard to factor out the prime numbers given the output although it can be done in exponential time. Another candidate is the Rabin function which gave rise to the Rabin cryptosystem on the assumption that the Rabin function is one-way.
The two candidates above can be broken though if a really good mathematician knows how to write an efficient algorithm.
This problem was what Rafael Pass, Professor of computer science at Cornell Tech wanted to tackle. He believes that if he could find a really good and valid one-way function, then all internet security problem could be solved. Internet encryption would be safe for all. According to his postulate, a good one-way function is like lighting a match. After a match is lit, you cannot get back the sticks. They are now ashes. So, a good one-way function would be an encryption scheme in which the decryption would lie only in the hands of the person who encrypted it. To get a candidate, he looked to mathematics and to a field that is unrelated to cryptography – quantifying the amount of randomness in a string of numbers, or what is known as the Kolmogorov complexity.
The Kolmogorov complexity of an object is defined as the length of the shortest computer program that can generate that object as an output. The Kolmogorov complexity of a string that has a definite pattern to it, like ababababababab, which is writing ab 7 times, can easily be computed. But what if you have some random string? asdwer2345tgdhncjmckkjkd? How do you compute the Kolmogorov complexity in an efficient manner? It has been found that the Kolmogorov complexity for such random strings is computationally close to impossible. What makes it more infeasible is computing the time bounds of such an algorithm.
Taking from this idea, Professor Pass focused his research on whether an algorithm can solve the time-bounded Kolmogorov complexity. If such an algorithm exists, his research posits, then all cryptography can be broken. On the other hand, if no efficient algorithm exists for such a time-bound Kolmogorov complexity, then one-way functions do exist and they can be found.
His research has implications for encryption schemes that are widely used in the Internet. Popular social media platforms use encryption to make their platforms more secure, banks in e-banking platforms rely on encryption being more unbreakable, and overall, we depend on making sure our internet lives are kept free from the prying public. So, Professor Pass’ theory is of great interest and only time will tell when a really good algorithm can be found based on his research that would make sure our Internet security is compromised no matter what platform we are using.
Source for this article was from Cornell University.