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.

The question has been central to cryptography for thousands of years, and lies at the heart of efforts to secure private information on the internet. 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.

«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.

Pass is co-author of «On One-Way Functions and Kolmogorov Complexity,» which will be presented at the IEEE Symposium on Foundations of Computer Science, to be held Nov. 16-19 in Durham, North Carolina.

«The result,» he said, «is that a natural computational problem introduced in the 1960s in the Soviet Union characterizes the feasibility of basic cryptography — private-key encryption, digital signatures and authentication, for example.»

For millennia, cryptography was considered a cycle: Someone invented a code, the code was effective until someone eventually broke it, and the code became ineffective. In the 1970s, researchers seeking a better theory of cryptography introduced the concept of the one-way function — an easy task or problem in one direction that is impossible in the other.

Story Source: Materials provided by Cornell University. Original written by Melanie Lefkowitz. Note: Content may be edited for style and length.