"If your hashing function hashes all messages to the same number of bits (as almost all hash functions do), then the answer is trivially no,... there are only a finite number of inputs ..., so I can hard code the answer for all of them and then look up the answer in linear time."
Good point, but this seems like another easily-correctable problem with my question. Certainly, for one specific h...(more)
Unfortunately, it's completely impractical for real use. Also, I'll reiterate that the fact that this problem is NP-hard tells you nothing about whether this is a good hash function. It may be terrible for almost all inputs.
"If your hashing function hashes all messages to the same number of bits (as almost all hash functions do), then the answer is trivially no,... there are only a finite number of inputs ..., so I can hard code the answer for all of them and then look up the answer in linear time."
Good point, but this seems like another easily-correctable problem with my question. Certainly, for one specific hash function with digest length, you can upper-bound the time required for a solution in all cases (even if that upper bound is infeasibly large), just like you can upper-bound the difficulty of any limited-size version of a problem class (say, general 3-SAT vs 3-SAT with at most 5 clauses).
What I should have asked, I think, is about a family of cryptographic hash functions for which you can set a parameter that determines the digest length n, which can be arbitrary large. In that case, it's clear that the difficulty of hash inversion scales exponentially with n, and (I think) makes it at least as hard as the hardest problems in NP.
In that case, would there be a reduction (in any direction) between (variable-digest-length) hash inversion and NP-complete problems?
...s the digest length <i>n</i>, which can be arbit...(view context)
"If your hashing function hashes all messages to the same number of bits (as almost all hash functions do), then the answer is trivially no,... there are only a finite number of inputs ..., so I can hard code the answer for all of them and then look up the answer in linear time."
Good point, but this seems like another easily-correctable problem with my question. Certainly, for one specific hash function with digest length, you can upper-bound the time required for a solution in all cases (even if that upper bound is infeasibly large), just like you can upper-bound the difficulty of any limited-size version of a problem class (say, general 3-SAT vs 3-SAT with at most 5 clauses).
What I should have asked, I think, is about a family of cryptographic hash functions for which you can set a parameter that determines the digest length <i>n</i>, which can be arbitrary large. In that case, it's clear that the difficulty of hash inversion scales exponentially with n, and (I think) makes it at least as hard as the hardest problems in NP.
In that case, would there be a reduction (in any direction) between (variable-digest-length) hash inversion and NP-complete problems?
Good point, but this seems like another easily-correctable problem with my question. Certainly, for one specific h... (more)
http://en.wikipedia.org/w
Unfortunately, it's completely impractical for real use. Also, I'll reiterate that the fact that this problem is NP-hard tells you nothing about whether this is a good hash function. It may be terrible for almost all inputs.