Randomness theory could hold key to internet security

July 27, 2020

ITHACA, N.Y. - Is there an unbreakable code?

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.

For example, it's easy to light a match, but impossible to return a burning match to its unlit state without rearranging its atoms - an immensely difficult task.

"The idea was, if we have such a one-way function, maybe that's a very good starting point for understanding cryptography," Pass said. "Encrypting the message is very easy. And if you have the key, you can also decrypt it. But someone who doesn't know the key should have to do the same thing as restoring a lit match."

But 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."

Meanwhile, mathematicians in the 1960s identified what's known as Kolmogorov Complexity, which refers to quantifying the amount of randomness or pattern of a string of numbers. The Kolmogorov Complexity of a string of numbers is defined as the length of the shortest computer program that can generate the string; for some strings, such as 121212121212121212121212121212, there is a short program that generates it - alternate 1s and 2s. But for more complicated and apparently random strings of numbers, such as 37539017332840393452954329, there may not exist a program that is shorter than the length of the string itself.

The problem has long interested mathematicians and computer scientists, including Juris Hartmanis, professor emeritus of computer science and engineering. Because the computer program attempting to generate the number could take millions or even billions of years, researchers in the Soviet Union in the 1960s, as well as Hartmanis and others in the 1980s, developed the time-bounded Kolmogorov Complexity - the length of the shortest program that can output a string of numbers in a certain amount of time.

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.

"If you can come up with an algorithm to solve the time-bounded Kolmogorov complexity problem, then you can break all crypto, all encryption schemes, all digital signatures," Pass said. "However, if no efficient algorithm exists to solve this problem, you can get a one-way function, and therefore you can get secure encryption and digital signatures and so forth."
The research was funded in part by the National Science Foundation and the Air Force Office of Scientific Research, and was based on research funded by the Intelligence Advanced Research Projects Activity in the Office of the Director of National Intelligence.

Cornell University

Related Cryptography Articles from Brightsurf:

New tool detects unsafe security practices in Android apps
Computer scientists at Columbia Engineering have shown for the first time that it is possible to analyze how thousands of Android apps use cryptography without needing to have the apps' actual codes.

A question of reality
Physicist Reinhold Bertlmann of the University of Vienna, Austria has published a review of the work of his late long-term collaborator John Stewart Bell of CERN, Geneva in EPJ H.

Randomness theory could hold key to internet security
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.

Future quantum computers may pose threat to today's most-secure communications
Quantum computers that are exponentially faster than any of our current classical computers and are capable of code-breaking applications could be available in 12 to 15 years, posing major risks to the security of current communications systems, according to a new RAND Corporation report.

Automated cryptocode generator is helping secure the web
In a paper presented at the recent IEEE Symposium on Security and Privacy, MIT researchers detail a system that, for the first time, automatically generates optimized cryptography code that's usually written by hand.

Is quantum computing scalable?
Debbie Leung, a fellow in CIFAR's Quantum Information Science program and a faculty member at the University of Waterloo's Institute for Quantum Computing, will discuss the challenges of scaling quantum computing at the AAAS meeting on Feb.

Quantifying how much quantum information can be eavesdropped
Summary The most basic type of quantum information processing is quantum entanglement.

Communication interception can be traced through meteor trails
Meteor burst communication is based on using meteors as cryptography assistants.

Slicing optical beams: Cryptographic algorithms for quantum networks
The mathematical models can be used not only for quantum networks and authentication but also for full-scale quantum computing.

Ytterbium: The quantum memory of tomorrow
Quantum communication and are the future of high-security communication. One of the major challenges is to create memories with the capacity to store quantum information carried by light.

Read More: Cryptography News and Cryptography Current Events
Brightsurf.com is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to Amazon.com.