Comment by gnull | Hacker News Reader

Comment by gnull | Hacker News Reader

Identifying the connection between one-way functions and Kolmogorov complexity is truly impressive. But the article oversimplified a few things that may be misleading for someone.

1. One-way functions are not all cryptography. Some constructions may need stronger assumptions than one-way functions (we don't know yet if they do). So this problem is a “Master Problem” only for a subset of cryptography (symmetric encryption, pseudorandom generators, etc.).

2. This is not the first “Master Problem” to base one-way functions on. There's Levin's complete one way function [1; Section 4.3]. Breaking it is proven to be as hard as any other one-way function, in other words if there exist one-way functions then this is one of them. But Levin's construction is somewhat artificial (it combines many one-way function candidates to create the “master one-way function”) and is not as surprising since its techniques and formulation are similar to how the usual one-way functions are defined. The connection from the linked article, on the other hand, is very surprising and unusual; it connects one-way functions to a more distant field which (to me) seems to be operating with quite different concepts.

It's also fun to know that similar “Master Problems” exist for other primitives too. For example, for public-key encryption there's a Complete Public Key cryptosystem [2]. Albeit this one is similar in spirit to Levin's construction (not as surprising IMO as the linked article), the complete cryptosystem is obtained by combining many other cryptosystems.

[1]: https://arxiv.org/abs/cs/0012023

[2]: https://eccc.weizmann.ac.il//eccc-reports/2006/TR06-046/inde...

> There's Levin's complete one way function [1; Section 4.3].

I think the article also mentions this:

> But his construction was “very artificial,” said Eric Allender, a computer scientist at Rutgers University. It is “not something anybody would have studied for any reason other than to get a result like that.”

But as a layman to cryptography I don't get what is the significant difference between this finding and Levin's. Is there anyone who can explain this to someone with an undergraduate level of mathematical backgrounds?

> But as a layman to cryptography I don't get what is the significant difference between this finding and Levin's. Is there anyone who can explain this to someone with an undergraduate level of mathematical backgrounds?

Here's a massive simplification. Let's say you tell me "Here's a conjecture: since multiplying 2x3 is hard, multiplying any combination of two numbers from 1-5 is hard. I can't prove that it is hard, but if all of them are hard, then my cryptography works!"

Levin's complete function approach : "Here's a function that's at least as hard as any given combination of two numbers: (1x2) + (1x2) + (1x3) + (1x4) + (1x5) + (2x3) + (2x4)... [and so on]. If that turns out to be easy, than your conjecture is wrong!"

The article states that there is a novel and surprising connection: "Proving the difficulty of multiplying any random combination of numbers under 5 is equivalent to solving this seemingly unrelated (and as yet unsolved) problem in geometry."

The two approaches are pretty different and have very different ramifications. While in a lot of cases, the approach of "here's an equivalent problem" doesn't actually help, in some cases it turns out that the equivalent problem is easier to solve. Or that the connection between the two opens up completely new approaches to solutions - or even applications of the math involved. Sometimes just the proof itself causes new connections! Often it takes considerable time before the impacts show themselves.

> I think the article also mentions this

My bad, I didn't read the article carefully enough.

> I don't get what is the significant difference between this finding and Levin's.

I think it's generally very important to find connections between distant and seemingly unrelated fields. And it's even better to express two seemingly separate fields in the same terms. Because then there's a lot of potential to cross apply the techniques which were developed in those fields. You can see the linked result not only as a formal construction of a problem with certain properties, but also as a link between two distant fields and as one of the many steps needed to maybe one day show that those fields are the same thing. One of my theoretician friends likes to say that solutions in mathematics are valuable because of the "moral" they have, i.e. the possibilities and lessons they demonstrate, not because they formally satisfy some conditions.

Think of Physics, Chemistry and Biology. Centuries ago they were completely separate fields. A growing plant and a lightning bolt were completely different concepts which seemed to be operated by their own distinct laws and have nothing to do with each other. But as the Science progressed, people learned about the elemental particles and could see now that lightning bolt and a plant are not separate concepts, but only manifestations of the same laws and processes on lower levels. Now Physics, Chemistry and Biology are not completely distinct domains (Richard Feynman would argue that the latter two are sub-fields of Physics) and techniques and findings from one can be sometimes converted to the others.

> There's Levin's complete one way function [1; Section 4.3]. Breaking it is proven to be as hard as any other one-way function, in other words if there exist one-way functions then this is one of them.

So you could refer to Levin's complete OWF as "one-way-function-inversion-complete"? And, since one-way functions are, by construction, the hardest to invert, it's function-inversion-complete?

Edit: Wait, I guess the second part wouldn't follow, because OWFs only include functions that are easy in the forward direction, so they don't necessarily cover functions that are hard in both directions.

And one-way functions are not necessarily the hardest to invert. They are, in some sense, "hard enough", at least as hard as certain threshold (speaking informally).

What I meant was, the set of OWFs includes the upper bound on inversion difficulty (for functions easy in the forward direction) -- that is, you cannot remove a function from the set of OWFs by making it harder to invert (while preserving forward-direction-easiness).

You say:

> 1. One-way functions are not all cryptography.

The article says:

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

Looks like they alreadyd mentioned that?

Yes, I realized I made some rushed conclusions there.

No worries. The rest of your comment was very informative!

Has this paper actually found anything meaningful or just engaged in sophistry? So instead of using a Turing machine to compute the Kolmogorov complexity where you face the halting problem and uncomputability, they use a time-bounded Turing machine to compute the time-bounded Kolmogorov complexity where you face the hardness of one-way functions.

Yes, constructing a one-way function out of a computation of Kolmogorov complexity is interesting, but frankly it would appear that it is the possible existence of one-way functions (i.e. hard computations) that is more fundamental, just like the uncomputability of the halting problem is more fundamental, not the wrapper that is Kolmogorov complexity.

Reply on news.ycombinator.com