“In a new paper, Cornell Tech researchers identified a problem that holds the key to whether all encryption can be broken — as well as a surprising connection to a mathematical concept that aims to define and measure randomness,” according to a news release shared by Slashdot reader bd580slashdot:
“Our result not only shows that cryptography has a natural ‘mother’ problem, it also shows a deep connection between two quite separate areas of mathematics and computer science — cryptography and algorithmic information theory,” said Rafael Pass, professor of computer science at Cornell Tech…
Researchers have not been able to prove the existence of a one-way function. The most well-known candidate — which is also the basis of the most commonly used encryption schemes on the internet — relies on integer factorization. It’s easy to multiply two random prime numbers — for instance, 23 and 47 — but significantly harder to find those two factors if only given their product, 1,081. It is believed that no efficient factoring algorithm exists for large numbers, Pass said, though researchers may not have found the right algorithms yet.
“The central question we’re addressing is: Does it exist? Is there some natural problem that characterizes the existence of one-way functions?” he said. “If it does, that’s the mother of all problems, and if you have a way to solve that problem, you can break all purported one-way functions. And if you don’t know how to solve that problem, you can actually get secure cryptography….”
In the paper, Pass and doctoral student Yanyi Liu showed that if computing time-bounded Kolmogorov Complexity is hard, then one-way functions exist. Although their finding is theoretical, it has potential implications across cryptography, including internet security.
of this story at Slashdot.
Source:: Slashdot