A central problem in all computer security (branch of cryptography) is the one-way problem. Cryptography should function as a one-way street: You can go north but you can’t go south. So if a hacker doesn’t have the code to go north, he can’t go anywhere. Which is where the computer security expert would like to leave the hacker…

Is there such a thing as a one-way function in mathematics? Mathematician Erica Klarreich says, probably yes, and explains what it looks like:

To get a feel for how one-way functions work, imagine someone asked you to multiply two large prime numbers, say 6,547 and 7,079. Arriving at the answer of 46,346,213 might take some work, but it is eminently doable. However, if someone instead handed you the number 46,346,213 and asked for its prime factors, you might be at a loss. In fact, for numbers whose prime factors are all large, there is no efficient way (that we know of) to find those factors. This makes multiplication a promising candidate for a one-way function: As long as you start with large enough prime numbers, the process seems easy to do, but hard to undo. But we don’t know for sure that this is the case. Someone could find a fast way to factor numbers at any moment.”

Erica Klarreich, “Researchers Identify ‘Master Problem’ Underlying All Cryptography” at Quanta (April 6, 2022)

However, she tells us that a 2020 paper showed that a master cryptography program that a hacker can’t just break is indeed possible:

Liu and Pass proved that if a certain version of Kolmogorov complexity is hard to compute, in a specific sense, then true one-way functions do exist, and there’s a clear-cut way to build one. Conversely, if this version of Kolmogorov complexity is easy to compute, then one-way functions cannot exist. “This problem, [which] came before people introduced one-way functions, actually turns out to fully characterize it,” Pass said.

The finding suggests that instead of looking far and wide for candidate one-way functions, cryptographers could just concentrate their efforts on understanding Kolmogorov complexity. “It all hinges on this problem,” Ishai said. The proof is “breakthrough work on the…