[ad_1]
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 foundations of cryptography.”
Erica Klarreich, “Researchers Identify ‘Master Problem’ Underlying All Cryptography” at Quanta (April 6, 2022)
As Klarreich points out, Kolmogorov complexity, the great achievement of Andrei Kolomogorov (1903–1987)was to clarify the fact that randomness may not necessarily look disordered. The question turns on the ease with which a string of numbers can be described:
The string 99999999999999999999 can be concisely described as “20 9s,” but the string 03729563829603547134 might not have any description shorter than the string itself.
Erica Klarreich, “Researchers Identify ‘Master Problem’ Underlying All Cryptography” at Quanta (April 6, 2022)
A string that has no description shorter than itself would be a better bet for cryptography. If the hacker doesn’t know it, he can’t guess it.
Computer security is rapidly becoming a huge problem, as David Kruger has been telling us in a series here at Mind Matters News. Curiously, creating better security is not just plain common sense; it takes us high into the very philosophy of mathematics.
You may also wish to read:
The sweet science of agile software development. Effective security, as opposed to partial security, increases costs in the short run but decreases them in the long run. Software veteran David Kruger: Getting makers to change their priorities to safer products safe rather than the next cool new feature will by no means be easy.
[ad_2]
Source link
