News for hackers. Stuff that matters.

A comment on Decades-Old Computer Science Conjecture Solved in Two Pages. Parent comment

Re:Decades-Old Computer Science Conjecture Solved in Two Pages by SilasX on Friday July 26, 2019 @08:19AM (#20534167)
Note: correct me if I’m wrong, but to be relevant to this theorem and definition of sensitivity, the two strings would have to be for the same circuit and therefore be the same length, which is much harder than finding hash collisions in general.

And I thought they had ways to construct hash functions so that all the inputs of the same length have a different output?

[ Parent | on HN ]
Re:Decades-Old Computer Science Conjecture Solved in Two Pages by Leszek on Friday July 26, 2019 @09:19AM (#20534537)
> And I thought they had ways to construct hash functions so that all the inputs of the same length have a different output?

That's trivially impossible for fixed-size hashes, by the pigeon hole principle.

[ Parent | on HN ]
Re:Decades-Old Computer Science Conjecture Solved in Two Pages by SilasX on Friday July 26, 2019 @11:43AM (#20535606)
Sorry, I meant all inputs whose length equals the output length.

The point being, for at least that case you can guarantee a sensitivity of one bit.

[ Parent | on HN ]
Re:Decades-Old Computer Science Conjecture Solved in Two Pages by lonelappde on Friday July 26, 2019 @11:00AM (#20535278)
Not if the output is longer than the input, such as for passwords
[ Parent | on HN ]
Re:Decades-Old Computer Science Conjecture Solved in Two Pages by gitrebase on Friday July 26, 2019 @11:09AM (#20535356)
I doubt any study of hash functions restricts itself to studying a very tiny subset of all possible (infinite) inputs. The security of hash functions is always studied under the assumption of arbitrary inputs.
[ Parent | on HN ]