Hacker News Reader

Comment by S4M | Hacker News Reader

It's a nice example, but I think it's flawed. The steps are: folio -> individual -> human -> or -> alternatives -> things.

So, is "folio" the only (five letters) word in the dictionnary that has "individual" as the second word of its definition?

Is "individual" the only word in the dictionnary that has "human" as the third word of its definition?

I doubt it, so their way or identifying words is by no mean bijective, hence it's not a valid one.

View on HN

No, it's not. According to my dictionary search there are two other words (piece and world) with the same word.

And, as you point out, this means that the function is not bijective. However, I am not claiming that it is, I am illustrating a process of going from one word to another that is easy in one direction and hard in the other.

This blog post is not about collision resistance, but it would make a good follow up topic. Especially since some previously thought to be resistant one way functions (MD5 and SHA1) are now known not to be.

I think it's actually a good analogy because of that. When an astute listener asks that question, you have the perfect segue into discussing collisions and why designing cryptographic hash functions is difficult and should be left to experts.

It doesn't matter. The exact point of a one-way function is to go forward from a known answer. It should be very hard (impossible) to go backwards. As the article mentioned, he could have stopped at 1 round but did 5 just to show the concept.

It matters (in the case of the example), because if I tell you "things", you have no way to know if I got it by starting from folio, or from another word X that gave me the steps (for example):

X -> Y -> Z -> or -> alternatives -> things

EDIT: grammatical correction.

I don't want to tell you 'folio'. I want to prove to you that I know the answer is 'folio' without telling you the word 'folio'.

If you thought the answer was 'bored' and you followed the steps (which are not a secret) and you didn't come up with the same end confirmation word as I did. (i.e. me = 'things' you = 'hamster') one of us is wrong and neither of us had to provide our starting word to the other. We don't know who is right yet, we just know we don't agree.

One round leaves some room for error because we could both accidentally choose a word that resolves to the same word in the target position. But since we are doing 5 rounds and moving the target word (1st, 2nd, 3rd etc) for each successive round the odds become much better that we won't have an accidental collision.

(edit: grammar)

I'm not quite sure your last point is true (ie "each successive round the odds become much better") although it's more of a gut feeling than anything else. The universe words in a dictionary is the same so every iteration just chooses another random word from the set. Am I missing something?

Agreed. I think it's clear that looking at the backwards tree, it increases the longer the chain gets. Specifically, the preimage of "things" is at least as large as singleton set "alternatives"; the preimage of the preimage of "things" is larger than the preimage of "alternatives", etc.

I'd argue that you might even run into some convergence since some words will be more common than others. I suppose that's why you're always taking the "Nth" word you find but at some point you just run out words in the definition.

That's actually backwards. Since each round is independent of the last, collisions on an intermediate step will propagate forward. Since each round has the same chance of creating a collision, more rounds means higher total odds.

Yes, and I think it has a jump once you hit a very frequent word (such as "or" from the example).

Reply on news.ycombinator.com