Language Log

« previous post | next post »

If you're interested in one-way functions and Kolmogorov complexity, you'll probably want to read this mind-crunching article:

"Researchers Identify ‘Master Problem’ Underlying All Cryptography", by Erica Klarreich, Quanta Magazine (April 6, 2022)

The existence of secure cryptography depends on one of the oldest questions in computational complexity.

To ease our way, here are brief descriptions of the two key terms:

In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems. Not being one-to-one is not considered sufficient for a function to be called one-way….

(source)

In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that produces the object as output. It is a measure of the computational resources needed to specify the object, and is also known as algorithmic complexity, Solomonoff–Kolmogorov–Chaitin complexity, program-size complexity, descriptive complexity, or algorithmic entropy. It is named after Andrey Kolmogorov, who first published on the subject in 1963.

(source)

The article begins unexpectedly, at least for me:

In 1868, the mathematician Charles Dodgson (better known as Lewis Carroll) proclaimed that an encryption scheme called the Vigenère cipher was “unbreakable.” He had no proof, but he had compelling reasons for his belief, since mathematicians had been trying unsuccessfully to break the cipher for more than three centuries.

There was just one small problem: A German infantry officer named Friedrich Kasiski had, in fact, broken it five years earlier, in a book that garnered little notice at the time.

Cryptographers have been playing this game of cat and mouse, creating and breaking ciphers, for as long as people have been sending secret information. “For thousands of years, people [have been] trying to figure out, ‘Can we break the cycle?’” said Rafael Pass, a cryptographer at Cornell Tech and Cornell University.

Five decades ago, cryptographers took a huge step in this direction. They showed that it’s possible to create provably secure ciphers if you have access to a single ingredient: a “one-way function,” something that’s easy to carry out but hard to reverse. Since then, researchers have devised a wide array of candidate one-way functions, from simple operations based on multiplication to more complicated geometric or logarithmic procedures.

Today, the internet protocols for tasks like transmitting credit card numbers and digital signatures depend on these functions. “Most of the crypto that is used in the real world is something that can be based on one-way functions,” said Yuval Ishai, a cryptographer at the Technion in Haifa, Israel.

But this advance has not ended the cat-and-mouse game — it has only sharpened its focus. Now, instead of having to worry about the security of every aspect of an encryption scheme, cryptographers need only concern themselves with the function at its core. But none of the functions currently in use have ever been definitively proved to be one-way functions — we don’t even know for sure that true one-way functions exist. If they do not, cryptographers have shown, then secure cryptography is impossible.

In the absence of proofs, cryptographers simply hope that the functions that have survived attacks really are secure. Researchers don’t have a unified approach to studying the security of these functions because each function “comes from a different domain, from a different set of experts,” Ishai said.

Cryptographers have long wondered whether there is a less ad hoc approach. “Does there exist some problem, just one master problem, that tells us whether cryptography is possible?” Pass asked.

Now he and Yanyi Liu, a graduate student at Cornell, have shown that the answer is yes. The existence of true one-way functions, they proved, depends on one of the oldest and most central problems in another area of computer science called complexity theory, or computational complexity. This problem, known as Kolmogorov complexity, concerns how hard it is to tell the difference between random strings of numbers and strings that contain some information.

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

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

…

Here's the abstract of the paper by Yanyi Liu and Rafael Pass, submitted to arXiv on 9/24/20):

On One-way Functions and Kolmogorov Complexity

We prove that the equivalence of two fundamental problems in the theory of computing. For every polynomial t(n)≥(1+ε)n,ε>0, the following are equivalent:

– One-way functions exists [recte exist] (which in turn is equivalent to the existence of secure private-key encryption schemes, digital signatures, pseudorandom generators, pseudorandom functions, commitment schemes, and more);

– t-time bounded Kolmogorov Complexity, Kt, is mildly hard-on-average (i.e., there exists a polynomial p(n)>0 such that no PPT algorithm can compute Kt, for more than a 1−1p(n) fraction of n-bit strings).

In doing so, we present the first natural, and well-studied, computational problem characterizing the feasibility of the central private-key primitives and protocols in Cryptography.

Klarreich goes on to broach the core issue of her argument thus:

Leveraging Hardness

Usually, a hard problem is an obstacle. But in cryptography, where you can deploy it against your adversaries, it’s a boon. In 1976, Whitfield Diffie and Martin Hellman wrote a groundbreaking paper in which they argued that the particular hardness of one-way functions was precisely what cryptographers needed to meet the demands of the dawning computer age. “We stand today on the brink of a revolution in cryptography,” they wrote.

In the decades that followed, researchers figured out how to build a wide variety of cryptographic tools out of one-way functions, including private key encryption, digital signatures, pseudorandom number generators and zero-knowledge proofs (in which one person can convince another that a statement is true without revealing the proof). Diffie and Hellman’s paper was “almost like a prophecy,” Pass said. From the single building block of one-way functions, cryptographers managed to build “these super-complex and beautiful creatures,” he said.

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.

Cryptographers have gleaned an assortment of potential one-way functions from different areas of mathematics, but no single function has a higher claim than another. If, say, multiplication were toppled as a one-way function tomorrow, that wouldn’t say anything about the validity of the other candidate one-way functions. Cryptographers have long asked whether there is some quintessential one-way function — one which, if broken, would pull all the other candidates down with it.

…

What cryptographers were really after was a universal one-way function that stemmed from some natural problem — one that would give real insight into whether one-way functions exist. Researchers long had a particular problem in mind: Kolmogorov complexity, a measure of randomness that originated in the 1960s. But its connection with one-way functions was subtle and elusive.

Pass became fascinated with that connection as a graduate student in 2004. Over the years he toyed with the problem, without much success. But he felt sure there was something there, and a burst of activity in Kolmogorov complexity over the past five years only heightened his interest.

Pass tried to persuade several graduate students to explore the question with him, but none were willing to take on what might turn out to be a fruitless project. Then Yanyi Liu started graduate school at Cornell. “Yanyi was fearless,” Pass wrote in an email. Together, they plunged in.

Klarreich then asks:

What Is Random?

The concept of randomness is, by its nature, tricky to pin down. There’s a Dilbert comic strip in which an office tour guide shows Dilbert the accounting department’s “random number generator” — which turns out to be a monster who just keeps repeating the number 9. “Are you sure that’s random?” Dilbert asks. “That’s the problem with randomness,” his guide answers, “you can never be sure.”

After this, the article becomes increasingly mathematical and abstruse, paying attention to the implications of such deep and dense topics as computable and incomputable, practical and impractical (which is actually desirable), and so forth.

One quotation that struck me especially powerfully is this one from Ryan Williams, a computer scientist at the Massachusetts Institute of Technology:

“If you believe this [Kolmogorov complexity] problem is difficult … then you believe in one-way functions,” Williams said. And “if you believe in crypto at all, then you’ve kind of got to believe that this version of time-bounded Kolmogorov complexity must be hard.”

The article is accompanied by four captivating photographs:

1. Rafael Pass

2. Martin Hellman, Whitfield Diffie, and Ralph Merkle

3. Yanyi Liu

4. Andrey Kolmogorov

The caption of the last photograph reads:  "Andrey Kolmogorov came up with a way to measure randomness based on how easy it was to describe the generation of a string of numbers."  He is the veritable picture of a genial genius — but still a little bit scary.

 

Selected readings

• "Wake up! There's a Kolmogorov complexity trough!" (8/7/08)
• "Linguists who count" (5/28/09) — this comment
• "Becoming a modifier" (7/8/17)
• "The National Rhetoric Association" (1/5/13) — in the comments
• "Translating games" (12/9/08)
• "Man bites dog" (8/20/13)
• "'Tis the season" (12/21/07)
• "Pharyngula minutes" (8/1/08)

 

[Thanks to James Fanell]

April 12, 2022 @ 6:54 am · Filed by Victor Mair under Cryptography, Language and computers, Language and mathematics, Language and philosophy

Permalink